[LeetCode] 367. Valid Perfect Square

 Problem : https://leetcode.com/problems/valid-perfect-square/

Generally, for number N, it's square root is in the range of [1, N)

Use binary search to find the square root.

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        
        left, right = 1, num
        
        while left <= right:
            
            mid = left + (right - left) // 2
            
            if mid * mid == num:
                return True
            
            if mid * mid > num:
                right = mid - 1
            else:
                left = mid + 1
        
        
        return False

[LeetCode] 365. Water and Jug Problem

 Problem : https://leetcode.com/problems/water-and-jug-problem/

This problem equals to consider there is a large container, use the 2 jugs to pour water into the container or take water out of the container, and end up with z liters water in the container.

a * x + b * y = z

Positive a / b means pour water into the container.

Negative a / b means take water out of the container.

According to Bézout's identity :  a * x + b * y =  GCD( x, y )

GCD : greatest common divisor of x and y.

So, we can get the needed liters of water when GCD( x, y ) % z == 0.

class Solution:
    def canMeasureWater(self, x: int, y: int, z: int) -> bool:
        
        def gcd(a, b):
            if a != 0:
                return gcd(b%a, a)
            else:
                return b

        if x > y:
            x, y = y, x
            
        
        return z == 0 or z <= (x + y) and y > 0 and z % gcd(x, y) == 0

[LeetCode] 363. Max Sum of Rectangle No Larger Than K

 Problem : https://leetcode.com/problems/max-sum-of-rectangle-no-larger-than-k/

class Solution:
    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:
        if not matrix or not matrix[0]: return 0
        
        ROW = len(matrix)
        COLUMN = len(matrix[0])
        result = -2 ** 31
        
        for left in range(COLUMN):
            rowSums = [0] * ROW
            
            for right in range(left, COLUMN):
                
                for i in range(ROW):
                    rowSums[i] += matrix[i][right]
                    
                # find the max subarry no more than k
                dp = [0]
                total = 0

                for rsum in rowSums:
                    total += rsum

                    i = bisect.bisect_left(dp, total - k)
                    if i < len(dp): 
                        result = max(result, total - dp[i])

                    bisect.insort(dp, total)
            
        return result

[LeetCode] 357. Count Numbers with Unique Digits

 Problem : https://leetcode.com/problems/count-numbers-with-unique-digits/

The input number N means the maximum number of digits we can have for the wanted numbers.

Let F(N) = valid number of unique digits combination for N digits

F(0) = 0. Wanted number = 0. Total number = 1

F(1) = 1. Wanted number = [0 ... 9].   Total number = 10

F(2) =  9 * 9 + F (1) = 91.   The first digit has 9 options from 1 to 9. The second digit has 9 options from 0 to 9 ( excluding the digit used by the first digits)

F(3) = 9 * 9 * 8 + F(2) + F(1)

class Solution:
    def countNumbersWithUniqueDigits(self, n: int) -> int:
        if n == 0:
            return 1
        
        if n == 1:
            return 10
        
        result = 9
        digits = 9
        
        # calculate valid combiations of N digits
        for _ in range(1,n):
            result *= digits
            digits -= 1
        
        return result + self.countNumbersWithUniqueDigits(n-1)

[LeetCode] 335. Design Twitter

 Problem : https://leetcode.com/problems/design-twitter/

- Tweet be posted later may have smaller tweetId. So we need to save the time when the tweet be post.

- Should not allow user to follow themselves.

- Should not allow user to unfollow not-followed user.

from operator import itemgetter

class Twitter:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.timer = 1
        self.follows = defaultdict(set)
        self.tweets = defaultdict(list)

    def postTweet(self, userId: int, tweetId: int) -> None:
        """
        Compose a new tweet.
        """
        self.tweets[userId].append((self.timer, tweetId))
        self.timer += 1
        

    def getNewsFeed(self, userId: int) -> List[int]:
        """
        Retrieve the 10 most recent tweet ids in the user's news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent.
        """
        
        allTweets = self.tweets[userId][:]
        
        for f in self.follows[userId]:
            allTweets.extend(self.tweets[f])
            
        
        allTweets.sort(reverse = True, key = itemgetter(0))
        allTweets = allTweets if len(allTweets) <= 10 else allTweets[:10]
        
        return [tweetId for _, tweetId in allTweets]
                

    def follow(self, followerId: int, followeeId: int) -> None:
        """
        Follower follows a followee. If the operation is invalid, it should be a no-op.
        """
        
        if followerId != followeeId:
            self.follows[followerId].add(followeeId)
        

    def unfollow(self, followerId: int, followeeId: int) -> None:
        """
        Follower unfollows a followee. If the operation is invalid, it should be a no-op.
        """
        
        if followerId != followeeId and followeeId in self.follows[followerId]:
            self.follows[followerId].remove(followeeId)
        


# Your Twitter object will be instantiated and called as such:
# obj = Twitter()
# obj.postTweet(userId,tweetId)
# param_2 = obj.getNewsFeed(userId)
# obj.follow(followerId,followeeId)
# obj.unfollow(followerId,followeeId)

[LeetCode] 354. Russian Doll Envelopes

 Problem : https://leetcode.com/problems/russian-doll-envelopes/

This problem equals to find the length of longest increasing subsequence on 2 dimensions.

1. Sort the array. Ascending on width and descend on height for same width.

Because [3,3] cannot be contained by [3, 4], we need to put [3,4] in front of [3,3]. Otherwise,  "[3,3], [3,4]" will be considered as a valid increasing subsequence.

2.  Find the longest increasing subsequence base on height.

Since width of envelop has been sorted in increasing order, we only need to consider height.

Time Complexity = O ( N Log N )

from functools import cmp_to_key

class Solution:
    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
        
        def lowerBound(dp, n):
            left, right = 0, len(dp)
            
            while left < right:
                mid = left + (right - left) // 2
                
                if dp[mid] == n:
                    right = mid
                elif dp[mid] > n:
                    right = mid
                elif dp[mid] < n:
                    left = mid + 1
            
            return left
        
        def compare(a, b):
            return a[0] - b[0] if a[0] != b[0] else b[1] - a[1]
        
        envelopes.sort(key=cmp_to_key(compare))
        
        dp = []
        
        for _, h  in envelopes:
            i = lowerBound(dp, h)
            
            if i == len(dp):
                dp.append(h)
            else:
                dp[i] = h
        
        return len(dp)

[LeetCode] 352. Data Stream as Disjoint Intervals

 Problem : https://leetcode.com/problems/data-stream-as-disjoint-intervals/

Use binary search to find the insertion point. Then merge the previous and next intervals.

class SummaryRanges:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        
        self.intervals = []

    def addNum(self, val: int) -> None:
        
        left, right = 0, len(self.intervals)
        
        while left < right:
            mid = left + (right -left) // 2
            
            tmp = self.intervals[mid]
            
            if tmp[0] <= val <= tmp[1]:
                return
            
            if tmp[0] > val:
                right = mid
            elif tmp[1] < val:
                left = mid + 1
        
        self.intervals.insert(left, [val, val])
        
        cur = self.intervals[left]
        pre = self.intervals[left-1] if left -1 >= 0 else None
        nxt = self.intervals[left+1] if left + 1 < len(self.intervals) else None
        
        if pre and pre[1] + 1 == cur[0]:
            pre[1] = cur[0]
            cur = pre
            self.intervals.pop(left)
            left -= 1
        
        if nxt and cur[1] + 1 == nxt[0]:
            cur[1] = nxt[1]
            self.intervals.pop(left + 1)
            

    def getIntervals(self) -> List[List[int]]:
            return self.intervals

[LeetCode] 350. Intersection of Two Arrays II

Problem : https://leetcode.com/problems/intersection-of-two-arrays-ii/

2 pointers solution:  

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        nums1.sort()
        nums2.sort()
        
        result = []
        i = j = 0
        
        while i < len(nums1) and j < len(nums2):
            if nums1[i] < nums2[j]:
                i += 1
            elif nums1[i] > nums2[j]:
                j += 1
            else:
                result.append(nums1[i])
                i += 1
                j += 1
        
        return result

When elements are stored on disk, use external sort algorithm to sort items first. Then use this 2 pointers approach to find the intersection.

Hash table based solutin:

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        counter1 = Counter(nums1)
        counter2 = Counter(nums2)
        
        result = []
        
        for k, v1 in counter1.items():
            v2 = counter2.get(k, 0)
            
            if min(v1, v2):
                result += [k] * min(v1, v2)
        
        return result

Edited on 09/17/2021. Update a simpler hash table based solution.

[LeetCode] 349. Intersection of Two Arrays

 Problem : https://leetcode.com/problems/intersection-of-two-arrays/

Binary search solution: 

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        
        def bsearch(nums, target):
            left, right = 0, len(nums)
            
            while left < right:
                mid = left + (right - left) // 2
                if nums[mid] == target:
                    return True
                if nums[mid] < target:
                    left = mid + 1
                else:
                    right = mid
            
            return False
        
        result = []
        
        if len(nums1) > len(nums2) : nums1, nums2 = nums2, nums1
        
        nums1.sort()
        nums2.sort()
        
        for i, n in enumerate(nums1):
            if i - 1 >= 0 and nums1[i] == nums1[i-1]:
                continue
            
            if bsearch(nums2, n):
                result.append(n)
            
        
        return result

2 pointers solution:

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        nums1.sort()
        nums2.sort()
        
        result = []
        
        i = j = 0
        
        while i < len(nums1) and j < len(nums2):
            if nums1[i] < nums2[j]:
                i += 1
            elif nums1[i] > nums2[j]:
                j += 1
            else:
                if not result or result[-1] != nums1[i]:
                    result.append(nums1[i])
                i += 1
                j += 1
        
        return result

Hash table based solution:

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        seen = defaultdict(lambda : [0, 0])
        
        for n in nums1:
            seen[n][0] += 1
        
        for n in nums2:
            seen[n][1] += 1
            
        
        return filter(lambda n : seen[n][0] >= 1 and seen[n][1] >= 1, seen.keys())

[LeetCode] 347. Top K Frequent Elements

 Problem : https://leetcode.com/problems/top-k-frequent-elements/

Use hash map to save count of each elements. 

Then use heap to get first k element .

Time Complexity = O ( N Log k )

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        if k > len(nums): return nums
        
        count = Counter(nums)
        
        return heapq.nlargest(k, count.keys(), key=count.get)

[LeetCode] 345. Reverse Vowels of a String

 Problem : https://leetcode.com/problems/reverse-vowels-of-a-string/

class Solution:
    def reverseVowels(self, s: str) -> str:
        vowels = set(['a', 'A', 'e', 'E', 'i', 'I', 'o', 'O', 'u', 'U'])
        result = [w for w in s]
        
        i, j = 0, len(s)-1
        
        while i <= j:
            if result[i] not in vowels:
                i += 1
            elif result[j] not in vowels:
                j -= 1
            else:
                result[i], result[j] = s[j], s[i]
                i += 1
                j -= 1
           
        return "".join(result)

[LeetCode] 344. Reverse String

 Problem : https://leetcode.com/problems/reverse-string/

An uncommon 2 pointers approach.

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        N = len(s)
        for i in range(N//2):
            j = N - i - 1
            s[i], s[j] = s[j], s[i]

[LeetCode] 343. Integer Break

 Problem : https://leetcode.com/problems/integer-break/

For each number i,  it can be broken into at least  j,  (i-j).  j = [1 ... i -1]

Let DP[i] = maximum product of number i when i be broken into at least 2 integers.

DP[i] = Max( j * (i-j),  j * DP[i-j] ),    j = [ 1 ... i - 1 ]

class Solution:
    def integerBreak(self, n: int) -> int:
        dp = [1] * (n+1)
        
        for i in range(3, n+1):
            for j in range(1, i):
                dp[i] = max(dp[i], max(j* (i-j),  j *dp[i-j]))
        
        return dp[n]

Another memorization approach:

class Solution {
    int[] memo;
    
    public int integerBreak(int n) {
        memo = new int[n+1];
        memo[1] = 1;
        
        return helper(n);
    }
    
    int helper(int n) {
        if (memo[n] != 0) {
            return memo[n];
        }
        
        for (int x = 1; x <= n / 2; x++) {
            
            // i.e. For number 3,  helper(3) = 1 * 2 = 2. 
            // 3 > helper(3).  we need to use 3 instead of helper(3) to get the larger product.
            memo[n] = Math.max(memo[n], Math.max(x, helper(x)) * Math.max(n-x, helper(n-x)));
        } 
        
        return memo[n];
    }
}

Edited on 11/26/2021. Update the top-down solution.

[LeetCode] 342. Power of Four

 Problem : https://leetcode.com/problems/power-of-four/

A recursive solution :

class Solution:
    def isPowerOfFour(self, num: int) -> bool:
        if num == 0: return False
        return num == 1 or num % 4 == 0 and self.isPowerOfFour(num // 4)

A math solution:

If N is power of 4, Log(N, base=4) is an integer.

class Solution:
    def isPowerOfFour(self, num: int) -> bool:
        return num > 0 and log(num, 4) % 1 == 0

[LeetCode] 341. Flatten Nested List Iterator

 Problem : https://leetcode.com/problems/flatten-nested-list-iterator/

Use stack to cache the expanded lists.

Must filter out the empty nested lists in hasNext() method.

# """
# This is the interface that allows for creating nested lists.
# You should not implement it, or speculate about its implementation
# """
#class NestedInteger:
#    def isInteger(self) -> bool:
#        """
#        @return True if this NestedInteger holds a single integer, rather than a nested list.
#        """
#
#    def getInteger(self) -> int:
#        """
#        @return the single integer that this NestedInteger holds, if it holds a single integer
#        Return None if this NestedInteger holds a nested list
#        """
#
#    def getList(self) -> [NestedInteger]:
#        """
#        @return the nested list that this NestedInteger holds, if it holds a nested list
#        Return None if this NestedInteger holds a single integer
#        """

class NestedIterator:
    def __init__(self, nestedList: [NestedInteger]):
        self.stack = []
        for n in reversed(nestedList):
            self.stack.append(n)
    
    def next(self) -> int:
        return self.stack.pop().getInteger()
        
    def hasNext(self) -> bool:
        while self.stack and not self.stack[-1].isInteger():
            # expand non-empty nested list
            nestedList = self.stack.pop().getList()
            if nestedList:
                for n in reversed(nestedList):
                    self.stack.append(n)

        return self.stack
         

# Your NestedIterator object will be instantiated and called as such:
# i, v = NestedIterator(nestedList), []
# while i.hasNext(): v.append(i.next())

Another approach of using stack. It's similar to how compiler maintains call-stack.

# """
# This is the interface that allows for creating nested lists.
# You should not implement it, or speculate about its implementation
# """
#class NestedInteger:
#    def isInteger(self) -> bool:
#        """
#        @return True if this NestedInteger holds a single integer, rather than a nested list.
#        """
#
#    def getInteger(self) -> int:
#        """
#        @return the single integer that this NestedInteger holds, if it holds a single integer
#        Return None if this NestedInteger holds a nested list
#        """
#
#    def getList(self) -> [NestedInteger]:
#        """
#        @return the nested list that this NestedInteger holds, if it holds a nested list
#        Return None if this NestedInteger holds a single integer
#        """

class NestedIterator:
    def __init__(self, nestedList: [NestedInteger]):
        self.stack = [[nestedList, 0]]
    
    def next(self) -> int:
        nlist, nindex = self.stack[-1]
        
        self.stack[-1][1] += 1
        return nlist[nindex].getInteger()
        
    
    def hasNext(self) -> bool:     
        while self.stack:
            nlist, nindex = self.stack[-1]

            if nindex == len(nlist):
                self.stack.pop()
                continue

            if nlist[nindex].isInteger():
                break

            self.stack[-1][1] += 1
            childList = nlist[nindex].getList()
            if childList:
                self.stack.append([childList, 0])
        
        return self.stack
         

# Your NestedIterator object will be instantiated and called as such:
# i, v = NestedIterator(nestedList), []
# while i.hasNext(): v.append(i.next())

Edited on 04/13/2021. Add the second stack based approach.

[LeetCode] 338. Counting Bits

 Problem : https://leetcode.com/problems/counting-bits/

A naive solution:

Time complexity = O (n * sizeof(integer))  

class Solution:
    def countBits(self, num: int) -> List[int]:
        def helper(n):
            result = 0
            while n:
                result += n & 1
                n >>= 1
            
            return result
        
        return [helper(n) for n in range(num+1)]

A DP solution:

class Solution:
    def countBits(self, num: int) -> List[int]:
        result = [0] * (num + 1)
        if num >= 1:
            result[1] = 1
            
            for i in range(2, num+1):
                if i & 1 == 0:
                    # if i is even number
                    result[i] = result[i//2]
                else:
                    # if i is odd number
                    result[i] = result[i//2] + 1
        
        return result

[LeetCode] 337. House Robber III

 Problem : https://leetcode.com/problems/house-robber-iii/

Each level of the tree has 2 state :   safe or  not-safe.

If current level is safe to rob, thief can choose rob current level then next level is not safe to rob. Or skip current level, then next level is safe to rob.

Use memorization approach to find the answer.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def rob(self, root: TreeNode) -> int:
        
        @lru_cache(maxsize = None)
        def helper(node, safe):
            result = 0
            
            if node:
                if safe:
                    result = node.val + helper(node.left, not safe) + helper(node.right, not safe)
                    result = max(result, helper(node.left, safe) + helper(node.right, safe))
                else:
                    result = helper(node.left, not safe) + helper(node.right, not safe)
                
            return result
        
        return max(helper(root, True), helper(root, False))

[LeetCode] 336. Palindrome Pairs

 Problem : https://leetcode.com/problems/palindrome-pairs/

There are 3 cases can form a palindrome string.

1)  ABC + CBA

2)  CBA + [A-Palindrome-String] ABC 

3)  ABC[A-Palindrome-String]  + CBA   

class Solution:
    def palindromePairs(self, words: List[str]) -> List[List[int]]:
        
        def isPalindrome(w, left, right):
            while left < right:
                if w[left] != w[right]: return False
                left += 1
                right -= 1
            
            return True
        
        
        result = []
        seen = { k : v for v, k in enumerate(words) }
        lens = sorted({len(w) for w in words})
        
        for i, w in enumerate(words):
            # rw = reversed 'w'
            rw = w[::-1]
            
            # case abc -- cba
            if rw in seen and seen[rw] != i:
                result.append([i, seen[rw]])
                
            l = 0
            while lens[l] < len(rw):
                # case cba  -- ddabc                
                if isPalindrome(rw, 0, len(rw) - lens[l] - 1) and \
                   rw[len(w) - lens[l]:] in seen:
                    
                    result.append([i, seen[rw[len(w) - lens[l]:]]])
                # case abcdd -- cba
                if isPalindrome(rw, lens[l], len(rw)-1) and \
                   rw[:lens[l]] in seen:
                    result.append([seen[rw[:lens[l]]], i])
                
                l += 1
        
        return result

Use Trie to find possible suffix.

class TrieNode:
    def __init__(self, val):
        self.val = val
        self.index = -1
        self.nodes = {}


class Trie:
    def __init__(self):
        self.root = TrieNode('')
    
    def add(self, index, word):
        if not word:
            self.root.index = index
        else:
            p = self.root
            
            for w in word:
                if w in p.nodes:
                    p = p.nodes[w]
                else:
                    node = TrieNode(w)
                    p.nodes[w] = node
                    p = node
                    
            p.index = index
        
def isPalindrome(word):
    if not word: return True
    
    left, right = 0, len(word)-1
    
    while left < right and word[left] == word[right]:
        left += 1
        right -=1 
    
    return left >= right

class Solution:
    def palindromePairs(self, words: List[str]) -> List[List[int]]:
        trie = Trie()
        
        for index, word in enumerate(words):
            trie.add(index, word[::-1])
        
        result = []
        
        for index, word in enumerate(words):
            i = 0
            p = trie.root
                        
            # dfs
            stack = [(p, "")]
            
            while stack:
                p, suffix = stack.pop()
                
                if p.index != -1 and p.index != index and isPalindrome(word[i:] + suffix):
                    result.append((index, p.index))
                
                if not suffix and i < len(word) and word[i] in p.nodes:
                    stack.append((p.nodes[word[i]], ""))
                    i += 1
                else:
                    for n in p.nodes.values():
                        stack.append((n, n.val + suffix))
        return result

Edited on 06/13/2021. Add the Trie based solution.

[LeetCode] 335. Self Crossing

 Problem : https://leetcode.com/problems/self-crossing/

There are only 3 cases can lead self-crossing.

class Solution:
    def isSelfCrossing(self, x: List[int]) -> bool:
        N = len(x)
        
        for i in range(N):
            # 4th line >= 2nd line and 1st line >= 3rd line
            if i >= 3 and x[i] >= x[i-2] and x[i-3] >= x[i-1]:
                return True
            
            # 2nd line == 4th line and 5th line >= 3rd line - 1st line
            if i >= 4 and x[i-1] == x[i-3] and x[i] >= x[i-2] - x[i-4]:
                return True
            
            # 4th line >= 2nd line and 
            # 3rd line >= 5th line and 
            # 5th line >= 3rd line - 1st line
            # and 6th line >= 4th line - 2nd line
            
            if i >= 5 and x[i-2] >= x[i-4] and \
               x[i-3] >= x[i-1] and \
               x[i-1] >= x[i-3] - x[i-5] and \
               x[i] >= x[i-2] - x[i-4]:
                return True
        
        return False