[LeetCode] 1861. Rotating the Box

 Problem : https://leetcode.com/problems/rotating-the-box/

This problem is similar to removing zeros from the input array.

class Solution:
    def rotateTheBox(self, box: List[List[str]]) -> List[List[str]]:
        
        ROW = len(box)
        COLUMN = len(box[0])
        
        for y in range(ROW):
            i = COLUMN - 1
            for x in reversed(range(COLUMN)):
                if box[y][x] == '#':
                    box[y][i] = box[y][x]
                    i -= 1
                elif box[y][x] == '*':
                
                	# set positions between the last empty and the obstacle as empty spaces.
                    while i > x:
                        box[y][i] = '.'
                        i -= 1
                    
                    while i >= 0 and box[y][i] == '*':
                        i -= 1
            
            # set the rest positions as empty spaces
            while i >= 0:
                box[y][i] = '.'
                i -= 1
        
        # rotate the board 90 degrees clockwise
        result = [[''] * ROW for _ in range(COLUMN)]
        
        for y in range(ROW):
            for x in range(COLUMN):
                result[x][ROW-y-1]= box[y][x]
        
        return result

[LeetCode] 1137. N-th Tribonacci Number

 Problem : https://leetcode.com/problems/n-th-tribonacci-number/

Similar to Fibonacci number.

class Solution:
    def tribonacci(self, n: int) -> int:
        dp = [0, 1, 1]
      
        for i in range(3, n+1):
            dp[0], dp[1], dp[2] = dp[1], dp[2], sum(dp)
        
        return dp[n] if n < 2 else dp[2]

[LeetCode] 1239. Maximum Length of a Concatenated String with Unique Characters

 Problem : https://leetcode.com/problems/maximum-length-of-a-concatenated-string-with-unique-characters/

This problem is kind of knapsack problem.  For each sub-string, we can pick it if it does not introduce duplicated character or not pick it and use the rest sub-string to form a longer string.

Time Complexity = O ( N ** 2 ).  N = len(arr)

class Solution:
    def maxLength(self, arr: List[str]) -> int:
        # filter sub-string with duplicated characters
        wordsets = [set(w) for w in arr if len(set(w)) == len(w)]
        
        def helper(start, mask):
            if start >= len(wordsets):
                return len(mask)
            
            # don't pick current sub-string if it introduces duplicated characters
            if mask & wordsets[start]:
                return helper(start + 1, mask)
            
            picked = helper(start + 1, mask | wordsets[start])
            notPicked = helper(start + 1, mask)
            
            return picked if picked > notPicked else notPicked
        
        return helper(0, set())

[LeetCode] 1275. Find Winner on a Tic Tac Toe Game

 Problem : https://leetcode.com/problems/find-winner-on-a-tic-tac-toe-game/

Keep tracking counters of the 3 rows / columns and the 2 diagonals.

Increase counter by 1 if it is player 'A' otherwise decrease counter by 1 for player 'B'.

Player 'A' wins if any counter equals to 3. Player 'B' wins if any counter equals to -3.

class Solution:
    def tictactoe(self, moves: List[List[int]]) -> str:
        rows = [0] * 3
        cols = [0] * 3
        
        diag1 = 0
        diag2 = 0
        
        for i, (y, x) in enumerate(moves):
            player = 1 if i & 1 == 0 else -1
           
            rows[y] += player
            cols[x] += player

            if y == x:
                diag1 += player

            if y == 2 - x:
                diag2 += player
        
            if rows[y] == 3 or cols[x] == 3 or diag1 == 3 or diag2 == 3:
                return 'A'

            if rows[y] == -3 or cols[x] == -3 or diag1 == -3 or diag2 == -3:
                return 'B'
            
        return 'Draw' if len(moves) >= 9 else 'Pending'

[LeetCode] 333. Largest BST Subtree

 Problem : https://leetcode.com/problems/largest-bst-subtree/

To form a BST, the left sub-tree and right sub-tree are also need to be BST.

# 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 largestBSTSubtree(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        
        self.result = 1
        
        def postorder(node):
            if node.left and node.right:
                lmx, lmi, ltotal = postorder(node.left)
                rmx, rmi, rtotal = postorder(node.right)
                
                if ltotal < 0 or rtotal < 0:
                    return lmx, lmi, -1
                
                if node.val <= lmx:
                    return lmx, lmi, -1
                
                if node.val >= rmi:
                    return rmx, rmi, -1
                
                
                self.result = max(self.result, 1 + ltotal + rtotal)
                
                return rmx, lmi, 1 + ltotal + rtotal
            
            if node.left:
                lmx, lmi, ltotal = postorder(node.left)
                
                if ltotal < 0 :
                    return lmx, lmi, -1
                
                if node.val <= lmx:
                    return lmx, lmi, -1
                
                self.result = max(self.result, 1 + ltotal)
                return node.val, lmi, 1 + ltotal
            
            if node.right:
                rmx, rmi, rtotal = postorder(node.right)
                
                if rtotal < 0:
                    return rmx, rmi, -1
                
                if node.val >= rmi:
                    return rmx, rmi, -1
                
                self.result = max(self.result, 1 + rtotal)
                
                return rmx, node.val, 1 + rtotal
            
            return node.val, node.val, 1
        
        postorder(root)
        
        return self.result

[LeetCode] 1586. Binary Search Tree Iterator II

 Problem : https://leetcode.com/problems/binary-search-tree-iterator-ii/

Use another stack to save the previous nodes while iterating through in-order traversal.

# 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 BSTIterator:

    def __init__(self, root: Optional[TreeNode]):
        self.stack = []
        self.pre = []
        
        while root:
            tmp = root.left
            root.left = None
            self.stack.append(root)
            root = tmp
            

    def hasNext(self) -> bool:
        return len(self.stack) > 0
        
    def next(self) -> int:
        node = self.stack.pop()
        self.pre.append(node)
        
        if node.right:
            tmp = node.right
            node.right = None
            
            node = tmp
            
            while node:
                tmp = node.left
                node.left = None
                self.stack.append(node)
                node = tmp
        
        return self.pre[-1].val
    
    def hasPrev(self) -> bool:
        return len(self.pre) >= 2
        

    def prev(self) -> int:
        node = self.pre.pop()
        self.stack.append(node)
        return self.pre[-1].val


# Your BSTIterator object will be instantiated and called as such:
# obj = BSTIterator(root)
# param_1 = obj.hasNext()
# param_2 = obj.next()
# param_3 = obj.hasPrev()
# param_4 = obj.prev()

[LeetCode] 1059. All Paths from Source Lead to Destination

 Problem: https://leetcode.com/problems/all-paths-from-source-lead-to-destination/

We need to check if all paths start from 'source' can end up with the 'destination' and there is no cycle exists on the paths.

class Solution:
    def leadsToDestination(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
        graph = defaultdict(set)
        
        for a, b in edges:
            graph[a].add(b)
            
        def dfs(a, visited):
            if a in visited:
                # detect a cycle
                return False
            
            if not graph[a]:
                # check if it ends up at 'destination'
                return a == destination
            
            visited.add(a)
            
            for b in graph[a]:
                if not dfs(b, visited):
                    return False
            
            visited.remove(a)
            return True
        
        return dfs(source, set())

[LeetCode] 764. Largest Plus Sign

 Problem : https://leetcode.com/problems/largest-plus-sign/

To solve this problem with brute force approach, we need to check length of the 4 arms of each cell and use the shortest arm as the length of the axis-aligned plus sign which be centered by current cell.

To avoid repeatedly calculating arm length, we can use prefix-sum to accelerate.

Time complexity = O ( N * N )

class Solution:
    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:
        
        dp1 = [[0] * n for _ in range(n)]
        dp2 = [[0] * n for _ in range(n)]
        
        mineSet = {(y,x) for y, x in mines}
        
        for y in range(n):
            # left to right
            dp1[y][0] = 0
            for x in range(1, n):
                if (y, x) in mineSet or (y, x-1) in mineSet:
                    dp1[y][x] = 0
                else:
                    dp1[y][x] = dp1[y][x-1] + 1
        
            dp1[y][-1] = 0 
            # right to left
            for x in reversed(range(n-1)):
                if (y, x) in mineSet or (y, x+1) in mineSet:
                    dp1[y][x] = 0
                else:
                    dp1[y][x] = min(dp1[y][x], dp1[y][x+1] + 1)
        
        for x in range(n):
            # top to bottom
            dp2[0][x] = 0
            for y in range(1, n):
                if (y, x) in mineSet or (y-1, x) in mineSet:
                    dp2[y][x] = 0
                else:
                    dp2[y][x] = dp2[y-1][x] + 1
            
            dp2[-1][x] = 0
            # bottom to top
            for y in reversed(range(n-1)):
                if (y, x) in mineSet or (y+1, x) in mineSet:
                    dp2[y][x] = 0
                else:
                    dp2[y][x] = min(dp2[y][x], dp2[y+1][x] + 1)
        
        result = 0
        
        for y in range(n):
            for x in range(n):
                if (y, x) not in mineSet: 
                    result = max(result, min(dp1[y][x], dp2[y][x]) + 1)
        
        return result

[LeetCode] 1631. Path With Minimum Effort

 Problem : https://leetcode.com/problems/path-with-minimum-effort/

This problem cannot be solved by DP. Because for each cell, it can be reached from 4 directions.  There is no way to solve it base on optimal solution.

We may consider the absolute difference from cell A to cell B as the effort to travel from A to B. So the problem can be reduced to using Dijkstra algorithm to find the shortest path from (0,0) cell to (row-1, column-1) cell.

Time Complexity = O(M * N * Log ( M * N ))

class Solution:
    def minimumEffortPath(self, heights: List[List[int]]) -> int:
        ROW = len(heights)
        COLUMN = len(heights[0])
            
        heap = [(0,0,0)]
        visited = [[False] * COLUMN for _ in range(ROW)]
                
        while heap:
            for _ in range(len(heap)):
                e, y, x = heapq.heappop(heap)
                if visited[y][x]:
                    continue
                
                visited[y][x] = True

                if y == ROW - 1 and x == COLUMN - 1:
                    return e

                for dy, dx in [(-1,0), (1,0), (0,-1), (0,1)]:
                    ny, nx = y + dy, x + dx

                    if 0 <= ny < ROW and 0 <= nx < COLUMN and not visited[ny][nx]:               
                        ne = max(e, abs(heights[y][x] - heights[ny][nx]))
                        heapq.heappush(heap, (ne, ny, nx))
                    
        return -1

[LeetCode] 428. Serialize and Deserialize N-ary Tree

 Problem: https://leetcode.com/problems/serialize-and-deserialize-n-ary-tree/

Use preorder traversal to dump the given tree. To make the deserialize process simpler, we dump the size of children list after the node value to indicate how many children node is needed under current node.

"""
# Definition for a Node.
class Node(object):
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
"""

class Codec:
    def serialize(self, root: 'Node') -> str:
        """Encodes a tree to a single string.
        
        :type root: Node
        :rtype: str
        """
        
        def preorder(node):
            yield str(node.val)
            yield str(len(node.children))
            
            for nxt in node.children:
                yield from preorder(nxt)
            
        return ','.join(preorder(root)) if root else ''
	
    def deserialize(self, data: str) -> 'Node':
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: Node
        """
        
        data = data.split(',') if data else []
        

        def helper(index):
            if index >= len(data):
                return None, index
            
            node = Node(val=int(data[index]), children=[])
            index += 1
            size = int(data[index])
            index += 1
            
            for _ in range(size):
                child, index = helper(index)
                node.children.append(child)
                
            return node, index
                
        return helper(0)[0]

# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.deserialize(codec.serialize(root))

[LeetCode] 565. Array Nesting

 Problem: https://leetcode.com/problems/array-nesting/

According to the given rule,  a valid set is built upon with the values of nums[k], nums[nums[k]], ...

We can use Union-Find to build set. Then return size of the largest set as result.

class UnionFind:
    def __init__(self, n):
        self.parent = [i for i in range(n)]
       
    def union(self, a, b):
        ap = self.find(a)
        bp = self.find(b)
        
        if ap != bp:
            self.parent[bp] = ap
     
    def find(self, a):
        if self.parent[a] != a:
            self.parent[a] = self.find(self.parent[a])
        return self.parent[a]

class Solution:
    def arrayNesting(self, nums: List[int]) -> int:
        uf = UnionFind(len(nums))
        
        # build the sets
        for a, b in enumerate(nums):
            if a != b:
                uf.union(a, b)
        
        # get size of the largest set
        count = defaultdict(int)
        
        for i in range(len(nums)):
            count[uf.find(i)] += 1
        
        return max(count.values())