[LeetCode] 1161. Maximum Level Sum of a Binary Tree

 Problem : https://leetcode.com/problems/maximum-level-sum-of-a-binary-tree/

This is an easy problem which can be solved by either DFS or BFS.

But it needs to be aware that because node may have negative value, we cannot determine the final sum of a level until traversal is completed. 

Time Complexity = O (N + N)

# 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 maxLevelSum(self, root: Optional[TreeNode]) -> int:
        levels = []
        stack = [(root, 0)]
        
        while stack:
            node, index = stack.pop()
            
            if index == len(levels):
                levels.append(node.val)
            else:
                levels[index] += node.val
 
            if node.right:
                stack.append((node.right, index + 1))
            if node.left:
                stack.append((node.left, index + 1))
        
        mxSoFar = levels[0]
        miLevel = 0
        
        for level, sums in enumerate(levels):
            if sums > mxSoFar:
                mxSoFar = sums
                miLevel = level
        
        return miLevel + 1

[LeetCode] 742. Closest Leaf in a Binary Tree

 Problem : https://leetcode.com/problems/closest-leaf-in-a-binary-tree/

Because the goal is to find the nearest leaf node,  we use postorder to keep the shortest path to a leaf in left sub-tree or right sub-tree. 

If current node's value == k,  we use the shorter path from left or right sub-tree as the potential result. 

If k does not exist in either left sub-tree or right sub-tree, we only keep the shorter path

If k exists in left sub-tree, we consider path-to-value-k-in-left-sub-tree + shortest-path-to-leaf-in-right-sub-tree as potential result.

Similar procedure when k exists in right sub-tree.

This problem cannot solve by preorder traversal, because it cannot locate the lowest common ancestor with preorder traversal. 

Lesson learned:

- Postorder is useful we need to build path from leaf. 

- On each node, we can build a path by connecting path from left tree and path from right tree.

- We can return as much info as we need in postorder 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 Solution:
    def findClosestLeaf(self, root: Optional[TreeNode], k: int) -> int:
        self.result = None
        
        def postorder(node):
            if not node.left and not node.right:
                if node.val == k:
                    self.result = (0, k)
                    
                return (1, node.val == k, node.val)
            
            leftDepth, leftHasK, leftLeaf = postorder(node.left) if node.left else (1000, False, -1)
            rightDepth, rightHasK, rightLeaf = postorder(node.right) if node.right else (1000, False, -1)
            
            
            if node.val == k:
                if leftDepth < rightDepth:
                    self.result = (leftDepth, leftLeaf)
                    return (1, True, -1)
                else:
                    self.result = (rightDepth, rightLeaf)
                    return (1, True, -1)
            elif leftHasK:
                if leftDepth + rightDepth < self.result[0]:
                    self.result = ((leftDepth + rightDepth), rightLeaf)

                return (leftDepth+1, True, -1)
            elif rightHasK:
                if rightDepth + leftDepth < self.result[0]:
                    self.result = ((rightDepth + leftDepth), leftLeaf)

                return (rightDepth+1, True, -1)
            else:
                if leftDepth < rightDepth:
                    return (leftDepth+1, False, leftLeaf)

                return (rightDepth+1, False, rightLeaf)
            
        
        postorder(root)
        
        return self.result[1]

[LeetCode] 670. Maximum Swap

 Problem : https://leetcode.com/problems/maximum-swap/

To get maximum value, we need to have the larger digits on the higher end.

class Solution:
    def maximumSwap(self, num: int) -> int:
        digits = []
        
        # get digits
        while num:
            digits.append(num % 10)
            num = num // 10
        
        digits = digits[::-1]
        
        # find the max digits on right of each position
        N = len(digits)
        mxFromRight = [0] * N
        
        mxFromRight[N-1] = N-1
        mxForNow = N-1
        
        for i in reversed(range(N)):
            if digits[mxForNow] < digits[i]:
                mxForNow = i
            
            mxFromRight[i] = mxForNow
        
        for i in range(N):
            # iterate from left and swap the first digit not equal to the maximum digit from right side.
            if digits[i] == digits[mxFromRight[i]] :
                continue
            
            digits[i], digits[mxFromRight[i]] =  digits[mxFromRight[i]],  digits[i]
            break
        
        # assemble the final result
        result = 0
        for i in range(N):
            result = result * 10
            result += digits[i]
        
        return result

[LeetCode] 921. Minimum Add to Make Parentheses Valid

 Problem : https://leetcode.com/problems/minimum-add-to-make-parentheses-valid/

Use stack to match left parenthesis with right parenthesis as much as possible.

class Solution:
    def minAddToMakeValid(self, s: str) -> int:
        stack = []
        
        for w in s:
            if w == '(':
                stack.append(w)
            elif stack and stack[-1] == '(':
                stack.pop()
            else:
                stack.append(w)
        
        return len(stack)

[LeetCode] 652. Find Duplicate Subtrees

 Problem : https://leetcode.com/problems/find-duplicate-subtrees/

A tree can be represented by its path. 2 trees are identical if their dumped paths are the same.

Use postorder traversal to find sub-trees with same dumped path.

# 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 findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:
        
        seen = defaultdict(list)
        result = []
        
        def postorder(node):
            if not node: return "#"
            
            key = '(' + str(node.val) + ')'+ postorder(node.left) + postorder(node.right)
            seen[key].append(node)
            
            if len(seen[key]) == 2:
                result.append(node)
            
            return key
        
        postorder(root)
        
        return result

[LeetCode] 1448. Count Good Nodes in Binary Tree

 Problem : https://leetcode.com/problems/count-good-nodes-in-binary-tree/

Use DFS to find number of nodes where value not less than the current local maximum value.

# 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 goodNodes(self, root: TreeNode) -> int:
        
        result = 0
        stack = [(root, -10**4)]
        
        while stack:
            node, mx = stack.pop()
            
            if mx <= node.val:
                result += 1
                mx = node.val
            
            if node.right:
                stack.append((node.right, mx))
            
            if node.left:
                stack.append((node.left, mx))
        
        return result

[LeetCode] 1762. Buildings With an Ocean View

 Problem : https://leetcode.com/problems/buildings-with-an-ocean-view/

Maintain a decreasing monotonic stack.

class Solution:
    def findBuildings(self, heights: List[int]) -> List[int]:
        stack = []
        
        for i, h in enumerate(heights):
            while stack and heights[stack[-1]] <= h:
                stack.pop()
            
            stack.append(i)
        
        return stack

[LeetCode] 1019. Next Greater Node in Linked List

 Problem : https://leetcode.com/problems/next-greater-node-in-linked-list/

Use postorder traversal and maintain a decreasing monotonic stack.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def nextLargerNodes(self, head: Optional[ListNode]) -> List[int]:
        result = []
        
        def postorder(node):
            if node.next:
                stack = postorder(node.next)
                while stack and stack[-1] <= node.val:
                    stack.pop()
                
                result.append(stack[-1] if stack else 0)                
                stack.append(node.val)
                
                return stack
            else:
                result.append(0)
                return [node.val]
        
        postorder(head)
        return result[::-1]

Or maintain a increasing monotonic stack which also saves the position of each smaller value.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def nextLargerNodes(self, head: Optional[ListNode]) -> List[int]:
        result = []
        stack = []
        
        while head:
            while stack and stack[-1][1] < head.val:
                result[stack[-1][0]] = head.val
                stack.pop()
            
            stack.append([len(result), head.val])
            result.append(0)
            
            head = head.next
        
        return result

[LeetCode] 256. Paint House

 Problem : https://leetcode.com/problems/paint-house/

Let the state dp[i] as minimum cost by using color i to paint current house. Because current state is decided by the last state. This problem can be solved by DP solution. 

class Solution:
    def minCost(self, costs: List[List[int]]) -> int:
        N = len(costs)
        dp = costs[0]
        
        for i in range(1, N):
            dp = [min(dp[1], dp[2]) + costs[i][0], min(dp[0], dp[2]) + costs[i][1], min(dp[0], dp[1]) + costs[i][2]]
        
        return min(dp)

[LeetCode] 265. Paint House II

 Problem : https://leetcode.com/problems/paint-house-ii/

A naive DP solution. 

Time complexity = O ( N * K * K )

class Solution:
    def minCostII(self, costs: List[List[int]]) -> int:
        N = len(costs)
        K = len(costs[0])
        MAX_INT = 2**31 - 1
        
        dp = costs[0]
        
        for i in range(1, N):
            tmp = [MAX_INT] * K
            
            for j in range(K):
                for k in range(K):
                    if j != k:            
                        tmp[j] = min(tmp[j], costs[i][j] + dp[k])
            
            dp = tmp
        
        return min(dp)

Use extra space to find the minimal value of DP except position i. 

Time complexity  = O ( N * K )

class Solution:
    def minCostII(self, costs: List[List[int]]) -> int:
        N = len(costs)
        K = len(costs[0])
        MAX_INT = 2**31 - 1
        
        dp = costs[0]
        
        for i in range(1, N):
            tmp = [MAX_INT] * K
            leftMi = [MAX_INT] * K  # minimum value from left
            rightMi = [MAX_INT] * K # minimum value from right
            
            mi = dp[0]
            for j in range(1, K):
                leftMi[j] = mi
                mi = min(mi, dp[j])
            
            mi = dp[K-1]
            for j in reversed(range(K-1)):
                rightMi[j] = mi
                mi = min(mi, dp[j])
            
            for j in range(K):
                tmp[j] = min(leftMi[j], rightMi[j]) + costs[i][j]
            
            dp = tmp
        
        return min(dp)

[LeetCode] 926. Flip String to Monotone Increasing

 Problem : https://leetcode.com/problems/flip-string-to-monotone-increasing/

One valid monotone-increasing can either end by '0'  or '1'.

For every s[i], consider the number of flip may need by appending it to the monotone-increasing ended by flipping s[i-1].

class Solution:
    def minFlipsMonoIncr(self, s: str) -> int:
        N = len(s)
        
        end_by_zero = 0 if s[0] == '0' else 1
        end_by_one = 0 if s[1] == '1' else 0
        
        for i in range(1, N):
            if s[i] == '0':
                # no need to flip to expand valid monotone increasing end by 0
                # end_by_zero = end_by_zero
                
                # flip 0 to 1 to expand valid monotone increasing end by 1
                end_by_one = end_by_one + 1
            elif s[i] == '1':
                # no need to flip to expand valid monotone increasing end by 1
                end_by_one = min(end_by_zero, end_by_one)
                
                # flip 1 to 0 to expand valid monotone increasing end by 1
                end_by_zero = end_by_zero + 1         
        
        return min(end_by_zero, end_by_one)

[LeetCode] 415. Add Strings

 Problem: https://leetcode.com/problems/add-strings/

Simulate the process of adding 2 numbers.

class Solution:
    def addStrings(self, num1: str, num2: str) -> str:
        num1 = [int(w) for w in num1]
        num2 = [int(w) for w in num2]
        
        result = []
        carry = 0
        
        while num1 or num2:
            a = num1.pop() if num1 else 0 
            b = num2.pop() if num2 else 0
            
            c = a + b + carry
            
            result.append(c % 10)
            carry = c // 10
        
        if carry:
            result.append(carry)
        
        return ''.join([str(w) for w in reversed(result)])

[LeetCode] 276. Paint Fence

 Problem : https://leetcode.com/problems/paint-fence/

Similar to the climbing-stairs, we should think about the 'last state'.

When we paint the last fence, we either paint it with a different color or paint it with the same color as the last 2 fence.

class Solution:
    def numWays(self, n: int, k: int) -> int:
        end_with_diff_color = [0] * n
        end_with_same_color = [0] * n
        
        end_with_diff_color[0] = k
        
        for i in range(1, n):
            end_with_diff_color[i] = end_with_same_color[i-1] * (k-1) + end_with_diff_color[i-1] * (k-1)
            end_with_same_color[i] = end_with_diff_color[i-1]
            
        return end_with_diff_color[-1] + end_with_same_color[-1]

Because "i" state only dependes on the result of "i - 1" state. We can reduce the space complexity.

class Solution:
    def numWays(self, n: int, k: int) -> int:
        end_with_same_color, end_with_diff_color = 0, k
    
        for i in range(1, n):
            end_with_same_color, end_with_diff_color = end_with_diff_color, end_with_same_color * (k-1) + end_with_diff_color * (k-1)
                        
        return end_with_diff_color + end_with_same_color

[LeetCode] 429. N-ary Tree Level Order Traversal

 Problem : https://leetcode.com/problems/n-ary-tree-level-order-traversal/

BFS Solution:

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

class Solution:
    def levelOrder(self, root: 'Node') -> List[List[int]]:
        if not root: return []
        
        queue = [root]
        result = []
        
        while queue:
            result.append([node.val for node in queue])
            queue = [child for node in queue for child in node.children]
        
        return result

DFS Solution:

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

class Solution:
    def levelOrder(self, root: 'Node') -> List[List[int]]:
        if not root: return []
        
        result = []
        
        stack = [(root, 0)]
        
        while stack:
            node, level = stack.pop()
            
            if level == len(result):
                result.append([node.val])
            else:
                result[level].append(node.val)
            
            for child in reversed(node.children):
                stack.append((child, level+1))
        
        return result

[LeetCode] 827. Making A Large Island

 Problem : https://leetcode.com/problems/making-a-large-island/

Consider an island is a group, it is intuitive to use union-find to find the size of islands then find the maximum size of island when join 2 disconnected islands together.

class UnionFind:
    def __init__(self, n):
        self.group = [i for i in range(n)]
        self.usize = defaultdict(lambda:1)
        
    def union(self, a, b):
        ap = self.find(a)
        bp = self.find(b)
        
        if ap != bp:
            self.group[bp] = ap
            self.usize[ap] += self.usize[bp]
            self.usize[bp] = 0
        
    
    def find(self, a):
        b = self.group[a]
        
        while b != self.group[b]:
            b = self.group[b]
        
        while self.group[a] != b:
            tmp = self.group[a]
            self.group[a] = b
            a = tmp
        
        return b
    
    def sizeOf(self, a):
        ap = self.find(a)
        return self.usize[ap]
            

class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        ROW = len(grid)
        COLUMN = len(grid[0])
        
        uf = UnionFind(ROW * COLUMN)
        
        for y in range(ROW):
            for x in range(COLUMN):
                # union the adjucent '1's
                for dy, dx in [(-1,0), (0,-1)]:
                    ny, nx = y + dy, x + dx
                    if 0 <= ny < ROW and 0 <= nx < COLUMN and grid[ny][nx] == 1 and grid[y][x] == 1:
                        uf.union(ny*COLUMN + nx, y*COLUMN + x)
        
        result = 0
        for y in range(ROW):
            for x in range(COLUMN):
                if grid[y][x] == 1:
                    result = max(result, uf.sizeOf(y*COLUMN + x))
                else:
                    tmp = {}
                    # connect the disjointed unions
                    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 grid[ny][nx] == 1:
                            p = uf.find(ny * COLUMN + nx)
                            tmp[p] = uf.sizeOf(p)
                    
                    result = max(result, sum(tmp.values()) + 1)
        
        return result

[LeetCode] 1168. Optimize Water Distribution in a Village

 Problem :  https://leetcode.com/problems/optimize-water-distribution-in-a-village/

This problem can be reduced to a Minimum Spanning Tree problem.

We may consider the cost to build well in a village is the cost to reach to this village from any other villages. So we can use greedy algorithm to get the minimum cost to visit all villages.

class Solution:
    def minCostToSupplyWater(self, n: int, wells: List[int], pipes: List[List[int]]) -> int:
        graph = defaultdict(list)
        
        # consider the cost of laying pipe between village 'a' and 'b'
        # as the cast to reach village 'a' from 'b' and vice versa
        for a, b, cost in pipes:
            graph[a].append((b, cost))
            graph[b].append((a, cost))
        
        visited = set()
        
        heap = []
        total = 0
        
        # consider the cost of building well in one village
        # as the cost to reach to this building from any other building
        for i in range(n):
            heapq.heappush(heap, (wells[i], i+1))
        
        # greedily find the the minimum cost to visit all villages.
        while heap and len(visited) < n:
            cost, a = heapq.heappop(heap)
            
            if a not in visited:
                total += cost
                
                visited.add(a)
                
                for b, bcost in graph[a]:
                    heapq.heappush(heap, (bcost, b))
        
        return total

[LeetCode] 863. All Nodes Distance K in Binary Tree

 Problem : https://leetcode.com/problems/all-nodes-distance-k-in-binary-tree/

It is straightforward  to use BFS to collect the nodes on distance K in the binary tree. 

To support move upward and downward simultaneously, we need to add one more pointer to point from each node to its parent node. So we convert the given binary tree to a directed graph. 

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def distanceK(self, root: TreeNode, target: TreeNode, k: int) -> List[int]:
        
        # use dfs to find parent of each nodes
        parent = {root: None}
        def dfs(node):
            for child in [node.left, node.right]:
                if child:
                    parent[child] = node
                    dfs(child)
        
        dfs(root)
        
        # start from target node and use bfs to find all nodes on distance k
        queue = deque([target])
        visited = set([target])
        
        result = []
        step = 0
        
        while queue and step <= k:
            for _ in range(len(queue)):
                node = queue.popleft()
                if step == k:
                    result.append(node.val)
                
                for nxt in [node.left, node.right, parent[node]]:
                    if nxt and nxt not in visited:
                        visited.add(nxt)
                        queue.append(nxt)
                
            step += 1
                
        return result

[LeetCode] 1711. Count Good Meals

 Problem : https://leetcode.com/problems/count-good-meals/

This problem is like an enhanced 2sum problem. The only difference is, the 'target' number is not explicitly given.

class Solution:
    def countPairs(self, deliciousness: List[int]) -> int:
        M = 10 ** 9 + 7
        result = 0
        seen = defaultdict(int)
        
        # sort the numbers first
        # for one given number there is no larger number before it.
        deliciousness.sort()
        
        for n in deliciousness:
            # the maximum sum of 'n' is n + n
            # try every power of two less than n + n
            target = 1
            while target <= n + n:
                result += seen[target - n]
                result %= M
                target *= 2
            
            # increase the counter of n
            seen[n] += 1
        
        return result