[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