[LeetCode] 334. Increasing Triplet Subsequence

Problem : https://leetcode.com/problems/increasing-triplet-subsequence/

Use 2 caches to save the minimal number from left and the maximal number from right of each position.

Return true when minimal_from_left < nums[i] < maximal_from_right.

Time Complexity = O ( N )

Space Complexity = O ( 2 * N )

class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        if len(nums) < 3:
            return False
        
        mi = [0] * len(nums)
        mx = [0] * len(nums)
        
        mi_so_far = nums[0]
        for i in range(len(nums)):
            mi_so_far = min(mi_so_far, nums[i])
            mi[i] = mi_so_far
        
        mx_so_far = nums[-1]
        for i in reversed(range(len(nums))):
            mx_so_far = max(mx_so_far, nums[i])
            mx[i] = mx_so_far
        
        for i in range(len(nums)):
            if mi[i] < nums[i] < mx[i]:
                return True
        
        return False

Space Complexity O(1) Solution:

Use 2 pointers m1, m2 to save number with smaller value.

It finds the increasing triplet when find a number larger than both m1 and m2.

 
class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        if len(nums) < 3:
            return False
        
        m1 = m2 = 2 ** 31 - 1 #MAX_INT
        
        for n in nums:
            if m1 >= n : 
                m1 = n
            elif m2 >= n :
                # find m2 > m1
                m2 = n
            else:
                # find m3 > m2 > m1
                return True
        
        return False

[LeetCode] 332. Reconstruct Itinerary

 Problem : https://leetcode.com/problems/reconstruct-itinerary/

Consider each city is a vertex in a directed graph, then every ticket is an edge between 2 vertices.

Use one hash table to track all available tickets. ( Notice : There could be duplicated tickets between 2 cities )

Then use DFS to find the possible path between city "JFK" to the ending city.

DFS ends when number of city = total number of tickets  + 1

class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        graph = defaultdict(list)
        allTickets = defaultdict(int)
        
        for src, dst in tickets:
            graph[src].append(dst)
            allTickets[(src,dst)] += 1
        
        for src in graph.keys():
            graph[src].sort()
        
        
        def dfs(src, path):
            if len(path) == len(tickets) + 1:
                return path
            
            for dst in graph[src]:
                if allTickets[(src,dst)] > 0:
                    allTickets[(src,dst)] -= 1
                    
                    tmp = dfs(dst, path + [dst])
                    if tmp:
                        return tmp
                    
                    allTickets[(src,dst)] += 1
                    
            return None
        
    
        return dfs("JFK", ["JFK"])

[LeetCode] 331. Verify Preorder Serialization of a Binary Tree

 Problem : https://leetcode.com/problems/verify-preorder-serialization-of-a-binary-tree/

Re-create node list by splitting the input string with comma.

Then iterate the node list with pre-order traversal process.

Validate the tree node during traversal.

class Solution:
    def isValidSerialization(self, preorder: str) -> bool:
        nodes = preorder.split(',')
        
        if not nodes : return True
        
        def helper(i):
            if i >= len(nodes):
                return (i, False)
            
            if nodes[i] == '#':
                return (i, True)
            
            i, result = helper(i+1)
            if not result:
                return (i, False)
            
            i, result = helper(i+1)
            if not result:
                return (i, False)
            
            return (i, True)
        
        i, result = helper(0)
        
        return i == len(nodes) - 1 and result

[LeetCode] 329. Longest Increasing Path in a Matrix

 Problem : https://leetcode.com/problems/longest-increasing-path-in-a-matrix/

class Solution:
    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
        ROW = len(matrix)
        COLUMN = len(matrix[0])
        
        diff = ((0,1), (0,-1), (1,0), (-1,0))
        
        @cache
        def helper(y, x):
            """
            Longest increasing path starts from matrix[y][x]
            """
            result = 1
            for dx, dy in diff:
                nx = x + dx
                ny = y + dy
                if 0 <= nx < COLUMN and 0 <= ny < ROW and matrix[y][x] < matrix[ny][nx]:
                    # increasing sequence can only be built with one direction
                    # no need to mark the visited positions
                    result = max(result, 1 + helper(ny, nx))
            
            return result
        
        result = 1
        for y in range(ROW):
            for x in range(COLUMN):
                result = max(result, helper(y,x))
        return result

Edited on 04/10/2021. Use @cache annotation.

[LeetCode] 328. Odd Even Linked List

 Problem : https://leetcode.com/problems/odd-even-linked-list/

Use dummy list to save odd and even node separately:

/**
 * 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 oddEvenList(ListNode head) {
        ListNode odd = new ListNode();
        ListNode even = new ListNode();
        
        ListNode p = head;
        ListNode po = odd;
        ListNode pe = even;
        
        int count = 1;
        
        while (p != null) {
            if (count++ % 2 == 1) {
                po.next = p;
                po = po.next;
            } else {
                pe.next = p;
                pe = pe.next;
            }
            
            p = p.next;
        }
        
        po.next = even.next;
        pe.next = null;
        
        return odd.next;
    }
}

Edited on 12/01/2021. Replaced with iterative solution.

[LeetCode] 327. Count of Range Sum

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

Time Complexity = O ( N ** 2 ). Time Limit Exceeded.

class Solution:
    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:
        N = len(nums)
        
        sums = [0] * (N+1)
        
        for i in range(N):
            sums[i+1] = sums[i] + nums[i]
        
        result = 0
        for i in range(N+1):
            for j in range(i+1, N+1):
                if lower <= sums[j] - sums[i] <= upper:
                    result += 1
        
        return result

Count and merge sort solution:

class Solution:
    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:
        
        def countAndMergeSort(sums, start, end):
            if end - start <= 1: return 0
            mid = start + (end - start) // 2
            
            count = countAndMergeSort(sums, start, mid) + countAndMergeSort(sums, mid, end)
            
            j = k = t = mid
            cache = [0] * (end - start)
            r = 0
            
            for i in range(start, mid):
                while k < end and sums[k] - sums[i] < lower: 
                    k += 1
                while j < end and sums[j] - sums[i] <= upper: 
                    j += 1
                while t < end and sums[t] < sums[i]:
                    cache[r] = sums[t]
                    r += 1
                    t += 1
    
                cache[r] = sums[i]
                r += 1
            
                count += j - k
            
            r = 0
            for i in range(start, t):
                sums[i] = cache[r]
                r += 1
            
            return count
            
        
        
        
        N = len(nums)
        
        sums = [0] * (N+1)    
        for i in range(N):
            sums[i+1] = sums[i] + nums[i]
        
    
        return countAndMergeSort(sums, 0, len(sums))
                
       

[LeetCode] 326. Power of Three

 Problem : https://leetcode.com/problems/power-of-three/

A naive solution:

class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        if n <= 0:
            return False
        
        if n == 1:
            return True
        
        return n % 3 == 0 and self.isPowerOfThree(n // 3)

A math solution:

class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        return n > 0 and 3 ** (math.log2(n) // math.log2(3)) == n

Edited on 05/04/2021. Update the math solution.

[LeetCode] 324. Wiggle Sort II

 Problem : https://leetcode.com/problems/wiggle-sort-ii/

class Solution:
    def wiggleSort(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        
        tmp = sorted(nums)
        N = len(tmp)
        
        i, j = ((N + 1) // 2) - 1, len(tmp) - 1
        k = 0
        
        while k < N:
            nums[k] = tmp[i]
            k += 1
            i -= 1
            
            if k == len(tmp):
                break
                
            nums[k] = tmp[j]
            k += 1
            j -= 1

[LeetCode] 322. Coin Change

Problem : https://leetcode.com/problems/coin-change/

Time Complexity = O ( M * N ),   M = amount,  N = len(coins).

Top-down Solution :

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        
        MAX_INT = 2 ** 31 - 1
        N = len(coins)
        coins.sort()
        
        @lru_cache(maxsize = None)
        def helper(amount):
            """
            Fewest number of coins needed
            to make up this amount.
            """
            if amount == 0:
                return 0
            
            result = MAX_INT
            
            for i in range(N):
                if coins[i] > amount:
                    break
                
                tmp = helper(amount - coins[i])
                if tmp != -1:
                    result = min(result, tmp + 1)
            
            return result if result != MAX_INT else -1
        
        
        return helper(amount)

Bottom-up Solution:

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        # dp[n] = Fewest number of coins needed to make up amount n
        dp = [amount+1] * (amount + 1)
        dp[0] = 0
        
        coins.sort()
        
        for n in range(1, amount+1):
            for coin in coins:
                if coin > n:
                    break
                
                dp[n] = min(dp[n], dp[n-coin] + 1)
        
        return dp[-1] if dp[-1] != amount + 1 else -1

[LeetCode] 321. Create Maximum Number

 Problem : https://leetcode.com/problems/create-maximum-number/

class Solution:
    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:
        
        def monotoneDecreasingSequence(nums, size):
            if size <= 0: return []
            
            dropCount = len(nums) - size
            
            result = []
            
            for n in nums:
                while result and result[-1] < n and dropCount > 0:
                    result.pop()
                    dropCount -= 1
                    
                result.append(n)
            
            return result[:size]
    
    
        def merge(n1, n2):
            i = j = 0
            result = []
            while i < len(n1) or j < len(n2):
                if i < len(n1) and j < len(n2):
                    # important! compare the rest numbers in lexical 
                    if n1[i:] > n2[j:]:
                        result.append(n1[i])
                        i += 1
                    else:
                        result.append(n2[j])
                        j += 1
                elif i < len(n1):
                    result.append(n1[i])
                    i += 1
                else:
                    result.append(n2[j])
                    j += 1
            
            return result
        
        result = []
        for i in range(max(0, k - len(nums2)), min(k, len(nums1)) +1):
            mds1 = monotoneDecreasingSequence(nums1, i)
            mds2 = monotoneDecreasingSequence(nums2, k - i)
            merged = merge(mds1, mds2)
            
            result = max(result, merged)
        
        return result

[LeetCode] 319. Bulb Switcher

Problem : https://leetcode.com/problems/bulb-switcher/

A naive solution ( Time Limit Exceeded ).  Use bits to represent bulbs.

class Solution:
    def bulbSwitch(self, n: int) -> int:
        if n <= 0:
            return 0
        
        # turn on all bulbs
        bits = [0xFFFFFFFF] * (n // 32 + 1)
        
        for i in range(1, n):
            for j in range(i, n, i+1):
                # toggle bulbs
                bits[j//32] ^= 1 << (j%32)
        
        # count "ON" bulbs
        result = 0
        for i in range(n):
            if bits[i//32] & (1 << (i%32)):
                result += 1
        
        return result

Math solution:

Since a bulb is "OFF" initially,  a bulb ends up with "ON" state if it is switched an odd number of times.

Bulb X is switched in round Y if and only if  Y divides X ( X % Y == 0 ). 

So bulb X ends up with "ON" if and only if it has odd number of divisor.

Divisors come in pairs.  When X = 36, its divisors are (1, 36), (2, 18), (3,12), (4,9), (6,6)

So Bulb 36 will be toggled in round 1, 2, 3, 4, 6, 9, 12, 18, 36.  So Bulb 36 will be "ON" in the end.

So only square numbers have odd number of divisors.

The problem equals to count the square number between 1 to n 

class Solution:
    def bulbSwitch(self, n: int) -> int:
        result = 1
        
        while result * result <= n:
            result += 1
        
        return result - 1

[LeetCode] 318. Maximum Product of Word Lengths

 Problem : https://leetcode.com/problems/maximum-product-of-word-lengths/

Calculate hash key base on the letters.  Then wordA and wordB have common letter if keyA & keyB != 0

Time Complexity = O ( N ** 2 )

class Solution {
    public int maxProduct(String[] words) {
        final int[] keys = Arrays.stream(words)
            .mapToInt(this::keyOf)
            .toArray();
        
        return IntStream.range(0, words.length)
            .map(i -> maxProductStartsWithWord(i, words, keys))
            .max()
            .orElse(0);
    }
    
    int maxProductStartsWithWord(int i, String[] words, int[] keys) {
        return IntStream.range(i+1, words.length)
                    .filter(j -> (keys[i] & keys[j]) == 0)
                    .map(j -> words[i].length() * words[j].length())
                    .max()
                    .orElse(0);
    }
    
    int keyOf(String word) {
        return word.chars()
            .reduce(0, (key, w) -> key | (1 << (w - 'a')));
    }
}

Edited on 05/31/2022. Replace with Java functional programming style solution.

[LeetCode] 316. Remove Duplicate Letters

 Problem : https://leetcode.com/problems/remove-duplicate-letters/

To form the smallest string in lexicographical order, we need to put the remaining smallest letters in front.

Time Complexity = O ( N )

class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        seen = {}
        used = defaultdict(bool)
        
        # remember the last position the letter be seen
        for i, w in enumerate(s):
            seen[w] = i
        
        result = []
        
        for i, w in enumerate(s):
            if used[w]:
                continue
            
            # replace the selected letter
            # if the letter is larger than current one
            # and we still have this letter in the back
            while result and ord(result[-1]) > ord(w) and seen[result[-1]] > i:
                used[result[-1]] = False
                result.pop()
                
            result.append(w)
            used[w] = True
        
        return ''.join(result)

[LeetCode] 315. Count of Smaller Numbers After Self

 Problem : https://leetcode.com/problems/count-of-smaller-numbers-after-self/

The original array is unsorted. Iterate the input array from the rear and use insert sort to create a sorted sequence.  The insert position indicates the number of smaller elements.

Time Complexity = O ( N * Log N  + N * N ).   Inserting number to array is O(N) time complexity operation.

class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]: 
        def lowerBound(n, dp):
            """
            the first poistion on the left where dp[i] <= n
            """
            left, right = 0, len(dp)
            
            while left < right:
                mid = left + (right - left) // 2
                
                if dp[mid] == n:
                    right = mid
                elif dp[mid] < n:
                    left = mid + 1
                elif dp[mid] > n:
                    right = mid
            
            return right
        
        result = [0] * len(nums)
        dp = []
        
        for i in reversed(range(len(nums))):
            n = nums[i]
            # insert sort
            j = lowerBound(n, dp)
            dp.insert(j, n)
            
            result[i] = j
            
        return result

Use Python build-in lib:

class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        dp = []
        result = [0] * len(nums)
        
        for i in reversed(range(len(nums))):
            
            lowerBound = bisect.bisect_left(dp, nums[i])
            
            result[i] = lowerBound
            
            bisect.insort_left(dp, nums[i])
        
        return result

Use segment tree:

class SegmentTree:
    def __init__(self, m):
        # M = number of leafs of the segement tree
        self.M = m
        
        # Because segement tree is a completed binary tree.
        # If number of leafs = M, then number of internal nodes = M - 1.
        # Because tree[0] will not be used, the total number of nodes = 2 * M
        self.tree = [0] * (2 * self.M)
        
    def update(self, n, delta):
        """
        update counter of number on index n
        """
        
        # number n leaf node index = n + M
        n += self.M
        self.tree[n] += delta
        
        n //= 2
        while n > 0:
            # left child node index = 2 * n
            # right child node index = 2 * n
            self.tree[n] = self.tree[2*n] + self.tree[2*n+1]
            n //= 2
    
    def query(self, left, right):
        """
        query accumulative count between range [left, right).
        the 'right' is excluded.
        """
        
        result = 0
        
        left += self.M
        right += self.M
        
        while left < right:
            if left & 1 == 1:
                # on left side, the left child node is not in the needed range.
                result += self.tree[left]
                left += 1
            
            left //= 2
            
            if right & 1 == 1:
                # on right side, the right child node is not in the needed range
                right -= 1
                result += self.tree[right]
            
            right //= 2
        
        return result

class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        if not nums: return []
        
        mi = min(nums)
        mx = max(nums) + 1
        m = mx - mi + 1
        segmentTree = SegmentTree(m)
        
        # query in segement tree for number of smaller elements to the right of nums[i]
        result = [0] * len(nums)
        for i in reversed(range(len(nums))):
            n = nums[i] - mi
            
            result[i] = segmentTree.query(0, n)
            segmentTree.update(n, 1)
        
        return result

Use fenwick tree:

class FenwickTree:
    def __init__(self, m):
        self.tree = [0] * m
    
    def update(self, n, delta):
        while n < len(self.tree):
            self.tree[n] += delta
            n += self.lowbit(n)
    
    def query(self, n):
        result = 0
        
        while n > 0 :
            result += self.tree[n]
            n -= self.lowbit(n)
        
        return result
            
    
    def lowbit(self, n):
        return n & (~(n-1))
        
class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        if not nums: return []
        
        mi = min(nums)
        mx = max(nums) + 1
        m = mx - mi + 1
        
        fenwickTree = FenwickTree(m)
        
        result = [0] * len(nums)
        
        for i in reversed(range(len(nums))):
            # fenwick tree node index starts with 1
            n = nums[i] - mi + 1
            
            result[i] = fenwickTree.query(n-1)
            fenwickTree.update(n, 1)
        
        return result

Use merge sort approach.

Split the nums array into left and right parts.

Sort the right part first, then for each number on the left part, use binary-search to find count of number less than it. (lower-bound)

class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        if not nums: return []
        
        result = [0] * len(nums)
        
        def mergeSort(left, right):
            if left + 1 == right: 
                return 

            mid = left + (right - left) // 2

            # sort right side
            mergeSort(mid, right)

            # for each number on left side, find
            # how many number is smaller than it on right side.
            for i in range(left, mid):
                lowerBound = bisect.bisect_left(nums, nums[i], mid, right)
                # count of smaller numbers = lowerBound - mid
                result[i] += lowerBound - mid
            
            # sort left side
            mergeSort(left, mid)
            
            # merge the sorted left and right side
            tmp = []
            i = left
            j = mid

            while i < mid and j < right:
                if nums[i] < nums[j]:
                    tmp.append(nums[i])
                    i += 1
                else:
                    tmp.append(nums[j])
                    j += 1

            while i < mid:
                tmp.append(nums[i])
                i += 1

            while j < right:
                tmp.append(nums[j])
                j += 1

            for i in range(right - left):
                nums[left+i] = tmp[i]
        
        # merge sort starts
        mergeSort(0, len(nums))
        
        return result

[LeetCode] 313. Super Ugly Number

Problem : https://leetcode.com/problems/super-ugly-number/

Ugly Number A = Ugly Number B * Prime Number

Consider each prime number is assigned to a list. Then the problem becomes merge multiple ugly number list. We need to generate ugly number on each list on the fly.

class Solution:
    def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:
        idx = [0] * len(primes)
        dp = [2**31 - 1] * n
        dp[0] = 1
        
        for i in range(1, n):
            # next ugly number = the minimal number generated by one prime
            # multiple the previous ulgy number
            for j, p in enumerate(primes):
                dp[i] = min(dp[i], p * dp[idx[j]])
                
            for j, p in enumerate(primes):
                # there could be multiple primes
                # generate current minimal number
                # increase idx for all of them
                if dp[i] ==  p * dp[idx[j]]:
                    idx[j] += 1
       
        return dp[-1]

[LeetCode] 312. Burst Ballons

 Problem : https://leetcode.com/problems/burst-balloons/

Time Complexity = O ( N ** 3 ) 

class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        nums = [1] + nums + [1]
        
        @lru_cache(maxsize = None)
        def dp(left, right):
            """
            maximumal coins can get for section section(left : right)
            left and right is excluded from this section
            """
            
            if left + 1 == right:
                # not include left and right
                return 0
            
            result = 0
            for i in range(left+1, right):
                # Balllon list = nums[left] , section(left, i), nums[i], section(i, right), nums[right]
                # tmpResult = nums[left] * nums[i] * nums[right] + max coins of section(left,i) + max coins of section(i, right)
                tmp = nums[left] * nums[i] * nums[right]
                tmp += dp(left, i)
                tmp += dp(i, right)
                result = max(result,  tmp)
            
            return result
        
        
        return dp(0, len(nums) - 1)

[LeetCode] 310. Minimum Height Trees

 Problem : https://leetcode.com/problems/minimum-height-trees/

The entire process is like peeling an onion.  Keep removing vectors only has 1 edge until the graph has less than 2 vectors left. Return the remaining vectors as the root of MHTs.

class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {   
        int[] degree = new int[n];
        Map<Integer, List<Integer>> graph = new HashMap();
        
        // construct the graph
        for (int i = 0; i < edges.length; i++) {
            int a = edges[i][0];
            int b = edges[i][1];
            
            if (!graph.containsKey(a)) {
                graph.put(a, new ArrayList<Integer>());
            }
            
            if (!graph.containsKey(b)) {
                graph.put(b, new ArrayList<Integer>());
            }
            
            graph.get(a).add(b);
            graph.get(b).add(a);
            
            degree[a] += 1;
            degree[b] += 1;
        }
        
        // start to peel the onion
        Queue<Integer> queue = new LinkedList();
        boolean[] deleted = new boolean[n];
        int remains = n;
        
        for (int i = 0; i < n; i++) {
            // put all nodes on outline to the queue
            if (degree[i] <= 1) {
                queue.offer(i);
            }
        }
        
        // peel the onion until less than 2 nodes are left
        // a MHT can have 2 possible roots in maximum
        while (remains > 2) {
            int size = queue.size();
            // use for-loop to ensure peel all nodes on current layer
            for (int i = 0; i < size; i++) {
                // peel the node off the tree
                int a = queue.poll();
                deleted[a] = true;
                degree[a] -= 1;
                remains -= 1;

                for (int b : graph.get(a)) {
                    if (deleted[b]) {
                        continue;
                    }

                    // put its peer to queue if the peer node is on the next layer
                    degree[b] -= 1;
                    if (degree[b] == 1) {
                        queue.offer(b);
                    }
                }
            }
        }
        
        // nodes on the last layer are MHT's root 
        return new ArrayList<Integer>(queue);
    }
}

Edited on 12/16/2021. Replace with Java solution.

[LeetCode] 309. Best Time to Buy and Sell Stock with Cooldown

 Problem : https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/

Each day has either 3 state :  Buy, Sell, CoolDown

On day i:

If it is in "buy" state, then it either buy stock on the last day, or it buy stock on day i ( cool down on last day ) .

If it is in "sell" state, then it either sell stock on the last day, or it sell stock on day i.

If it is in "cooldown" state, then it either cool down on last day, or it sell stock on last day.

Helper(i, state) returns the maximum profit on day i  in  x state.

To get the maximum profit on the last day,  it returns the profit can be made on the last day in "sell" state.

Top-Down Solution:

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        buy, sell, cooldown = 0, 1, 2
        
        @lru_cache(maxsize = None)
        def helper(i, state):
            if i < 0:
                return 0
            
            if i == 0 and state == sell:  
                return 0
            
            if i == 0 and state == buy:
                return -1 * prices[0]
            
            if i == 0 and state == cooldown:
                return 0
            
            if state == buy:
                # max(buy-on-last-day,  buy-on-day-i)
                return max(helper(i-1, buy), -1 * prices[i] + helper(i-1, cooldown))
            
            if state == sell:
                # max(sell-on-last-day, sell-on-day-i)
                return max(helper(i-1, sell), prices[i] + helper(i-1, buy))
            
            if state == cooldown:
                # max(continue-cool-down, sell-on-last-day)
                return max(helper(i-1, cooldown), helper(i-1, sell)
    
        return helper(len(prices)-1, sell)

Bottom-Up Solution:

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        
        if not prices:
            return 0
        
        buy = [0] * len(prices)
        sell = [0] * len(prices)
        cooldown = [0] * len(prices)
        
        buy[0] = -prices[0]
        
        for i in range(1, len(prices)):
            buy[i] = max(buy[i-1], -1 * prices[i] + cooldown[i-1])
            sell[i] = max(sell[i-1], buy[i-1] + prices[i])
            cooldown[i] = max(cooldown[i-1], sell[i-1]) 
            
        return sell[-1]

[LeetCode] 307. Range Sum Query - Mutable

 Problem : https://leetcode.com/problems/range-sum-query-mutable/

Cache accumulative sum of each element and diffs introduced by each update.

class NumArray:

    def __init__(self, nums: List[int]):
        self.nums = nums
        self.sums = [0] * (len(nums) + 1)
        for i in range(len(nums)):
            self.sums[i+1] = self.sums[i] + self.nums[i]
        
        self.diff = {}
        
    def update(self, i: int, val: int) -> None:
        self.diff[i] = val - self.nums[i]
        
    def sumRange(self, i: int, j: int) -> int:
        result = self.sums[j+1] - self.sums[i]
        
        #print(self.nums, self.diff)
        
        for k in self.diff.keys():
            if i <=  k  <= j :
                result += self.diff[k]
        
        return result
        


# Your NumArray object will be instantiated and called as such:
# obj = NumArray(nums)
# obj.update(i,val)
# param_2 = obj.sumRange(i,j)

[LeetCode] 306. Additive Number

 Problem : https://leetcode.com/problems/additive-number/

Use DFS approach to verify the sequence.

Time Complexity = O ( N ** 3 )

class Solution:
    def isAdditiveNumber(self, num: str) -> bool:
        def dfs(start, pre, target):
            if start == len(num):
                return True
            
            if num[start] == '0':
                if target == 0:
                    return dfs(start + 1, 0, 0)
                else:
                    return False
            
            for i in range(start+1, len(num) + 1):
                if int(num[start:i]) > target:
                    return False
                
                
                if int(num[start:i]) == target:
                    return dfs(i, target, pre + target)
            
            return False
        
        
        for i in range(1, len(num) - 1):
            for j in range(i+1, len(num)):
                if i > 1 and num[0] == '0':
                    break
                
                a = int(num[:i])
                
                if j - i > 1 and num[i] == '0':
                    continue
                    
                b = int(num[i:j])
                if dfs(j, b, a + b):
                    return True
        
        return False

[LeetCode] 304. Range Sum Query 2D - Immutable

 Problem : https://leetcode.com/problems/range-sum-query-2d-immutable/

Calculate accumulative sum in the region row by row.

class NumMatrix:

    def __init__(self, matrix: List[List[int]]):
        self.row = len(matrix)
        self.column = len(matrix[0]) if self.row > 0 else 0
        
        if self.row != 0 and self.column != 0:
            self.nums = [[0] * (self.column + 1) for _ in range(self.row)]
            
            for y in range(self.row):
                for x in range(self.column):
                    self.nums[y][x+1] = self.nums[y][x] + matrix[y][x]
            
        else:
            self.nums = None
        

    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        result = 0
        
        if 0 <= row1 < self.row and 0 <= col1 < self.column and \
           0 <= row2 < self.row and 0 <= col2 < self.column:
            for y in range(row1, row2+1):
                result += self.nums[y][col2+1] - self.nums[y][col1]
        
        
        return result
        
        


# Your NumMatrix object will be instantiated and called as such:
# obj = NumMatrix(matrix)
# param_1 = obj.sumRegion(row1,col1,row2,col2)

Use Binary Index Tree:

class BIT:
    def __init__(self, data):
        self.N = len(data)
        self.bit = [0] * (self.N + 1)
        
        for i in range(self.N):
            self.update(i+1, data[i])
    
    def update(self, index, delta): 
        while index <= self.N:
            self.bit[index] += delta
            index += self.lowbit(index)
    
    def query(self, index):
        sums = 0
        
        while index > 0:
            sums += self.bit[index]
            index -= self.lowbit(index)
        
        return sums
        
    
    def lowbit(self, index):
        return index & (-index)
    

class NumMatrix:

    def __init__(self, matrix: List[List[int]]):
        self.bits = [BIT(row) for row in matrix]
        

    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        sums = 0
        
        for i in range(row1, row2+1):
            sums += self.bits[i].query(col2+1) - self.bits[i].query(col1)
        
        return sums


# Your NumMatrix object will be instantiated and called as such:
# obj = NumMatrix(matrix)
# param_1 = obj.sumRegion(row1,col1,row2,col2)

Edited on 02/27/2021. Use BIT based approach.

[LeetCode] 303. Range Sum Query - Immutable

 Problem : https://leetcode.com/problems/range-sum-query-immutable/

Let  Sums[i] = nums[0] + nums[1] + ...  nums[i - 1],

then SumRange(i, j) = Sums[j+1] - Sums[i]

class NumArray:

    def __init__(self, nums: List[int]):
        self.sums = [0] * (len(nums) + 1)
        
        for i in range(len(nums)):
            self.sums[i+1] = self.sums[i] + nums[i]
        
    def sumRange(self, i: int, j: int) -> int:
        return self.sums[j+1] - self.sums[i]
        


# Your NumArray object will be instantiated and called as such:
# obj = NumArray(nums)
# param_1 = obj.sumRange(i,j)

[LeetCode] 301. Remove Invalid Parentheses

 Problem : https://leetcode.com/problems/remove-invalid-parentheses/

Iterating the input string from left right,  for each bracket, we have 2 options. Either keep this bracket or remove this bracket from the final expression. In the end, check the expression is valid by verify if opening bracket == closing bracket. Use removedCount to track how many bracket be removed from the final expression.  Only save the expression with minimal removal count.

Time Complexity = O ( 2 ** N ).     ( As for each character we can choose either keep or remove it from the final expression. )

class Solution:
    def removeInvalidParentheses(self, s: str) -> List[str]:
        self.result = set()
        self.minRemoved = 2 ** 31 - 1
        
        def helper(index, leftCount, rightCount, expression, removedCount):
            
            if index == len(s):
                if leftCount == rightCount:
                    if removedCount < self.minRemoved:
                        self.result = set([expression])
                        self.minRemoved = removedCount
                    elif removedCount == self.minRemoved:
                        self.result.add(expression)
            else:
                if s[index] not in '()':
                    helper(index + 1, leftCount, rightCount, expression + s[index], removedCount)
                else:
                    # remove this bracket
                    helper(index + 1, leftCount, rightCount, expression, removedCount + 1)
                    
                    # keep this bracket
                    if s[index] == '(':
                        helper(index + 1, leftCount + 1, rightCount, expression + s[index], removedCount)
                    elif rightCount < leftCount:
                        # only keep closing bracket when right < left
                        helper(index + 1, leftCount, rightCount + 1, expression + s[index], removedCount)
        
        
        helper(0, 0, 0, '', 0)
        return self.result

Limited Backtracking:

This algorithm is faster because it only remove the misplaced parentheses.

class Solution:
    def removeInvalidParentheses(self, s: str) -> List[str]:
        misplacedLeft = misplacedRight = 0
        
        # find all misplaced parentheses 
        for i in range(len(s)):
            if s[i] == '(':
                misplacedLeft += 1
            elif s[i] == ')':
                if misplacedLeft > 0:
                    misplacedLeft -= 1
                else:
                    misplacedRight += 1
        
        # note: use hash set to avoid duplicate result
        result = set()
        
        def helper(left, right, leftToRemove, rightToRemove, index, tmp):
            if index == len(s):
                if leftToRemove == 0 and rightToRemove == 0:
                    # tmp is valid because all misplaced parentheses have been removed
                    result.add(tmp)
            else:
                if s[index] == '(':
                    if leftToRemove > 0:
                        # remove one misplaced 'left' parenthesis
                        helper(left, right, leftToRemove - 1, rightToRemove, index + 1, tmp)

                    # keep the 'left' parenthesis
                    # note: increase the 'left' counter
                    helper(left + 1, right, leftToRemove, rightToRemove, index + 1, tmp + '(')
                elif s[index] == ')':
                    if rightToRemove > 0:
                        # remove one misplaced 'right' parenthesis
                        helper(left, right, leftToRemove, rightToRemove - 1, index + 1, tmp)

                    if left > right:
                        # keep the 'right' parenthesis if it can still maintain a valid string
                        # note : increase the 'right' counter
                        helper(left, right + 1, leftToRemove, rightToRemove, index + 1, tmp + ')')
                else:
                    # keep all letters
                    helper(left, right, leftToRemove, rightToRemove, index + 1, tmp + s[index])
        
        helper(0, 0, misplacedLeft, misplacedRight, 0, '')
        return result

[LeetCode] 300. Longest Increasing Subsequence

 Problem : https://leetcode.com/problems/longest-increasing-subsequence/

DP Solution

Let DP[i] = longest increasing sequence end at i, then DP[i] = DP[j] + 1 if Nums[i] > Nums[j]

Time Complexity = O ( N ** 2 )

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        if not nums:
            return 0
        
        N = len(nums)
        dp = [1] * N
        
        for i in range(1, N):
            for j in reversed(range(i)):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i], 1 + dp[j])
        
        return max(dp)

DP + Binary Search Solution

DP is a cache to store the increasing sequence.

Iterate the input array and pick number from left to right to insert into DP.

lowerBound method returns the position of the newly added number should be inserted into DP to maintain an increasing sequence.  Replace existing number if the returned position does not expand DP. Otherwise, append the new number to DP.

The final length of DP is the length of the longest increasing subsequence.  However, DP is not the longest increasing subsequence.

Time Complexity = O ( N * LogN )

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        
        def lowerBound(nums, n):
            """
            return the first position from left where nums[i] <= n
            return 0 if all items in nums > n
            return len(nums) if all items in nums < n
            """
            
            left, right = 0, len(nums)
            
            while left < right:
                mid = left + (right - left) // 2
                
                if nums[mid] == n:
                    right = mid
                elif nums[mid] < n:
                    left = mid + 1
                elif nums[mid] > n:
                    right = mid
                
            return left
        
        
        dp = []
        
        for n in nums:    
            i = lowerBound(dp, n)
            if i == len(dp):
                dp.append(n)
            else:
                dp[i] = n
        
        return len(dp)

Use built-in binary-search lib:

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        dp = []
        
        for n in nums:
            i = bisect.bisect_left(dp, n)
            if i == len(dp):
                dp.append(n)
            else:
                dp[i] = n
        
        return len(dp)

Edited on 02/06/2021. Add implementation with built-in binary search lib.

[LeetCode] 299. Bulls and Cows

 Problem : https://leetcode.com/problems/bulls-and-cows/

An intuitive solution based on hash table.

class Solution:
    def getHint(self, secret: str, guess: str) -> str:
        counterS = Counter(secret)
        
        bulls = 0
        for i, g in enumerate(guess):
            if g == secret[i]:
                bulls += 1
                counterS[g] -= 1
        
        cows = 0
        for i, g in enumerate(guess):
             if g != secret[i] and g in counterS and counterS[g] > 0:
                cows += 1
                counterS[g] -= 1
        
        return "{}A{}B".format(bulls, cows)

[LeetCode] 297. Serialize and Deserialize Binary Tree

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

Use BFS to serialize and deserialize the tree.

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

class Codec:

    def serialize(self, root):
        """Encodes a tree to a single string.
        
        :type root: TreeNode
        :rtype: str
        """
        output = []
        
        queue = deque([root])
        
        while queue:
            tmp = deque()
            
            while queue:
                node = queue.popleft()
                if not node:
                    output.append('#')
                else:
                    output.append(str(node.val))
                    tmp.append(node.left)
                    tmp.append(node.right)
                    
            queue = tmp
        
        return ','.join(output) if output[0] != '#' else ''
        

    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        
        if not data:
            return None
        
        data = data.split(',')
        
        root = TreeNode(int(data[0]))
        i = 1
        
        queue = deque([root])
        
        while i < len(data):
            tmp = deque()
            
            while queue:
                node = queue.popleft()
                
                if data[i] == '#':
                    node.left = None
                else:
                    node.left = TreeNode(int(data[i]))
                    tmp.append(node.left)
                
                i += 1
                
                if data[i] == '#':
                    node.right = None
                else:
                    node.right = TreeNode(int(data[i]))
                    tmp.append(node.right)
                
                i += 1
            
            queue = tmp
        
        return root
                    
        
        

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

[LeetCode] 295. Find Median from Data Stream

 Problem : https://leetcode.com/problems/find-median-from-data-stream/

Use insert sort to keep the data cache in ascending order.

Then median = ( nums[len(nums) // 2 ] + nums[(len(nums) - 1) // 2] ) / 2

Time Complexity = O ( Log N ) +  O ( N ) ≈ O ( N )

class MedianFinder:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.nums = []
        

    def addNum(self, num: int) -> None:
        
        def lowerBoundary(n):
            left, right = 0, len(self.nums)
            
            while left < right:
                mid = left + (right - left) // 2
                
                if self.nums[mid] == n:
                    right = mid
                elif self.nums[mid] < n:
                    left = mid + 1
                elif self.nums[mid] > n:
                    right = mid
            
            return left if left - 1 >= 0 else 0
            
        # insert sort   
        self.nums.insert(lowerBoundary(num), num)
        

    def findMedian(self) -> float:
        
        l = len(self.nums)
        
        return (self.nums[l//2] + self.nums[(l-1)//2]) / 2.0
        


# Your MedianFinder object will be instantiated and called as such:
# obj = MedianFinder()
# obj.addNum(num)
# param_2 = obj.findMedian()

[LeetCode] 292. Nim Game

 Problem : https://leetcode.com/problems/nim-game/

Let player A goes first.  When there is 4 stones,  player A will always lose.  Because no matter how many stone player A removes, player B can always remove the reset stones.

Because player A and B play optimally.  Both of they will try to remove stones and left 4 * N stones to its opponent.  So player A always lost, if total number of stones can be dived by 4.

class Solution:
    def canWinNim(self, n: int) -> bool:
        
        return n % 4 != 0

[LeetCode] 290. Word Pattern

 Problem : https://leetcode.com/problems/word-pattern/

Use 2 hash maps to save the mapping relationship.

class Solution:
    def wordPattern(self, pattern: str, str: str) -> bool:
        word = str.split(' ')
        
        w2p = defaultdict(lambda : '')
        p2w = defaultdict(lambda : '')
        
        if len(word) != len(pattern):
            return False
        
        for i in range(len(pattern)):
            if pattern[i] not in p2w and word[i] not in w2p:
                p2w[pattern[i]] = word[i]
                w2p[word[i]] = pattern[i]
            
            elif p2w[pattern[i]] != word[i] or w2p[word[i]] != pattern[i]:
                return False
        
        
        return True

[LeetCode] 289. Game of Life

 Problem : https://leetcode.com/problems/game-of-life/

Use bit mask to save the next-state on high-order bits.

Time Complexity = O ( M * N )

Space Complexity = O ( 1 )

class Solution:
    def gameOfLife(self, board: List[List[int]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        
        ROW = len(board)
        if ROW == 0: return 
        
        COLUMN = len(board[0])
        if COLUMN == 0: return
        
        def alive(y,x):
            return 0 <= y < ROW and 0 <= x < COLUMN and board[y][x] & 1 == 1
        
        def nextState(y,x):
            aliveCount = 0
            
            for dy in [-1, 0, 1]:
                for dx in [-1, 0, 1]:
                    if dy == 0 and dx == 0:
                        continue
                    
                    if alive(y+dy, x+dx):
                        aliveCount += 1
            
            """
            Any live cell with fewer than two live neighbors dies as if caused by under-population.
            Any live cell with two or three live neighbors lives on to the next generation.
            Any live cell with more than three live neighbors dies, as if by over-population.
            Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.
            """
            
            # dead
            nextState = 0
            
            if board[y][x] == 1:
                if aliveCount < 2:
                    # dead
                    pass
                elif 2 <= aliveCount <= 3:
                    # alive
                    nextState = 1 << 3
                else:
                    # dead
                    pass
            else:
                if aliveCount == 3:
                    # alive
                    nextState = 1 << 3
                else:
                    # dead
                    pass
            
            board[y][x] |= nextState
                    
        
        def normalizeState(y,x):
            board[y][x] = 1 if board[y][x] & (1<<3) else 0
        
        for y in range(ROW):
            for x in range(COLUMN):
                nextState(y, x)
        
        for y in range(ROW):
            for x in range(COLUMN):
                normalizeState(y, x)                

[LeetCode] 287. Find the Duplicate Number

 Problem : https://leetcode.com/problems/find-the-duplicate-number/

Put number n back to its origin position Nums[n-1].

The first number n which Nums[n-1] != n is the duplicate number.

Time Complexity = O ( N )

Space Complexity = O ( 1 )

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        for i in range(len(nums)):
            while nums[i] != i + 1 and nums[nums[i] - 1] != nums[i]:
                tmp = nums[nums[i] - 1]
                nums[nums[i] - 1] = nums[i]
                nums[i] = tmp
        
        for i in range(len(nums)):
            if i + 1 != nums[i]:
                return nums[i]

[LeetCode] 284. Peeking Iterator

 Problem : https://leetcode.com/problems/peeking-iterator/

# Below is the interface for Iterator, which is already defined for you.
#
# class Iterator:
#     def __init__(self, nums):
#         """
#         Initializes an iterator object to the beginning of a list.
#         :type nums: List[int]
#         """
#
#     def hasNext(self):
#         """
#         Returns true if the iteration has more elements.
#         :rtype: bool
#         """
#
#     def next(self):
#         """
#         Returns the next element in the iteration.
#         :rtype: int
#         """

class PeekingIterator:
    def __init__(self, iterator):
        """
        Initialize your data structure here.
        :type iterator: Iterator
        """
        self.iterator = iterator
        self.peeked = None
        

    def peek(self):
        """
        Returns the next element in the iteration without advancing the iterator.
        :rtype: int
        """
        if self.peeked:
            return self.peeked
        
        self.peeked = self.iterator.next()
        return self.peeked
        

    def next(self):
        """
        :rtype: int
        """
        
        if self.peeked:
            tmp = self.peeked
            self.peeked = None
            return tmp
        
        return self.iterator.next()
        

    def hasNext(self):
        """
        :rtype: bool
        """
        
        if self.peeked:
            return True
        
        return self.iterator.hasNext()

# Your PeekingIterator object will be instantiated and called as such:
# iter = PeekingIterator(Iterator(nums))
# while iter.hasNext():
#     val = iter.peek()   # Get the next element but not advance the iterator.
#     iter.next()         # Should return the same value as [val].

[LeetCode] 283. Move Zeroes

 Problem : https://leetcode.com/problems/move-zeroes/

Use 2 pointers approach.  The slow pointer moves only when num != 0. The fast pointer moves every time. 

Time Complexity = O ( N )

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        
        i = j = 0
        
        while j < len(nums):
            if nums[j] != 0:
                nums[i] = nums[j]
                i += 1
            
            j += 1
            
        while i < len(nums):
            nums[i] = 0
            i += 1

Another solution similar to bubble-sort. Time Complexity = O ( N ** 2 )

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        
        i = 0
        N = len(nums)
        
        while i < N:
            if nums[i] != 0:
                i += 1
                continue

            j = i
            while j + 1 < N:
                nums[j], nums[j+1] = nums[j+1], nums[j]
                j += 1
            
            N -= 1

[LeetCode] 282. Expression Add Operators

 Problem : https://leetcode.com/problems/expression-add-operators/

class Solution:
    def addOperators(self, num: str, target: int) -> List[str]:
        result = []
        
        def helper(num, diff, curNum, partial):
            if len(num) == 0 and curNum == target:
                result.append(partial)
                return
            
            for i in range(1, len(num)+1):
                cur = num[:i]
                
                
                if len(cur) > 1 and cur[0] == '0':
                    return
              
                if len(partial) == 0:
                    helper(num = num[i:], diff = int(cur), curNum = int(cur), partial = cur)
                else:
                    # A + B
                    helper(num = num[i:], diff = int(cur), curNum = curNum + int(cur), partial = partial + '+' + cur)
                
                    # A - B
                    helper(num = num[i:], diff = -1 * int(cur), curNum = curNum - int(cur), partial = partial + '-' + cur)
        
                    # A * B
                    helper(num = num[i:], diff = diff * int(cur), curNum = curNum - diff + diff * int(cur), partial = partial + '*' + cur)
                
        helper(num, 0, 0, "")
        
        return result

Instead of saving the diff of previous calculation, we may postpone the process of '+' operator.  The '-' operator can be considered as add a negative number.

class Solution:
    def addOperators(self, num: str, target: int) -> List[str]: 
        result = []
        
        def backtrack(start, preNum, curNum, expr):
            """
            calculate preNum + curNum [operator] tmp
            [operator] = +, -, *
            """
            if start == len(num):
                if preNum + curNum == target:
                    result.append(expr)
                return
            
            tmp = 0
            for i in range(start, len(num)):
                tmp = tmp * 10 + int(num[i])
                
                # *  multiplication is the highest priority operator, we get the result of curNum * tmp right away.
                backtrack(i+1, preNum, curNum * tmp, expr + '*' + num[start:i+1])
                
                # +  addition is a low priority operator, save current partial result and postpone the calculation of + tmp
                backtrack(i+1, curNum + preNum, tmp, expr + '+' + num[start:i+1])
                
                # -  substruction is a low priority operator, save current partial result and postpone the calculation of + (-tmp)
                backtrack(i+1, curNum + preNum, -tmp, expr + '-' + num[start:i+1])
                
                if num[start] == '0':
                	# break to avoid number with leading '0'
                    break
            
        
        tmp = 0
        for i in range(len(num)):
            tmp = tmp * 10 + int(num[i])
            backtrack(i+1, 0, tmp, num[:i+1])
            if num[0] == '0':
                # break to avoid number with leading '0'
                break
        
        return result

Edited on 03/16/2021. An optimized version.

Edited on 09/18/20201. Add more comment to the 2nd solution which postpone the process of '+' operator.