[LeetCode] 1026. Maximum Difference Between Bode and Ancestor

 Problem : https://leetcode.com/problems/maximum-difference-between-node-and-ancestor/

Calculate the difference of node.val and the maximum and minimum value from its child trees.

Time complexity = O(N), N = total nodes of the given tree.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int maxAncestorDiff(TreeNode root) {
        return postOrder(root)[2];
    }
    
    int[] postOrder(TreeNode node) {
        int mi = node.val;
        int mx = node.val;
        int diff = 0;
        
        for (TreeNode child: new TreeNode[] {node.left, node.right}) {
            if (child != null) {
                // mi, mx, diff
                int[] tmp = postOrder(child);
                
                mi = Math.min(mi, tmp[0]);
                mx = Math.max(mx, tmp[1]);
                
                diff = Math.max(diff, tmp[2]); 
                diff = Math.max(diff, Math.abs(node.val - tmp[0]));
                diff = Math.max(diff, Math.abs(node.val - tmp[1])); 
            }
        }
        
        return new int[] {mi, mx, diff};
    }
}

[LeetCode] 876. Middle of the Linked List

 Problem : https://leetcode.com/problems/middle-of-the-linked-list/

The fast and slow pointer approach :

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        
        while (fast != null  && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        
        return slow;
    }
}

[LeetCode] 973. K Closest Points to Origin

 Problem : https://leetcode.com/problems/k-closest-points-to-origin/

Use max priority queue to find the K closest points.

Time complexity = O( N * Log K ),  N = length of the input array. 

Space complexity = O ( K ),  the priority queue will contain at most K elements.

class Solution {
    public int[][] kClosest(int[][] points, int k) {
        // create a max priority queue for saving the K closest points
        PriorityQueue<int[]> pq = new PriorityQueue<int[]>((a, b) -> distanceOf(b) - distanceOf(a));
        
        for (int i = 0; i < points.length; i++) {
            if (pq.size() < k) {
                // put the point into the priority queue if the queue size is less than K
                pq.offer(points[i]);
            } else if (distanceOf(pq.peek()) > distanceOf(points[i])) {
                // otherwise, add the new point into priority queue if it is closer than the top point.
                // because it is max priority queue, the top point is the furthest point so far.
                // this condition check is needed to avoid blindly adding new point inito priority queue.
                pq.poll();
                pq.offer(points[i]);
            }
        }
    
        return pq.toArray(new int[0][]);
    }
    
    int distanceOf(int[] p) {
        return p[0] * p[0] + p[1] * p[1];
    }
}

Quick Selection solutioin.

Time complexity = O(N)

class Solution {
    public int[][] kClosest(int[][] points, int k) {
        return quickSelect(points, 0, points.length-1, k);
    }
    
    int[][] quickSelect(int[][] points, int left, int right, int k) {       
        while (left < right) {
            int p = partition(points, left, right);
            if (p == k-1) {
                break;
            }
            
            if (p < k-1) {
                // continue to sort the rang [p+1, right]
                left = p + 1;
            } else {
                // continue to sort the range [left, p-1]
                right = p - 1;
            }
        }
        
        return Arrays.copyOf(points, k); 
    }
    
    int partition(int[][] points, int left, int right) {
        // use points[left] as the pivot value
        int pivotDistance = distanceOf(points[left]);
        
        int i = left, j = right + 1; // left and right scan indices
        
        while (true) {
            // scan left, stop when points[i] > pivotDistance or i reaches the array end
            while (distanceOf(points[++i]) < pivotDistance) if (i == right) break;
            // scan right, stop when points[j] < pivotDistance or j reaches the array start
            while (distanceOf(points[--j]) > pivotDistance) if (j == left) break;
            
            // stop scan
            if (i >= j) break;
            
            // exchange i and j
            int[] tmp = points[j];
            points[j] = points[i];
            points[i] = tmp;
        }
        
        // points[j] is the last element on right smaller than points[left]
        // swap 'left' and 'j'
        int[] tmp = points[left];
        points[left] = points[j];
        points[j] = tmp;
        
        return j;
    }
    
    int distanceOf(int[] p) {
        return p[0] * p[0] + p[1] * p[1];
    }
}

Edited on 12/26/2021. Add the quick select solution.

I got the 2021 annual medal badge

[LeetCode] 1200. Minimum Absolute Difference

 Problem : https://leetcode.com/problems/minimum-absolute-difference/

Because the minimum difference can only exist between 2 consecutive elements in sorted list.

We sort the input array first, then find the pairs with minimum difference.

Time complexity = O(N * LogN) + O(N),  N = length of the input array.

class Solution {
    public List<List<Integer>> minimumAbsDifference(int[] arr) {
        int miGlobal = Integer.MAX_VALUE;
        List<List<Integer>> result = new ArrayList();
        
        // minimum absolute difference can only exist between 2 consecutive elements
        Arrays.sort(arr);
        
        for (int i = 1; i < arr.length; i++) {
            int miLocal = arr[i] - arr[i-1];
            if (miLocal < miGlobal) {
                // start a new result when find a new minimum difference
                miGlobal = miLocal;
                result = new ArrayList(Arrays.asList(Arrays.asList(arr[i-1], arr[i])));
            } else if (miLocal == miGlobal) {
                // otherwise append this new pair to the result list.
                result.add(Arrays.asList(arr[i-1], arr[i]));
            }
        }
        
        return result;
    }
}

Because the value range of the input array is from -10^6 to 10^6, the input array can be sorted with counting sort approach which Time complexity is O(N)

[LeetCode] 394. Decode String

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

Use 2 stacks to decode. One stack save the counter. Another stack save of the decoded string of current level.

Time Complexity = O ( N * K ),  N = length of the input string. K = maximum value of the counter .

class Solution {
    public String decodeString(String s) {
        // save the decoded string
        // use StringBuilder to avoid repeatedly creating string object
        Stack<StringBuilder> strStack = new Stack();
        // save the counter of decoded string
        Stack<Integer> counterStack = new Stack();
        
        strStack.push(new StringBuilder());
        int count = 0;
        
        for (Character a: s.toCharArray()) {            
            if (Character.isDigit(a)) {
                // important!  counter k may have more than one digits!
                count = count * 10 + (a - '0');
            } else if (a == '[') {
                // push the counter
                counterStack.push(count);
                // push a new string builder to start a new level
                strStack.push(new StringBuilder());
                // reset the counter
                count = 0;
            } else if (a == ']') {
                // current level decoded string
                String decoded = strStack.pop().toString(); 
                // count of current level decoded string
                int n = counterStack.pop();
                
                // append the decoded string to its upper level string
                for (int j = 0; j < n; j++) {
                    strStack.peek().append(decoded);
                }
            } else {
                // append the character to current level string
                strStack.peek().append(String.valueOf(a));
            }
        }
        
        return strStack.peek().toString();
    }
}

[LeetCode] 938. Range Sum of BST

 Problem : https://leetcode.com/problems/range-sum-of-bst/

Use BST property to trim branches outside of the range.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int rangeSumBST(TreeNode root, int low, int high) {
        if (root == null) return 0;
        // left subtree and current node are out of the range
        if (root.val < low)  return rangeSumBST(root.right, low, high);
        // right subtree and current node are out of the range
        if (root.val > high) return rangeSumBST(root.left, low, high);
        // current node is inside of the range
        return rangeSumBST(root.left, low, high) + root.val + rangeSumBST(root.right, low, high);
    }
}

[LeetCode] 1306. Jump Game III

Problem : https://leetcode.com/problems/jump-game-iii/

A typical BFS problem. In case it encounters a loop during the traversal, it is impossible to reach to the position with value 0.

Time complexity = O ( N ).   N = length of the arr. Because we need to every item in the input array at least once.

class Solution {
    public boolean canReach(int[] arr, int start) {
        if (arr[start] == 0) return true;
        
        int N = arr.length;
        boolean[] visited = new boolean[N];
        visited[start] = true;
        
        Queue<Integer> queue = new LinkedList();
        queue.offer(start);
        
        int[] diffs = new int[] {1, -1};
        
        while (!queue.isEmpty()) {
            int index = queue.poll();
                        
            for (int d : diffs) {
                int next  = index + d * arr[index];
                if (next >= 0 && next < N && !visited[next]) {
                    if (arr[next] == 0) return true;

                    visited[next] = true;
                    queue.offer(next);
                }
            }
        }
        
        return false;
    }
}

[LeetCode] 1032. Stream of Characters

 Problem : https://leetcode.com/problems/stream-of-characters/

This is an obvious Tire problem. It is difficult because it is hard to realize the edge cases at the first place.

We cannot assume one input word cannot be prefix of another input word.

Such as:  ["ab","ba","aaab","abab","baa"]

To cover all cases, we need to remember the last pointer of all valid prefixes.

class TrieNode {
    char letter = 0;
    boolean end = false;
    HashMap<Character, TrieNode> children = new HashMap();
}

class StreamChecker {
    TrieNode root = new TrieNode();
    Queue<TrieNode> queue = new LinkedList();
    
    public StreamChecker(String[] words) {
        for (int i = 0; i < words.length; i++) {
            TrieNode p = root;
            
            for (int j = 0; j < words[i].length(); j++) {
                if (p.children.containsKey(words[i].charAt(j))) {
                    p = p.children.get(words[i].charAt(j));
                } else {
                    TrieNode tmp = new TrieNode();
                    tmp.letter = words[i].charAt(j);
                    p.children.put(words[i].charAt(j), tmp);
                    p = tmp;
                }
            }
            
            p.end = true;
        }
    }
    
    public boolean query(char letter) {
        queue.offer(root);
        
        boolean found = false;
        Queue<TrieNode> next = new LinkedList();
        
        while (!queue.isEmpty()) {
            TrieNode p = queue.poll();
            
            if (p.children.containsKey(letter)) {
                next.offer(p.children.get(letter));
                if (p.children.get(letter).end) {
                    found = true;
                }
            }
        }
        
        queue = next;
        return found;
    }
}

However this process is not optimized.

A better solution is saving the prefixes backwards in Trie. Because all potential valid prefixes end with the same letter.

class TrieNode:
    def __init__(self, w = None):
        self.w = w
        self.children = {}
        self.end = False

class StreamChecker:

    def __init__(self, words: List[str]):
        self.root = TrieNode()
        self.max_len = 0
        self.stream = deque()
        
        for word in words:
            self.max_len = max(self.max_len, len(word))
            
            p = self.root
            
            for w in word[::-1]:
                if w not in p.children:
                    trie = Trie(w)
                    p.children[w] = trie
                    p = trie
                else:
                    p = p.children[w]
            
            p.end = True
                      

    def query(self, letter: str) -> bool:
        self.stream.append(letter)
        
        while len(self.stream) > self.max_len:
            self.stream.popleft()
        
        p = self.root
        
        for w in reversed(self.stream):
            
            if w in p.children:
                p = p.children[w]
                if p.end:
                    return True
            else:
                return False
                
        return False

[LeetCode] 721. Accounts Merge

 Problem : https://leetcode.com/problems/accounts-merge/

Use union-find to group email address of the same account.  Remember to sort the mail list in the end.

class UnionFind {
    int[] parent;
    
    UnionFind(int size) {
        parent = new int[size];
        
        for (int i = 0; i < size; i++) {
            parent[i] = i;
        }
    }
    
    void union(int a, int b) {
        int ap = find(a);
        int bp = find(b);
        
        if (ap != bp) {
            parent[ap] = bp;
        }
    }
    
    int find(int a) {
        if (parent[a] == a) {
            return a;
        }
        
        parent[a] = find(parent[a]);
        
        return parent[a];
    }
}


class Solution {
    public List<List<String>> accountsMerge(List<List<String>> accounts) {
        int ID = 0;
        
        // convert mail to ids
        HashMap<String, Integer> mailIds = new HashMap();
        HashMap<Integer, String> idToMail = new HashMap();
        HashMap<String, Integer> mailToName = new HashMap();
        
        for (int i = 0; i < accounts.size(); i++) {
            for (int j = 1; j < accounts.get(i).size(); j++) {
                if (mailIds.containsKey(accounts.get(i).get(j))) {
                    continue;
                }
                
                mailIds.put(accounts.get(i).get(j), ID);
                idToMail.put(ID, accounts.get(i).get(j));
                ID++;
                mailToName.put(accounts.get(i).get(j), i);
            }    
        }
        
        // use union-find to group mail ids
        UnionFind uf = new UnionFind(ID);
        
        for (int i = 0; i < accounts.size(); i++) {
            for (int j = 2; j < accounts.get(i).size(); j++) {
                uf.union(mailIds.get(accounts.get(i).get(j-1)), mailIds.get(accounts.get(i).get(j)));        
            }
        }
        
        // construct the mail list
        HashMap<Integer, List<String>> groups = new HashMap();
        
        for (int i = 0; i < ID; i++) {
            String email = idToMail.get(i);
       
            if (groups.containsKey(uf.find(i))) {
                groups.get(uf.find(i)).add(email);
            } else {
                List<String> emailList = new ArrayList();
                emailList.add(email);
                groups.put(uf.find(i), emailList);
            }
        }
        
        List<List<String>> result = new ArrayList();
        for (int pid : groups.keySet()) {
            List<String> list = new ArrayList();
            
            // sort mails
            Collections.sort(groups.get(pid));
            String name = accounts.get(mailToName.get(idToMail.get(pid))).get(0);
            
            list.add(name);
            list.addAll(groups.get(pid));
            result.add(list);
        }
        
        return result;
    }
}

[LeetCode] 369. Plus One Linked List

 Problem : https://leetcode.com/problems/plus-one-linked-list/

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode plusOne(ListNode head) {
        // reverse list
        ListNode reversed = reverse(head);
        
        int carry = 1;    
        ListNode p = reversed;
        ListNode last = null;
        
        while(p != null) {
            int total = p.val + carry;
            p.val = total % 10;
            carry = total / 10;
            last = p;
            p = p.next;
        }
        
        if (carry != 0) {
            last.next = new ListNode(carry);
        }
        
        
        return reverse(reversed);
    }
    
    ListNode reverse(ListNode head) {
        ListNode last = null;
        ListNode current = head;
        ListNode next = head.next;
        
        while (next != null) {
            current.next = last;
            last = current;
            current = next;
            next = current.next;
        }
        
        // remember to link the last element!
        current.next = last;
        return current;
    }
}

[LeetCode] 647. Palindromic Substrings

 Problem: https://leetcode.com/problems/palindromic-substrings/

class Solution {
    public int countSubstrings(String s) {
        int N = s.length();
        
        boolean[][] dp = new boolean[N][N];
        int result = 0;
        
        for (int i= N-1; i >= 0; i--) {
            for (int j = N-1; j >= i; j--) {
                dp[i][j] = s.charAt(i) == s.charAt(j) && (j - i <= 1 || dp[i+1][j-1]);
                if (dp[i][j]) {
                    result += 1;
                }
            }
        }
        
        return result;
    }
}

[LeetCode] 450. Delete Node in a BST

 Problem : https://leetcode.com/problems/delete-node-in-a-bst/

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode deleteNode(TreeNode root, int key) { 
        if (root == null) {
            return root;
        }
        
        // delete node from left sub-tree
        if (root.val > key) {
            root.left = deleteNode(root.left, key);
            return root;
        }
        
        // delete node from right sub-tree
        if (root.val < key) {
            root.right = deleteNode(root.right, key);
            return root;
        }
        
        // root.val == key
        if (root.left == null) {
            return root.right;
        }
        
        if (root.right == null) {
            return root.left;
        }
        
        // use right node as the new root
        TreeNode newRoot = root.right;
        
        // Because all nodes in right sub-tree are larger than current root node,
        // and left child is less than current root node, 
        // then the left child must be the smallest value comparing to the right sub-tree.
        // Attach current left child to the most left node of the right sub-tree.
        TreeNode p = root.right;
        while (p.left != null) {
            p = p.left;
        }
        
        p.left = root.left;
        
        return newRoot;
    }
}

[LeetCode] 448. Find All Numbers Disappeared in an Array

 Problem : https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array/

Because all numbers in the array is in the range [1, n].  If all numbers exist in the array, we can always swap the numbers to make nums[i] = i + 1.

So try to swap the number to its correct position. Then iterate the array to find the missing number which nums[i] != i + 1

class Solution {
    fun findDisappearedNumbers(nums: IntArray): List<int> {
        for (i in 0 until nums.size) {
            while (nums[i] != i+1) {
                if (nums[nums[i] - 1] == nums[i]) {
                    break
                }
                
                val tmp = nums[nums[i] - 1]
                nums[nums[i] - 1] = nums[i]
                nums[i] = tmp
            }
        }
        
        val result = mutableListOf<int>()
        
        for (i in 0 until nums.size) {
            if (nums[i] != i + 1) {
                result.add(i+1)
            }
        }
        
        return result
    }
}

[LeetCode] 739. Daily Temperatures

 Problem : https://leetcode.com/problems/daily-temperatures/

Use monotonic stack to keep a decreasing sequence.

class Solution {
    fun dailyTemperatures(temperatures: IntArray): IntArray {
        val stack = Stack<int>()
        val result = IntArray(temperatures.size) { 0 }
        
        for (i in 0 until temperatures.size) {
            // pop all the days which temperature is lower than current day
            while (!stack.empty() && temperatures[stack.peek()] < temperatures[i]) {
                val last = stack.pop()
                result[last] = i - last 
            }
            
            stack.push(i)
        }
        
        return result
    }
}

[LeetCode] 1014. Best Sightseeing Pair

 Problem : https://leetcode.com/problems/best-sightseeing-pair/

Keep tracking the maximum score we encountered. Decrease the maximum score while iterating to right side.

class Solution {
    fun maxScoreSightseeingPair(values: IntArray): Int {
        var mxScore = values[0]
        var result = 0
        
        for (i in 1 until values.size) {
            mxScore -= 1
            
            result = maxOf(result, values[i] + mxScore)    
            mxScore = maxOf(mxScore, values[i])
        }
        
        return result
    }
}

[LeetCode] 1567. Maximum Length of Subarray With Positive Product

 Problem : https://leetcode.com/problems/maximum-length-of-subarray-with-positive-product/

Positive A * Positive B -> Positive C

Negative A * Negative B -> Positive C

Keep tracking positive and negative product result sub-array length end by current number. 

Reset sub-array length when encounter '0'

class Solution {
    fun getMaxLen(nums: IntArray): Int {
        var positiveSoFar = 0
        var negativeSoFar = 0
        var result = 0
        
        for (n in nums) {
            if (n > 0) {
                positiveSoFar += 1
                negativeSoFar = if (negativeSoFar > 0) negativeSoFar + 1 else 0
            } else if (n < 0) {
                val prePositiveSoFar = positiveSoFar
                positiveSoFar = if (negativeSoFar > 0 ) negativeSoFar + 1 else 0
                negativeSoFar = prePositiveSoFar + 1
                
            } else {
                positiveSoFar = 0
                negativeSoFar = 0
            }
            
            result = maxOf(result, positiveSoFar)
        }
        
        return result
    }
}

[LeetCode] 918. Maximum Sum Circular Subarray

 Problem : https://leetcode.com/problems/maximum-sum-circular-subarray/

In a circular integer, the maximum sum of sub-array can exists in 2 parts:

AAABBBBA'A'A'

It may either exist in the contiguous sub-array [BBBB] or exists in the sub-array [A'A'A'AAA] which combined by the front and rear sub-arrays. 

It is easy to get maximum value of [BBBB].

The maximum value of [A'A'A'AAA] = total value - minimum value of [BBBB]

When the maximum value of [BBBB] <= 0, all numbers in the given array must <= 0.

The the total value == minimum 

The maximum sum of sub-array can only exist in [BBBB].

class Solution {
    fun maxSubarraySumCircular(nums: IntArray): Int {
        // maximum value of contiguous sub-array
        var mx = nums[0]
        var mxSoFar = nums[0]
        
        // minimum value of contiguous sub-array
        var mi = nums[0]
        var miSoFar = nums[0]
        
        for (i in 1 until nums.size) {
            mxSoFar = maxOf(mxSoFar + nums[i], nums[i])
            mx = maxOf(mx, mxSoFar)
            
            miSoFar = minOf(miSoFar + nums[i], nums[i])
            mi = minOf(mi, miSoFar)
        }
        
        // if mx > 0 :
        //     the maximum value either exists in one contiguous sub-array
        //     or existis in the combination of the front sub-array 
        //     and rear sub-array (= total - miSoFar)
        // if mx <= 0 :
        //     all numbers in the input array <= 0.
        //     mx is the maximum sum of sub-array 
        return if (mx > 0) maxOf(mx, nums.sum() - mi) else mx 
        
    }
}

[LeetCode] 1413. Minimum Value to Get Positive Step by Step Sum

 Problem : https://leetcode.com/problems/minimum-value-to-get-positive-step-by-step-sum/

Assume x is a valid start value, then x + 1 is also a start value.

Assume x is an invalid start value, then x - 1 is also a invalid start value.

So there is a contiguous valid start value section. We can use binary search to find the lower bound of the section.

class Solution {
    fun minStartValue(nums: IntArray): Int {
    
        fun isValid(x: Int): Boolean {
            var prefixSum = x
            
            nums.forEach {
                prefixSum += it
                if (prefixSum < 1) {
                    return false
                }
            }
            
            return true
        }
        
        // valid start value section [1, nums.size * 100 + 1]
        // 1 -> when all numbers in the array equal to 0
        // nums.size * 100 + 1 -> when all numbers in the array equal to -100
        
        var left = 1
        var right = nums.size * 100 + 1
        
        while (left < right) {
            val mid = left + (right - left) / 2
            
            if (isValid(mid)) {
                right = mid
            } else {
                left = mid + 1
            }
            
        }
        
        return right
    }
}

[LeetCode] 766. Toeplitz Matrix

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

No need to travel diagonally. Only need to check if number of one position equals to the number on its bottom-right position.

class Solution:
    def isToeplitzMatrix(self, matrix: List[List[int]]) -> bool:
        
        ROW = len(matrix)
        COLUMN = len(matrix[0])
        
        for y in range(ROW-1):
            for x in range(COLUMN-1):
                if matrix[y][x] != matrix[y+1][x+1]:
                    return False
                
        return True

The one liner solution:

class Solution:
    def isToeplitzMatrix(self, matrix: List[List[int]]) -> bool:
        ROW = len(matrix)
        COLUMN = len(matrix[0])
        
        return all(matrix[y][x] == matrix[y+1][x+1] for y in range(ROW-1) for x in range(COLUMN-1))

[LeetCode] 404. Sum of Left Leaves

 Problem : https://leetcode.com/problems/sum-of-left-leaves/

Use post-order traversal to accumulate left leave values.

# 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 sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
        
        self.result = 0
        
        def postorder(node):
            if not node.left and not node.right:
                # find a leaf
                return True
            
            if node.left and postorder(node.left):
                # find a left leaf
                self.result += node.left.val
            
            if node.right:
                postorder(node.right)
            
            return False
        
        postorder(root)
        return self.result

[LeetCode] 441. Arranging Coins

 Problem : https://leetcode.com/problems/arranging-coins/

Because 1 + 2 + 3 + ... + n = n * (n+1) / 2,  we can use binary search to find the answer.

class Solution:
    def arrangeCoins(self, n: int) -> int:
        
        # the possible result range = [left, right)
        left, right = 1, n + 1
        
        while left < right:
            mid = left + (right - left) // 2
            
            # total coions = mid * (mid + 1) / 2
            if mid *(mid+1)//2 <= n:
                left = mid + 1
            else:
                right = mid 
        
        return left - 1

[LeetCode] 430. Flatten a Multilevel Doubly Linked List

 Problem : https://leetcode.com/problems/flatten-a-multilevel-doubly-linked-list/

 Use stack to mimic DFS

"""
# Definition for a Node.
class Node:
    def __init__(self, val, prev, next, child):
        self.val = val
        self.prev = prev
        self.next = next
        self.child = child
"""

class Solution:
    def flatten(self, head: 'Node') -> 'Node':
        if not head: return None
        
        dummy = Node()
        p = dummy
        
        stack = [head]
        
        while stack:
            h = stack.pop()
            
            while h:
                p.next = h
                h.prev = p
                p = p.next
                    
                if h.child:
                    if h.next:
                        stack.append(h.next)
                    
                    tmp = h.child
                    h.child = None
                    h = tmp
                else:
                    h = h.next
                
        
        dummy.next.prev = None
        return dummy.next

[LeetCode] 1636. Sort Array by Increasing Frequency

 Problem : https://leetcode.com/problems/sort-array-by-increasing-frequency/

This is a bucket sort problem. Firstly put numbers with same frequency into same bucket. Then reverse sort numbers in the same bucket.

class Solution:
    def frequencySort(self, nums: List[int]) -> List[int]:
        bucket = defaultdict(list)
        
        for n, c in Counter(nums).items():
            bucket[c].append(n) 
            
        result = []
        
        for c in range(101):
            for n in sorted(bucket[c], reverse=True): 
                result += [n] * c
        
        return result

[LeetCode] 828. Count Unique Characters of All Substrings of a Given String

 Problem : https://leetcode.com/problems/count-unique-characters-of-all-substrings-of-a-given-string/

Instead of counting substrings, count the contribution of each unique character.

class Solution:
    def uniqueLetterString(self, s: str) -> int:
        N = len(s)
        
        seen = defaultdict(lambda: -1)
        left = [0] * N   # the left side window in which the ith character is unique
        
        for i in range(N):
            left[i] = seen[s[i]]
            seen[s[i]] = i
        
        seen = defaultdict(lambda: N)
        right = [0] * N  # the right side window in which the ith character is unique
        
        for i in reversed(range(N)):
            right[i] = seen[s[i]]
            seen[s[i]] = i
        
        
        result = 0
        
        for i in range(N):
            # ith character can be unique in (left window size) * (right window size) substrings. 
            result += (i - left[i]) * (right[i] -i)
        
        return result
        

[LeetCode] 1167. Minimum Cost to Connect Sticks

 Problem : https://leetcode.com/problems/minimum-cost-to-connect-sticks/

Greedily connect the 2 shortest sticks in each round. Use heap to find the 2 shortest sticks.

class Solution:
    def connectSticks(self, sticks: List[int]) -> int:
        result = 0
        
        heapq.heapify(sticks)
        
        while len(sticks) > 1:
            a = heapq.heappop(sticks)
            b = heapq.heappop(sticks)
            c = a + b
            result += c
            heapq.heappush(sticks, c)
        
        return result

[LeetCode] 1710. Maximum Units on a Truck

 Problem : https://leetcode.com/problems/maximum-units-on-a-truck/

Greedily take the largest boxes first. Use heap to avoid sort all boxes.

class Solution:
    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:
        heap = [(-m, -n) for n, m in boxTypes]
        heapq.heapify(heap)
        
        result = 0
        
        while truckSize and heap:
            m, n = heapq.heappop(heap)
            m, n = -m, -n
            
            taken = min(truckSize, n)
            result += m * taken
            
            truckSize -= taken
            
        return result

[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())

[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

[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)

[LeetCode] 269. Alien Dictionary

 Problem : https://leetcode.com/problems/alien-dictionary/

Use topological sort to find order of letters.

class Solution:
    def alienOrder(self, words: List[str]) -> str:
        graph = defaultdict(list)
        indegree = defaultdict(int)
        
        for i in range(1, len(words)):
            for a, b in zip(words[i-1], words[i]):        
                if a != b:
                    graph[a].append(b)
                    indegree[b] += 1
                    break
            else:
                if len(words[i-1]) > len(words[i]):
                    return ''
        
        letters = set([l for w in words for l in w])
        queue = deque([l for l in letters if indegree[l] == 0])
                    
        result = []
        
        while queue:
            for _ in range(len(queue)):
                a = queue.popleft()
                result.append(a)
                
                for b in graph[a]:
                    indegree[b] -= 1
                    if indegree[b] == 0:
                        queue.append(b)
        
        # result is valid if all letters have be resolved.
        return ''.join(result) if len(result) == len(letters) else ""

Edited on 07/22/2021. Update for a shorter solution.