[LeetCode] 542. 01 Matrix

 Problem : https://leetcode.com/problems/01-matrix/

Start from all '0' cells and use BFS to find the shortest distance to '1' cells.

class Solution:
    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
        ROW = len(mat)
        COLUMN = len(mat[0])
        
        result = [[ROW*COLUMN] * COLUMN for _ in range(ROW)]
        queue = deque([])
        
        for y in range(ROW):
            for x in range(COLUMN):
                if mat[y][x] == 0:
                    result[y][x] = 0
                    queue.append((y, x))
        
        step = 1
        
        while queue:
            for _ in range(len(queue)):
                y, x= queue.popleft()

                for dy, dx in [(0,1), (0,-1), (1,0), (-1,0)]:
                    ny = y + dy
                    nx = x + dx
                    if 0 <= ny < ROW and 0 <= nx < COLUMN:
                        if step > result[ny][nx]:
                            continue

                        result[ny][nx] = step
                        queue.append((ny, nx))
            
            step += 1
            
        return result

[LeetCode] 549. Binary Tree Longest Consecutive Sequence II

 Problem : https://leetcode.com/problems/binary-tree-longest-consecutive-sequence-ii/

Assume we only construct increasing consecutive sequence. So a new node value can append to a sequence in below 3 scenarios:

[new value] xxxxx : add to the start position

xxxxx [new value] : add to the end position

xxxxx [new value] xxxxx : add to the middle of sequence from the left and right subtree.

# 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 longestConsecutive(self, root: TreeNode) -> int:
        self.result = 0
        
        def postorder(node):
            """
            return (s, e)
            s : the length of the longest sequence which starts with 'node'
            e : the length of the longest sequence which ends by 'node'
            """
            
            if node.left and node.right:
                ls, le = postorder(node.left)
                rs, re = postorder(node.right)
                s = e = 1
                
                if node.left.val + 1 == node.val and node.val + 1 == node.right.val:
                    self.result = max(self.result, le + 1 + rs)
                    
                    s = max(s, rs + 1)
                    e = max(e, le + 1)
                
                if node.left.val - 1 == node.val and node.val - 1 == node.right.val:
                    self.result = max(self.result, ls + 1 + re)
                    
                    s = max(s, ls + 1)
                    e = max(e, re + 1)
                
                if node.left.val + 1 == node.val:
                    self.result = max(self.result, le + 1)
                    e = max(e, le + 1)
                
                if node.left.val - 1 == node.val:
                    self.result = max(self.result, ls + 1)
                    s = max(s, ls + 1)
                
                if node.right.val + 1 == node.val:
                    self.result = max(self.result, re + 1)
                    e = max(e, re + 1)
                
                if node.right.val - 1 == node.val:
                    self.result = max(self.result, rs + 1)
                    s = max(s, rs + 1)
            
                return s, e
            
            if node.left:
                ls, le = postorder(node.left)
                s = e = 1
                
                if node.left.val + 1 == node.val:
                    self.result = max(self.result, le + 1)
                    e = max(e, le + 1)
                
                if node.left.val - 1 == node.val:
                    self.result = max(self.result, ls + 1)
                    s = max(s, ls + 1)
                
                return s, e
            
            if node.right:
                rs, re = postorder(node.right)
                s = e = 1
                
                if node.right.val + 1 == node.val:
                    self.result = max(self.result, re + 1)
                    e = max(e, re + 1)
                
                if node.right.val - 1 == node.val:
                    self.result = max(self.result, rs + 1)
                    s = max(s, rs + 1)
                    
                return s, e
            
            self.result = max(self.result, 1)
            return 1, 1
        
        
        postorder(root)
        
        return self.result

[LeetCode] 894. All Possible Full Binary Trees

 Problem : https://leetcode.com/problems/all-possible-full-binary-trees/

A full binary tree must have odd number of nodes.  So we can find all possible left and right sub trees to construct the needed trees.

# 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:
    @cache
    def allPossibleFBT(self, n: int) -> List[TreeNode]:
        if n == 1:
            return [TreeNode()]
        
        result = []
        
        for i in range(1, n+1):
            left = i - 1
            right = n - i
            
            if left % 2 == 1 and right % 2 == 1:
                lts = self.allPossibleFBT(left)
                rts = self.allPossibleFBT(right)
                
                for lt in lts:
                    for rt in rts:
                        result.append(TreeNode(left=lt, right=rt))
        
        return result

[LeetCode] 814. Binary Tree Pruning

 Problem : https://leetcode.com/problems/binary-tree-pruning/

Use postorder traversal to check if sub-tree has "one".  Delete the sub-tree if it does not have "one".

# 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 pruneTree(self, root: TreeNode) -> TreeNode:

        def postOrder(node):
            if not node:
                return False
            
            hasOneLeft = postOrder(node.left)
            if not hasOneLeft:
                node.left = None
            
            hasOneRight = postOrder(node.right)
            if not hasOneRight:
                node.right = None
            
            return node.val == 1 or hasOneLeft or hasOneRight
        
        return root if postOrder(root) else None

[LeetCode] 915. Partition Array into Disjoint Intervals

 Problem : https://leetcode.com/problems/partition-array-into-disjoint-intervals/

The requirement of all numbers in left sub-array are less than or equal to numbers in right sub-array can be interpreted as the maximum number in left sub-array is less than or equal to the minimum number in right sub-array.

class Solution:
    def partitionDisjoint(self, nums: List[int]) -> int:
        N = len(nums)
        
        # maximum number from left of nums[i] ( includes nums[i] )
        maxFromLeft = [0] * N
        maxFromLeft[0] = nums[0]
        
        for i in range(1, N):
            maxFromLeft[i] = max(maxFromLeft[i-1], nums[i])
        
        # minimum number from right of nums[i]
        minFromRight = nums[N-1]
        result = N-1
        
        for i in reversed(range(1, N)):
            minFromRight = min(minFromRight, nums[i])
            
            if minFromRight >= maxFromLeft[i-1]:
                result = i
        
        return result

[LeetCode] 611. Valid Triangle Number

 Problem : https://leetcode.com/problems/valid-triangle-number/

To form a valid triangle, the 3 side lengths must compel with  A + B > C.

Use binary search to find number of C which less than (A + B).

class Solution:
    def triangleNumber(self, nums: List[int]) -> int:
        nums.sort()
        result = 0
        
        for i in range(len(nums)):
            for j in range(i+1, len(nums)-1):
                k = bisect.bisect_left(nums, nums[i] + nums[j], j+1, len(nums))
                result +=  k - (j+1)
        
        return result

Java solution:

class Solution {
    public int triangleNumber(int[] nums) {
        Arrays.sort(nums);
        int result = 0;
        
        for (int i = 0; i < nums.length -1; i++) {
            for (int j = i+1; j < nums.length - 1; j++) {
                int k = lowerBound(nums, nums[i] + nums[j], j+1, nums.length);
                result += k - (j+1);
            }
        }
        
        return result;
    }
    
    /**
    * Return position of the first number >= target
    */
    int lowerBound(int[] nums, int target, int start, int end) {
        int left = start;
        int right = end;
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            
            if (nums[mid] > target)
                right = mid;
            else if (nums[mid] < target)
                left = mid + 1;
            else if (nums[mid] == target)
                right = mid;
        }
        
        return right;
    }
}

[LeetCode] 370. Range Addition

 Problem : https://leetcode.com/problems/range-addition/

Use scan line approach to increase value when update section starts and decrease value when update section ends.

Time complexity = O( M + N ) ,   M = len(updates), N = length.

class Solution:
    def getModifiedArray(self, length: int, updates: List[List[int]]) -> List[int]:
        
        memo = defaultdict(int)
        
        for a, b, d in updates:
            memo[a] += d
            memo[b+1] -= d
            
        value = 0
        result = []
        for i in range(length):
            value += memo[i]
            result.append(value)
        
        return result

[LeetCode] 717. 1-bit and 2-bit Characters

 Problem : https://leetcode.com/problems/1-bit-and-2-bit-characters/

Remove the last 2 bits, then check if the remaining sequence is still valid.

If the remaining sequence is not valid, then the last character must be a one-bit character.

class Solution:
    def isOneBitCharacter(self, bits: List[int]) -> bool:
        
        @cache
        def helper(i):
            """
            return True is bits[:i] is a valid sequence
            """
            
            if i == 0:
                return True
            
            # bits[i-1] can be decoded as the one-bit character
            if bits[i-1] == 0 and helper(i-1):
                return True
            
            # bits[i-2]bits[i-1] can be decoded as the two-bit character
            if i - 2 >= 0 and bits[i-2] == 1:
                return helper(i-2)
            
            # bits[:i] is an invalid sequence
            return False
        
        # bits[-2] == 0 so bits[-1] must be decoded as one-bit character
        if len(bits) == 1 or bits[-2] == 0: return True
        
        # return False if the remaining sequence is still valid by removing the last 2 bits
        return not helper(len(bits) - 2)

[LeetCode] 639. Decode Ways II

 Problem : https://leetcode.com/problems/decode-ways-ii/

The top-down solution:

class Solution:
    def numDecodings(self, s: str) -> int:
        
        @cache
        def helper(start):
            """
            total decoding way of s[start:]
            """
            
            if start == len(s):
                return 1
            
            # '0' cannot be the leading digit
            if s[start] == '0':
                return 0
            
            # total decoding way when consider s[start] is a letter
            result = (9 if s[start] == '*' else 1) * helper(start + 1)
            
            # total decoding way when consider s[start]s[start+1] is a letter 
            if start + 1 < len(s):
                if s[start] == '1':
                    if s[start+1] != '*':
                        result += 1 * helper(start + 2)
                    else:
                        # s[start+1] == '*'
                        result += 9 * helper(start + 2)
                elif s[start] == '2':
                    if '0' <= s[start+1] <= '6':
                        result += 1 * helper(start + 2)
                    elif s[start+1] == '*':
                        result += 6 * helper(start + 2)
                elif s[start] == '*':
                    if '0' <= s[start+1] <= '6':
                        result += 2 * helper(start + 2)
                    elif '7' <= s[start+1] <= '9':
                        result += 1 * helper(start + 2)
                    elif s[start+1] == '*':
                        result += (9 + 6) * helper(start+2)
            
            return result % (10 ** 9 + 7)
         
        return helper(0)

The bottom-up solution:

class Solution:
    def numDecodings(self, s: str) -> int:
        M = 10 ** 9 + 7
        N = len(s)
        
        if s[0] == '0': return 0
        
        dp = [0] * (N+1)
        dp[0] = 1
        dp[1] = 9 if s[0] == '*' else 1
        
        for i in range(1, N):
            if s[i] == '*':
                dp[i+1] = 9 * dp[i] % M
                
                if s[i-1] == '1':
                    dp[i+1] = (dp[i+1] + 9 * dp[i-1]) % M
                elif s[i-1] == '2':
                    dp[i+1] = (dp[i+1] + 6 * dp[i-1]) % M
                elif s[i-1] == '*':
                    dp[i+1] = (dp[i+1] + 15 * dp[i-1]) % M
            else:
                dp[i+1] = dp[i] if s[i] != '0' else 0
                if s[i-1] == '1':
                    dp[i+1] = (dp[i+1] + dp[i-1]) % M
                elif s[i-1] == '2' and s[i] <= '6':
                    dp[i+1] = (dp[i+1] + dp[i-1]) % M
                elif s[i-1] == '*':
                    if s[i] <= '6':
                        dp[i+1] = (dp[i+1] + 2 * dp[i-1]) % M
                    else:
                        dp[i+1] = (dp[i+1] + dp[i-1]) % M
        
        return dp[N]

[LeetCode] 1220. Count Vowels Permutation

 Problem : https://leetcode.com/problems/count-vowels-permutation/

In one state, we remember the number of permutations end by a particular vowel letter. Then the next state can be built upon the current state base on the given extending rule.

class Solution:
    def countVowelPermutation(self, n: int) -> int:
        vowels = {v: 1 for v in ['a', 'e', 'i', 'o', 'u']}
        
        for i in range(1, n):
            tmp = {}
            # extend permutations by appending 'a'
            tmp['a'] = vowels['e'] + vowels['u'] + vowels['i']
            # extend permutations by appending 'e'
            tmp['e'] = vowels['a'] + vowels['i']
            # extend permutations by appending 'i'
            tmp['i'] = vowels['e'] + vowels['o']
            # extend permutations by appending 'o'
            tmp['o'] = vowels['i']
            # extend permutations by appending 'u'
            tmp['u'] = vowels['o'] + vowels['i']
            # move to the next state
            vowels = tmp
        
        return sum(vowels.values()) % (10**9 + 7)

[LeetCode] 464. Can I Win

 Problem : https://leetcode.com/problems/can-i-win/

The state of this game is the integers be used. Because maximal number of integer is no more than 20.  

We can use bitmask to remember the used integers. 

Also use True to represent the first player wins and use False to represent the second player wins.

Time complexity = O( 2 ** N ).   For each integer we consider whether use it or not to form a new state.  There are 2 ** N states. 

class Solution:
    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:
        
        # use bitmask to remember the picked integer
        mask = 0
        
        @cache
        def helper(mask, sums, a):
            for i in range(maxChoosableInteger):
                
                # bypass if the integer (i+1) is already used
                if mask & (1 << i) != 0:
                    continue
                
                # current player wins when sums >= desiredTotal
                if sums + i + 1 >= desiredTotal:
                    return a
                
                # mark integer (i+1) is used
                mask ^= (1 << i)
                
                # because both players play optimally
                # we consider current player must chooses this routine
                # which leads to a win result for hime
                if helper(mask, sums + i + 1, not a) ==  a:
                    
                    # mark integer (i+1) is not used
                    mask ^= (1 << i)
                    
                    # current player can force a win
                    return a
                
                # mark integer (i+1) is not used
                mask ^= (1 << i)
            
            # current player cannot force a win
            return not a
        
        # it is impossible to win whe sum of all integers is less than the desiredTotal
        if maxChoosableInteger * (maxChoosableInteger + 1) // 2 < desiredTotal: return False
        
        return helper(0, 0, True)