[LeetCode] 122. Best Time to Buy and Sell Stock II

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

Should collect every possible profit

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices) < 2:
            return 0
        
        profit = 0
        buyin = prices[0]
        
        for i in range(1, len(prices)):
            p = prices[i]
            if p > buyin:
                profit += p - buyin
            
            buyin = p
            
        return profit

One liner solution:

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        return sum(b - a for a, b in zip(prices, prices[1:]) if b > a)

Edited on 11/09/2021. Add the one liner solution.

[LeetCode] 121. Best Time to Buy and Sell Stock

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

Maximum profit =  buy at the lowest price and sell at the highest price.

Time Complexity = O ( N )

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        minSoFar = 2 ** 31 - 1
        profit = 0
        
        for p in prices:
            profit = max(profit, p - minSoFar)
            minSoFar = min(minSoFar, p)
        
        return profit

A greedy solution :

Time Complexity = O ( N )

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        localmax, globalmax = 0, 0
        
        for i in range(1, len(prices)):
            localmax = max(localmax + prices[i] - prices[i-1], 0)
            globalmax = max(localmax, globalmax)
        
        return globalmax

Use localmax to save the maximum profit can get with consecutive days.

If localmax <  0, set localmax = 0 to restart.

Use globalmax to save the maximum localmax be found.

DP solution:

On each day, we either hold stock or sell stock.

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        holdStock = -prices[0]
        notHoldStock = 0
        
        for i in range(1, len(prices)):
            # keep holding stock or buy stock
            # don't accumulate profit, since it can only buy once
            holdStock = max(holdStock, -prices[i])
            
            # keep not holding stock or sell stock
            notHoldStock = max(notHoldStock, holdStock + prices[i])
        
              
        # on the last day, we get the maximum profit when not hold any stock
        return notHoldStock

[LeetCode] 120. Triangle

Problem : https://leetcode.com/problems/triangle/

Memorization Solution:

Time Complexity = O ( N ** 2 - 1)   N = Len(triangle)

Space Complexity = O ( N ** 2 - 1)

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        level = len(triangle)
        
        @lru_cache(maxsize = None)
        def path(y, x):
            if y == level - 1:
                return triangle[y][x]
            
            return triangle[y][x] + min(path(y+1,x), path(y+1, x+1))
        
        return path(0,0)

Bottom-to-Top Solution:

Time Complexity = O ( N ** 2 - 1)   N = Len(triangle)

Space Complexity = O ( N )

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        dp = triangle[-1][:]
        
        for i in reversed(range(len(triangle) - 1)):
            for j in range(i+1):
                dp[j] = triangle[i][j] + min(dp[j], dp[j+1])
        
        
        return dp[0]

[LeetCode] 119. Pascal's Triangle II

Problem : https://leetcode.com/problems/pascals-triangle-ii/

Time Complexity = O ( N * N )

class Solution:
    def getRow(self, rowIndex: int) -> List[int]:
        result = [1] * (rowIndex + 1)
        
        for i in range(2, rowIndex+1):
            preceding_number = result[0]
            for j in range(1, i):
                tmp = result[j]
                result[j] = preceding_number + result[j]
                preceding_number = tmp
        
        return result

[LeetCode] 118. Pascal's Triangle

Problem : https://leetcode.com/problems/pascals-triangle/

Calculate current line base on the last line numbers.

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        result = []
        
        if numRows <= 0:
            return result
    
        for i in range(numRows):
            result.append([1] * (i+1))
            
        for i in range(2, numRows):    
            for j in range(1, i):
                result[i][j] = result[i-1][j-1] + result[i-1][j]
            
        return result

[LeetCode] 117. Populating Next Right Pointers in Each Node II

Problem : https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/

Be careful to link to the leftmost node of right sub-trees. 

"""
# Definition for a Node.
class Node:
    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next
"""

class Solution:
    def connect(self, root: 'Node') -> 'Node':
        
        def right_node():
            p = root.next
            
            # find the leftmost node of the right subtrees
            while p:
                if p.left:
                    return p.left
                if p.right:
                    return p.right
                
                p = p.next
                
            return None
        
        if root:
            if root.left:
                if root.right:
                    root.left.next = root.right
                else:
                    root.left.next = right_node()
                
            if root.right:
                root.right.next = right_node()
            
            # should link next level right sub-trees first
            # to guarantee nodes on left sub-tree can always
            # find the leftmost node on right sub-trees
            self.connect(root.right)  
            self.connect(root.left)
        
        return root

[LeetCode] 116. Populating Next Right Pointers in Each Node

Problem : https://leetcode.com/problems/populating-next-right-pointers-in-each-node/

BFS solution :

"""
# Definition for a Node.
class Node:
    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next
"""

class Solution:
    def connect(self, root: 'Node') -> 'Node':
        if not root:
            return None
        
        
        queue = deque([root])
        
        while queue:
            level = deque()
            
            while queue:
                node = queue.popleft()
                
                if node.left:
                    level.append(node.left)
                
                if node.right:
                    level.append(node.right)
            
            for i in range(1, len(level)):
                level[i-1].next = level[i]
                
            queue = level
        
        
        return root

Recursive solution:

/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}
    
    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
*/

class Solution {
    public Node connect(Node root) {
        if (root != null) {
            if (root.left != null) {
                root.left.next = root.right;
            }
        
            if (root.right != null && root.next != null) {
                root.right.next = root.next.left;
            }
        
            connect(root.right); 
            connect(root.left);
        }
        
        return root;
    }
}

Iterative solution:

"""
# Definition for a Node.
class Node:
    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next
"""

class Solution:
    def connect(self, root: 'Node') -> 'Node':
        tmp = root
        while root and root.left:
            nxt = root.left
            
            while root:
                root.left.next = root.right
                root.right.next = root.next.left if root.next else None
                root = root.next
            root = nxt
        
        return tmp

Edited on 12/29/2021. Replace the recursive solution with Java code solution.

[LeetCode] 115. Distinct Subsequences

Problem : https://leetcode.com/problems/distinct-subsequences/

Use helper(i, j) method to calculate number of sequence of S[0:i] equals T[0:j]

j == 0  means target string is empty.  Then return 1 as there always 1 subsequence equals to empty target string;

i == 0 means source string is empty. Then return 0 as cannot find subsequence for non-empty target string.

if S[i-1] ==  T[j-1],  there are 2 options to get target string:

1.  Use S[i-1] to match T[j-1].  Number of sequence = helper(i-1, j-1)

2.  Skip S[i-1].   Number of sequence = helper(i-1, j)

If S[i-1] != T[j-1],  there is only 1 option:

Skip S[i-1].  Number of sequence = helper(i-1, j)

Time Complexity = O ( M * N ),   M = len(S),  N = len(T)

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        
        @cache
        def helper(i, j):
            if i >= len(s) or j >= len(t):
                return 1 if j == len(t) else 0
            
            if s[i] == t[j]:
                return helper(i+1, j+1) + helper(i+1, j)
            
            return helper(i+1, j)
        
        return helper(0, 0)

Bottom-up solution :

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        M = len(s)
        N = len(t)
        
        dp = [[0] * (N+1) for _ in range(M+1)]
        
        for i in range(M):
            dp[i+1][N] = 1 if s[i] == t[N-1] else 0
        
        for i in reversed(range(M)):
            for j in reversed(range(N)):
                if s[i] == t[j]:
                    dp[i][j] = dp[i+1][j+1] + dp[i+1][j]
                else:
                    dp[i][j] = dp[i+1][j]
    
        return dp[0][0]

Edited of 09/19/2021. Add the bottom-up solution.

[LeetCode] 114. Flatten Binary Tree to Linked List

Problem : https://leetcode.com/problems/flatten-binary-tree-to-linked-list/

Flatten left tree and right tree.  Append flattened right tree to flatten left tree.Then attach flattened left tree to current root's right child. Finally set current root's left child as None.

# 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 flatten(self, root: TreeNode) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        
        def helper(node):
            """
            Flatten tree and return the (head, tail) of the flattened tree
            """
            if not node:
                return (None, None)
            # has both left and right children
            if node.left and node.right:
                lh, lt = helper(node.left)
                rh, rt = helper(node.right)
                
                node.right = lh
                node.left = None
              
                lt.right = rh
               
                return (node, rt)
            
            # only has left child
            if node.left:
                lh, lt = helper(node.left)
                
                node.right = lh
                node.left = None
             
                return (node, lt)
            
            # only has right child
            if node.right:
                rh, rt = helper(node.right)
                
                node.right = rh
                node.left = None
               
                return (node, rt)
            
            # no left or right child
            return (node, node)
        
        return helper(root)[0]

[LeetCode] 113. Path Sum II

Problem : https://leetcode.com/problems/path-sum-ii/

Use backtracking approach to collect all valid paths.

# 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 pathSum(self, root: TreeNode, targetSum: int) -> List[List[int]]:    
        def allPaths(node, tmp):
            tmp.append(node.val)
            
            if not node.left and not node.right:
                yield tmp[:]
            else:
                if node.left:
                    yield from allPaths(node.left, tmp)
                if node.right:
                    yield from allPaths(node.right, tmp)
            
            tmp.pop()
        
        return [path for path in allPaths(root, []) if sum(path) == targetSum] if root else []

An iterative solution based on stack

# 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 pathSum(self, root: TreeNode, targetSum: int) -> List[List[int]]:
        if not root: return []
        result = []
        
        stack = [(root, [root.val])]
        
        while stack:
            node, path = stack.pop()
           
            if not node.left and not node.right:
                if sum(path) == targetSum:
                    result.append(path)
            else:
                if node.right:
                    stack.append((node.right, path + [node.right.val]))
                if node.left:
                    stack.append((node.left, path + [node.left.val]))
        
        return result

Edited on 04/22/2021. Update the DFS solution with 'yield' and 'yield from'.

Edited on 08/04/2021. Small refactor to the DFS solution.

Edited on 08/04/2021. Add the stack based iterative solution.

[LeetCode] 112. Path Sum

Problem : https://leetcode.com/problems/path-sum/

Be careful, the problem statement requires the path must end at leaf node.

Node values and the target value may be negative.

# Definition for a binary tree node.
# 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 hasPathSum(self, root: TreeNode, targetSum: int) -> bool:
        
        def dfs(node, sums):
            if node:
                sums += node.val
                if not node.left and not node.right:
                    yield sums
                else:
                    if node.left: yield from dfs(node.left, sums)
                    if node.right: yield from dfs(node.right, sums)
        
        return any(sums == targetSum for sums in dfs(root, 0))

Edited on 04/22/2021. Update DFS solution by using 'yield' and 'yield from'.

[LeetCode] 111. Minimum Depth of Binary Tree

Problem : https://leetcode.com/problems/minimum-depth-of-binary-tree/

DFS solution:

# 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 minDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        
        if root.left and root.right:
            return min(self.minDepth(root.left), self.minDepth(root.right)) + 1
        
        if root.left:
            return self.minDepth(root.left) + 1
        
        if root.right:
            return self.minDepth(root.right) + 1
        
        return 1

BFS Solution:

# 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 minDepth(self, root: TreeNode) -> int:
        
        level = 0
        queue = deque([root]) if root else deque()
        
        while queue:
            tmp = deque()
            level += 1
            while queue:
                node = queue.popleft()
                
                if not node.left and not node.right:
                    return level
                
                if node.left:
                    tmp.append(node.left)
                
                if node.right:
                    tmp.append(node.right)
            
            queue = tmp
        
        return level

[LeetCode] 110. Balanced Binary Tree

Problem : https://leetcode.com/problems/balanced-binary-tree/

Use memorization to avoid duplicate calculation of depth.

# 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:
    @lru_cache(maxsize = None)
    def depth(self, node):
        if node:
            return 1 + max(self.depth(node.left), self.depth(node.right))
        else:
            return 0
    
    def isBalanced(self, root: TreeNode) -> bool:
        if root:
            return self.isBalanced(root.left) and \
                   self.isBalanced(root.right) and \
                   abs(self.depth(root.left) - self.depth(root.right)) <= 1
        
        return True

[LeetCode] 109. Convert Sorted List to Binary Search Tree

Problem : https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/

Use fast-slow pointer to find mid node of the given linked list.

Then create BST recursively.

class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) return null;

        ListNode mid = breakInMiddle(head);

        return new TreeNode(
            mid.val,
            sortedListToBST(head != mid ? head : null),
            sortedListToBST(mid.next));
    }

    ListNode breakInMiddle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        ListNode pre = null;

        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            pre = slow;
            slow = slow.next;
        }

        if (pre != null) pre.next = null;
        return slow;
    }
}

[LeetCode] 108. Convert Sorted Array to Binary Search Tree

Problem : https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/

Use the middle number as the parent node and recursively build the left and right sub-tree.

# 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 sortedArrayToBST(self, nums: List[int]) -> TreeNode:
        
        def helper(left, right):
            if left >= right:
                return None
            
            mid = left + (right - left) // 2
            return TreeNode(nums[mid], helper(left, mid), helper(mid+1, right))
        
        return helper(0, len(nums))

Edited on 07/26/2021. Tidy the code.

[LeetCode] 107. Binary Tree Level Order Traversal II

Problem : https://leetcode.com/problems/binary-tree-level-order-traversal-ii/

Use BFS traverse the given tree and record the passed node 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 levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        
        # bfs
        queue = deque([root])
        result = []
        
        while queue:
            level = deque()
            tmp = []
            
            while queue:
                node = queue.popleft()
                
                tmp.append(node.val)
                
                if node.left:
                    level.append(node.left)
                    
                if node.right:
                    level.append(node.right)
            
            queue = level
            result.insert(0, tmp)
        
        return result

DFS solution

# 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 levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
        if not root: return []
        
        # dfs
        result = []
        stack = [(root, 0)]
        
        while stack:
            node, level = stack.pop()
            
            if level == len(result):
                result.append([node.val])
            else:
                result[level].append(node.val)
            
            if node.right:
                stack.append((node.right, level+1))
            
            if node.left:
                stack.append((node.left, level+1))
        
        return result[::-1]

Edited on 06/06/2021. Add the DFS solution.

[LeetCode] 106. Construct Binary Tree from Inorder and Postorder Traversal

Problem : https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/

The last number of postorder is the current root node value. Use the root node value to locate numbers belong to the left sub-tree and right sub-tree. Then construct binary tree recursively.

class Solution {
    static int[] memo = new int[6001];

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        for (int i = 0; i < inorder.length; i++) {
            memo[inorder[i]+3000] = i;
        }
        return helper(inorder, 0, inorder.length, postorder, 0, postorder.length);
    }

    TreeNode helper(int[] inorder, int l1, int r1, int[] postorder, int l2, int r2) {
        if (l1 >= r1 || l2 >= r2) {
            return null;
        }

        // find root in inorder
        int pivot = memo[postorder[r2-1] + 3000];
       
        return new TreeNode(
            inorder[pivot],
            helper(inorder, l1, pivot, postorder, l2, l2 + pivot - l1),
            helper(inorder, pivot+1, r1, postorder, l2 + pivot - l1, r2-1));
    }
}

[LeetCode] 105. Construct Binary Tree from Preorder and Inorder Traversal

Problem : https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

The first number of preorder array is the current root. Then use the root number to find the numbers belong to the left sub-tree. And numbers belong to the right sub-tree. Then recursively re-create the tree.

# 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 buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        if not preorder:
            return None
        
        root = TreeNode(preorder[0])
        
        i = 0
        while inorder[i] != preorder[0]:
            i += 1
        
        root.left = self.buildTree(preorder[1:1+i], inorder[:i])
        root.right = self.buildTree(preorder[1+i:], inorder[i+1:])
        
        return root

[LeetCode] 104. Maximum Depth of Binary Tree

Problem : https://leetcode.com/problems/maximum-depth-of-binary-tree/

Calculate depth recursively.

# 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 maxDepth(self, root: TreeNode) -> int:
        if root:
            return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))
        
        return 0

A iterative solution:

# 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 maxDepth(self, root: TreeNode) -> int:
        result = 0
        stack = [(1, root)] if root else []
        
        while stack:
            level, node = stack.pop()
            
            if not node.left and not node.right:
                result = max(result, level)
            else:
                if node.right:
                    stack.append(((level + 1), node.right))
                if node.left:
                    stack.append(((level + 1, node.left)))
        
        return result

Edited on 04/24/2021. Add the iterative solution.

[LeetCode] 103. Binary Tree Zigzag Level Order Traversal

Problem : https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/

Still use BFS approach to traverse the given binary tree. Remember to reverse value order on odd level.

/**
 * 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 List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result = new LinkedList<>();

        Deque<TreeNode> queue = new LinkedList<>();
        if (root != null) queue.offerLast(root);

        int level = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();
            LinkedList<Integer> tmp = new LinkedList<>();

            for (int i = 0; i < size; i++) {
                TreeNode node = queue.pollFirst();
                if (level % 2 == 0) {
                    tmp.offerLast(node.val);
                } else {
                    tmp.offerFirst(node.val);
                }
                if (node.left != null) queue.offerLast(node.left);
                if (node.right != null) queue.offerLast(node.right);
            }

            result.add(tmp);

            level += 1;
        }

        return result;
    }
}

DFS solution:

/**
 * 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 {
    List<List<Integer>> result = new ArrayList<>();

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        dfs(root, 0);
        return result;
    }

    void dfs(TreeNode node, int level) {
        if (node == null) return;

        if (level == result.size()) {
            result.add(new LinkedList<>());
        }

        if (level % 2 == 0) {
            ((LinkedList<Integer>)result.get(level)).offerLast(node.val);
        } else {
            ((LinkedList<Integer>)result.get(level)).offerFirst(node.val);
        }

        dfs(node.left, level + 1);
        dfs(node.right, level + 1);
    }
}

Edited on 06/06/2021. Add the DFS solution

Edited on 02/18/2023. Replace with Java version BFS & DFS solution

[LeetCode] 102. Binary Tree Level Order Traversal

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

Use BFS to traverse the given binary tree.

# 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 levelOrder(self, root: TreeNode) -> List[List[int]]:
        
        if not root:
            return []
        
        result = [] 
        queue = deque([root])
        
        # bfs
        while queue:
            level = deque()
            result.append([])
            
            while queue:
                node = queue.popleft()
                
                result[-1].append(node.val)
                
                if node.left:
                    level.append(node.left)
                    
                if node.right:
                    level.append(node.right)
            
            queue = level
        
        return result

Recursive DFS solution:

# 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 levelOrder(self, root: TreeNode) -> List[List[int]]:
        def dfs(level, node):
            if node:
                yield (level, node.val)
                yield from dfs(level + 1, node.left)
                yield from dfs(level + 1, node.right)
        
        result = []
        
        for level, val in dfs(0, root):
            if level >= len(result):
                result.append([val])
            else:
                result[level].append(val)
        
        return result

Iterative DFS solution:

# 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 levelOrder(self, root: TreeNode) -> List[List[int]]:
        result = []
        
        stack = [(0, root)] if root else []
        
        while stack:
            level, node = stack.pop()
            
            if level >= len(result):
                result.append([node.val])
            else:
                result[level].append(node.val)
        
            if node.right:
                stack.append((level + 1, node.right))
            
            if node.left:
                stack.append((level + 1, node.left))
            
        return result

Edited on 04/21/2021. Add resursive and iterative DFS solution.

[LeetCode] 101. Symmetric Tree

Problem : https://leetcode.com/problems/symmetric-tree/

Compare the given tree and its mirrored tree to check if they are the same.

# 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 isSymmetric(self, root: TreeNode) -> bool:
        
        def compare(lt, rt):
            if not lt or not rt:
                return not lt and not rt
            
            return lt.val == rt.val and \
                   compare(lt.left, rt.right) and \
                   compare(lt.right, rt.left)
        
        return compare(root, root)

Iterative solution:

# 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 isSymmetric(self, root: TreeNode) -> bool:
        
        stack = [(root, root)]
        
        while stack:
            
            n1, n2 = stack.pop()
            
            if not n1 and not n2:
                continue
                
            if not n1 or not n2 or n1.val != n2.val:
                return False
            
            stack.append((n1.right, n2.left))
            stack.append((n1.left, n2.right))
        
        return True

Edited on 04/22/2021. Add iterative solution.

[LeetCode] 100. Same Tree

Problem : https://leetcode.com/problems/same-tree/

Use DFS approach to recursively compare every node on the 2 trees.

Time Complexity = O ( Min( M, N ) ).  

M = total nodes of P tree. N = total nodes of Q tree.

Recursive Solution:

# 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 isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        def preorder(node):
            if not node:
                yield None
            else:
                yield node.val
                yield from preorder(node.left)
                yield from preorder(node.right)
        
        return all(a == b for a, b in zip(preorder(p), preorder(q)))

Iterative Solution:

# 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 isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        stack = [(p, q)]
        
        while stack:
            p, q = stack.pop()
            
            if not p and not q:
                continue
                
            if not q or not p or p.val != q.val:
                return False
            
            stack.append((p.right, q.right))
            stack.append((p.left, q.left))
        
        return True

BFS Solution:

# 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 isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        # bfs
        pq = deque([p])
        qq = deque([q])
        
        while pq and qq:
            ptmp = deque()
            qtmp = deque()
            
            while pq and qq:
                ph = pq.popleft()
                qh = qq.popleft()
                
                if not ph and qh:
                    return False
                
                if ph and not qh:
                    return False
                
                if not ph and not qh:
                    continue
                
                if ph.val != qh.val:
                    return False
                
                ptmp.append(ph.left)
                ptmp.append(ph.right)
                qtmp.append(qh.left)
                qtmp.append(qh.right)
            
            if len(pq) != len(qq):
                return False
            
            pq = ptmp
            qq = qtmp
        
        return len(pq) == len(qq)

Edited on 04/21/2021. Update the recursive solution by using 'yield' and 'yield from'

Edited on 04/21/2021. Update the iterative solution.

Edited on 06/26/2021. Update the recursive solution by using the 'any' function.

[LeetCode] 99. Recover Binary Search Tree

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

O(N) space solution:

1) In-order traverse the tree and put node values in to an array

2) Sort the array

3) In-order traverse the tree and set node values with the sorted array

# 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 recoverTree(self, root: TreeNode) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        
        def inorder_get(node, values):
            if node:
                inorder_get(node.left, values)
                values.append(node.val)
                inorder_get(node.right, values)
        
        def inorder_set(node, values, i):
            if node:
                i = inorder_set(node.left, values, i)
                
                node.val = values[i]
                i += 1
                
                i = inorder_set(node.right, values, i)
            
            return i
        
        values = []
        
        inorder_get(root, values)
        values.sort()
        inorder_set(root, values, 0)

[LeetCode] 98. Validate Binary Search Tree

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

In-order traversing a BST generates an ascending sequence.  Use this BST characteristic to valid the given BST.

Time Complexity = O ( N ).   N = total nodes of the 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 isValidBST(self, root: TreeNode) -> bool:
        
        def inorder(node, pre_val):
            if node:
                result = inorder(node.left, pre_val)
                
                if not result[1]:
                    return (pre_val, False)
                
                pre_val = result[0]
                
                if pre_val != None and pre_val >= node.val:
                    return (pre_val, False)
                
                pre_val = node.val
                
                result = inorder(node.right, pre_val)
                
                if not result[1]:
                    return (pre_val, False)
                    
                return result
            else:
                return (pre_val, True)
            
        
        return inorder(root, None)[1]

For a valid BST, values on left child tree must be in range [-2**31, root.val) and values on right child tree must be in range (root.val, 2**31-1]

Check if values in left / right sub-trees fall into the valid range.

# 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 isValidBST(self, root: TreeNode) -> bool:
        if not root: return True
        
        def inorder(node, mi, mx):
            if node.left:
                if not inorder(node.left, mi, node.val - 1):
                    return False
            
            if mx != None and node.val > mx:
                return False
            
            if mi != None and node.val < mi:
                return False
            
            if node.right:
                return inorder(node.right, node.val + 1, mx)
            
            return True
        
        return inorder(root, None,  None)

[LeetCode] 97. Interleaving String

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

Use DFS to reconstruct the interleaving string. Use memorization to avoid duplicate validation.

Time Complexity = O ( M * N )    M = len(s1),  N = len(s2)

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        
        @lru_cache(maxsize = None)
        def dfs(i, j, k):
            if k >= len(s3):
                return i == len(s1) and j == len(s2)
            
            if i < len(s1) and s3[k] == s1[i]:
                if dfs(i + 1, j, k + 1):
                    return True
            
            if j < len(s2) and s3[k] == s2[j]:
                if dfs(i, j + 1, k + 1):
                    return True
            
            return False
        
        
        return dfs(0, 0, 0)

[LeetCode] 96. Unique Binary Search Trees

Problem : https://leetcode.com/problems/unique-binary-search-trees/

Iterate all valid numbers and use each of them as root. Then calculate the number of valid left / right sub-tree.  Unique BST = Number of Valid Left Sub-Tree * Number Of Valid Right Sub-Tree

class Solution:
    def numTrees(self, n: int) -> int:
        
        @lru_cache(maxsize=None)
        def helper(start, end):
            if start >= end:
                return 1
            
            result = 0
            
            for i in range(start, end + 1):
                lefts = helper(start, i-1)
                rights = helper(i+1, end)
                
                
                result += lefts * rights
                  
            return result
        
        
        return helper(1, n)

Another top-down solution

class Solution:
    def numTrees(self, n: int) -> int:
        
        @cache
        def helper(x):
            if x == 0:
                return 1
            
            if x == 1:
                return 1
            
            result = 0
            
            for i in range(x):
                result += helper(i) * helper(x-i-1)
                
            return result
        
        return helper(n)

Bottom-up solution

class Solution:
    def numTrees(self, n: int) -> int:
        dp = [0] * (n+1)
        
        dp[0] = 1
        
        for i in range(1, n+1):
            for j in range(i):
                dp[i] += dp[j] * dp[i-j-1]

        return dp[n]

Edited on 11/07/2021. Add the bottom-up solution.

[LeetCode] 95. Unique Binary Search Trees II

Problem : https://leetcode.com/problems/unique-binary-search-trees-ii/

In BST,  each node is larger than every nodes in its left sub-tree and smaller than every nodes in its right sub-tree.  We should use every valid integer as root node and create BST recursively.

# 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 generateTrees(self, n: int) -> List[Optional[TreeNode]]:
        
        def helper(left, right):
            if left == right:
                return [TreeNode(val=left)]
            elif left > right:
                return [None]
            else:
                return [TreeNode(val=pivot, left=l, right=r) for pivot in range(left, right+1) for l in helper(left, pivot - 1) for r in helper(pivot+1, right)]

        return helper(1, n)

Edited on 09/02/2021. Update a simpler solution.

[LeetCode] 94. Binary Tree Inorder Traversal

Problem : https://leetcode.com/problems/binary-tree-inorder-traversal/

Recursive Solution:

# 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 inorderTraversal(self, root: TreeNode) -> List[int]:
        def inorder(node):
            if node:
                yield from inorder(node.left)
                yield node.val
                yield from inorder(node.right)
        
        return list(inorder(root))

Iterative Solution:

# 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 inorderTraversal(self, root: TreeNode) -> List[int]:
        
        result = []
        stack = [root] if root else []
        
        while stack:
            node = stack[-1]
            
            if not node.left:
                result.append(node.val)
                stack.pop()
                
                if node.right:
                    stack.append(node.right)
                    node.right = None
            else:
                stack.append(node.left)
                node.left = None
        
        return result

Edited on 04/21/2021. Update recursive solution by using 'yeild' and 'yield from'.

Edited on 04/21/2021. Small refactor to iterative solution.

[LeetCode] 93. Restore IP Addresses

Problem : https://leetcode.com/problems/restore-ip-addresses/

Use backtracking approach. For every digit, it can be either used as a new segment or used to extend the last segment.

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        result = []
        
        def backtracking(i, partial):
            if i == len(s):
                if len(partial) == 4:
                    ip = ".".join(partial)
                    result.append(ip)
                return
            
            # append new segment
            if len(partial) < 4:
                partial.append(s[i])
                backtracking(i+1, partial)
                partial.pop()
         
            # extend last segment
            if partial and partial[-1] != '0' and int(partial[-1] + s[i]) <= 255:
                partial[-1] = partial[-1] + s[i]
                backtracking(i+1, partial)
                partial[-1] = partial[-1][:-1]

        
        backtracking(0, [])
        
        return result

[LeetCode] 92. Reverse Linked List II

Problem : https://leetcode.com/problems/reverse-linked-list-ii/

Not really difficult. Be careful that the index starts from 1.  And it requires to reverse the list in range [m ~ n].

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
        dummy = ListNode()
        p = dummy
              
        def helper(i, node):
            if not node:
                return node
            
            nonlocal p
            
            if i < m:
                # append current node keep list order
                p.next = node
                p = p.next
                return helper(i+1, node.next)
            elif i > n:
                # return rest of the list
                return node
            else:
                # reverse order with postorder traversal
                tail = helper(i+1,node.next)
                p.next = node
                p = p.next
                
                return tail
        
        # append rest of the list
        p.next = helper(1, head)
        
        return dummy.next

An iterative solution:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseBetween(self, head: ListNode, left: int, right: int) -> ListNode:
        dummy1 = ListNode() # the prefix list in original order
        dummy2 = ListNode() # reversed list
        
        p1 = dummy1
        p2 = dummy2
        p3 = None    # end of the reversed list
         
        while right >= 0:
            left -= 1
            right -= 1
            
            if left > 0:
                p1.next = head
                p1 = p1.next
                head = head.next
                continue
                
            if left <= 0 and right >= 0:
                if left == 0:
                    p3 = head
                    
                tmp = head
                head = head.next
                
                tmp.next = p2.next
                p2.next = tmp
                continue
            
        p1.next = p2.next
        p3.next = head
        
        return dummy1.next

[LeetCode] 91. Decode Ways

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

There are 2 ways to decode for each digit.

1. Treat this digit as a letter

2. Combine this digit and its adjacent digit then treat them as a letter

Use cache to memorize decoded ways of each digit

Time Complexity = O ( N )

class Solution:
    def numDecodings(self, s: str) -> int:
        
        @cache
        def helper(start):
            if start == len(s):
                return 1
            
            # '0' cannot be leading digit
            if s[start] == '0':
                return 0
            
            # decode ways when treat s[i] as a letter 
            result = helper(start+1)
            
             # decode ways when treat s[i]s[i+1] as a letter
            if start + 1 < len(s)  and (s[start] == '1' or (s[start] == '2' and s[start+1] <= '6')):
                result += helper(start+2)
            
            return result
        
        return helper(0)
 

The bottom-up solution:

class Solution:
    def numDecodings(self, s: str) -> int:
        dp = defaultdict(int)
        
        dp[0] = 1
        dp[1] = 1 if s[0] != '0' else 0
        
        for i in range(1, len(s)):
            
            if s[i] != '0':
                dp[i+1] = dp[i]
            
            if s[i-1] == '1' or (s[i-1] == '2' and s[i] <= '6'):
                dp[i+1] += dp[i-1]
        
        return dp[len(s)]

Edited on 07/11/2021. Simplify top-down and bottom-up solutions.

[LeetCode] 90. Subsets II

Problem : https://leetcode.com/problems/subsets-ii/

Consider the code is traversing a tree. On each step, the code has 2 options that are pick or not pick number on this position.

Time Complexity =  O ( len(nums) * len(nums) * log (len(nums) )  )

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        result = []
        
        def backtracking(start, partial, maxSize):
            if len(partial) == maxSize:
                result.append(partial)
                return
            
            for i in range(start, len(nums)):
                # value of number[i-1] has been picked
                # skip number[i-1] to avoid duplicate subsets
                if i > start and nums[i] == nums[i-1]:
                    continue
                    
                backtracking(i + 1, partial + [nums[i]], maxSize)
        
        
        for i in range(len(nums)+1):
            backtracking(0, [], i)
            
        
        return result

An iterative solution which uses hashset to filter the duplicates.

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        result = set([()])
        nums.sort()
                
        for i, n in enumerate(nums):
            tmp = result.copy()
            for prefix in tmp:
                result.add(prefix + (n,))
                       
        return result

Edited on 08/03/2021. Add the hashset based iterative solution.

[LeetCode] 89. Gray Code

Problem :  https://leetcode.com/problems/gray-code/

Use DFS approach to find all valid codes.

Time Complexity  =  O ( 2 ** n )

class Solution:
    def grayCode(self, n: int) -> List[int]:
        if n == 0:
            return [0]
        
        result = [0,1]
        memo = set(result)
        
        last = 1
        
        while last != 0:
            num = last
            last = 0
            
            mask = 1
            
            # iterate each bit position to find the next number
            for i in range(n):
                tmp = num ^ (mask << i)
                
                if tmp not in memo:
                    memo.add(tmp)
                    result.append(tmp)
                    last = tmp
                    break
    
        return result

[LeetCode] 88. Merge Sorted Array

Problem : https://leetcode.com/problems/merge-sorted-array/

Since nums1 has enough space left to save nums2, which means  len(nums1) > m + n.

We may use the spare spaces from the rare of nums1 to do merging.

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        
        i, j = m - 1, n - 1
        p = len(nums1) - 1
        
        while i >= 0 and j >= 0:
            # select the larger number to add to the rear of nums1
            if nums1[i] > nums2[j]:
                nums1[p] = nums1[i]
                i -= 1
            else:
                nums1[p] = nums2[j]
                j -= 1
            
            p -= 1
        
        # add rest number of nums1
        while i >= 0:
            nums1[p] = nums1[i]
            p -= 1
            i -= 1
        
        # add rest number of nums2
        while j >= 0:
            nums1[p] = nums2[j]
            p -= 1
            j -= 1
        
        # move the merged list to the head of nums1
        p += 1
        i = 0
        while i < m + n:
            nums1[i] = nums1[p]
            i += 1
            p += 1
        
        # fill the rest spaces with 0
        while i < len(nums1):
            nums1[i] = 0
            i += 1

[LeetCode] 87. Scramble String

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

Each character of the string can be considered as a leaf node of the binary tree.

If S2 is scrambled of S1.  There is S1 = S11 + S12 and S2 = S21 + S22.   S21 is scrambled from S11a and S22 is scrambled from S12.

from collections import Counter

class Solution:
    def isScramble(self, s1: str, s2: str) -> bool:
        if not s1:
            return not s2
        
        if Counter(s1) != Counter(s2):
            return False
        
        if s1 == s2:
            return True
        
        for i in range(1, len(s1)):
            s11, s12 = s1[:i], s1[i:]
            s21, s22 = s2[:i], s2[i:]
            
            if self.isScramble(s11, s21) and self.isScramble(s12, s22):
                return True
            
            # flip s2 and compare to s1 substrings again
            s21, s22 = s2[:(len(s1) - i)], s2[(len(s1) - i):]
            
            if self.isScramble(s11, s22) and self.isScramble(s12, s21):
                return True
                  
        return False

[LeetCode] 86. Partition List

Problem : https://leetcode.com/problems/partition-list/

Create 2 linked lists.  Add node which's value less than x to the first list.  Add node which's value equal or larger than x to the second list. Then append the second linked list to the first linked list.  Finally, return the first linked list as result.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def partition(self, head: ListNode, x: int) -> ListNode:
        less = ListNode(0)
        pless = less
        
        larger = ListNode(0)
        plarger = larger
        
        p = head
        
        while p:
            if p.val < x:
                pless.next = p
                pless = pless.next
            else:
                plarger.next = p
                plarger = plarger.next
            
            p = p.next
        
        pless.next = None
        plarger.next = None
        
        pless.next = larger.next
        
        return less.next
        

[LeetCode] 85. Maximal Rectangle

Problem : https://leetcode.com/problems/maximal-rectangle/

This is an extended problem of 84. Largest Rectangle in Histogram

Scan "1" on each row and convert to histogram bars. Let every row as bottom of a histogram then calculate largest rectangle of each histogram.

class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        
        def largestRectangle(heights):
            """
            find largest rectangle of each histogram
            """
            result = 0
            stack = []
            
            for i in range(len(heights)):
                start = i
                h = heights[i]
                
                while stack and stack[-1][1] > h:
                    index, height = stack.pop()
                    
                    tmp = height * (i - index)
                    result = max(result, tmp)
                    
                    start = index
                
                stack.append((start, h))
            
            while stack:
                index, height = stack.pop()
                
                tmp = height * (len(heights) - index)
                result = max(result, tmp)
            
            return result     
        
        if not matrix:
            return 0
        
        row = len(matrix)
        column = len(matrix[0])
        
        heights = [0] * column
        
        result = 0
    
        for y in range(row):
            for x in range(column):
            	# convert "1" and "0" into bars
                if matrix[y][x] == "1":
                    heights[x] += 1
                else:
                    heights[x] = 0
                
            result = max(result, largestRectangle(heights))
        
        return result

[LeetCode] 84. Largest Rectangle in Histogram

Problem : https://leetcode.com/problems/largest-rectangle-in-histogram/

Solution 1 :

Iterate the input array until encounter a peak number ( number[i] > number[i+1] ), move backward to find the potential largest rectangle.

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
    
    	result = 0
        N = len(heights)
       
        for i in range(N):
            # find peak where heights[i] > heights[i+1]
            if i == N -1 or heights[i] > heights[i+1]:
                minHeight = heights[i]
                # move backward to find potential largest rectangle
                for j in reversed(range(0, i+1)):
                    minHeight = min(minHeight, heights[j])
                    result = max(result, minHeight * (i - j + 1))
                    
        return result

Solution 2 :

Iterate the input array and push current height and its start index to stack if current height higher than top value of stack. Otherwise, pop stack and extend start index of current height to left until top value of stack less than current height.  Calculate the potential largest rectangle size while popping stack.

At last, clear up the stack and calculate rectangle size formed with the bar in stack and the end of histogram.

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        result = 0
        stack = []
        
        for i, h in enumerate(heights):
            start = i
            
            while stack and stack[-1][1] > h:
                index, height = stack.pop()
                result = max(result, height * (i - index))
                
                # extend current short height index to left 
                start = index
                
            stack.append((start, h))
        
        # the remain heights are extended to end of histogram
        while stack:
            index, height = stack.pop()
            result = max(result, height * (len(heights) - index))
        
        return result

[LeetCode] 83. Remove Duplicates from Sorted List

Problem : https://leetcode.com/problems/remove-duplicates-from-sorted-list/

Traverse the input linked list and add node to output linked list if its value is encountered at the first time.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        dummy = None
        p1 = dummy
        p2 = head
        
        while p2:
            if not p1:
                dummy = p2
                p1 = dummy
            elif p1.val != p2.val:
                p1.next = p2
                p1 = p1.next
            
            p2 = p2.next
        
        # end the output linked list
        if p1:
            p1.next = None
        
        return dummy

[LeetCode] 82. Remove Duplicates from Sorted List II

Problem : https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/

Traverse the origin linked list and count the visited numbers.  Then append distinct number to the output linked list.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        
        dummy = ListNode(0)
        p1 = dummy
        
        p2 = head
        count = 1
        
        while p2 and p2.next:
            if p2.val == p2.next.val:
                count += 1
                p2 = p2.next
            else:
                if count == 1:
                    p1.next = p2
                    p1 = p1.next
                
                count = 1
                p2 = p2.next
    
        if p2 and count == 1:
            p1.next = p2
            p1 = p1.next
        
        # end the output linked list
        p1.next = None
        
        return dummy.next

A Sliding-window solution:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        p = head
        q = head
        
        dummy = ListNode()
        n = dummy
        
        while p:
            while q and p.val == q.val:
                q = q.next
            
            if p.next == q:
                n.next = p
                n = n.next
            
            p = q
            
        # end the new list
        n.next = None
            
        return dummy.next

[LeetCode] 81. Search in Rotated Sorted Array II

Problem : https://leetcode.com/problems/search-in-rotated-sorted-array-ii/

When nums[mid] < nums[right], the right part is sorted.

When nums[mid] > nums[right], the left part is sorted.

When nums[mid] == nums[right], shrink the right part.

class Solution:
    def search(self, nums: List[int], target: int) -> bool:
        left, right = 0, len(nums) - 1
        
        while left <= right:
            mid = left + (right - left) // 2
            
            if nums[mid] == target:
                return True
            
            if nums[mid] < nums[right]:
                # right part is sorted
                if  nums[mid] < target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1
            elif nums[mid] > nums[right]:
                # left part is sorted
                
                if nums[left] <= target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            else:
                # nums[mid] == nums[right]
                # bypass current nums[right]
                right -= 1
                    
        return False

[LeetCode] 80. Remove Duplicates from Sorted Array II

Problem : https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/

Uses 2 pointers approach. Pointer j moves 1 step per time. Pointer 'i' moves only when encounter valid character.

Time Complexity : O ( N )

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        i, j = 1, 1
        count = 1
        
        while j < len(nums):
            if nums[j] == nums[j-1]:
                count += 1
                
                if count <= 2:
                    # keep 2 duplicate  in maximum
                    nums[i] = nums[j]
                    i += 1
                    j += 1
                else:
                    # skip nums[j] as there are already two duplicated numbers
                    j += 1
            else:
                count = 1
                nums[i] = nums[j]
                i += 1
                j += 1
        
        return i

A much simpler solution of overwritting unwanted letters.

Because it is a sorted array, we only need to compare if current letter is same to letter on last 2nd postion of the wanted array.

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        i = j = 2
        
        while j < len(nums):
            if nums[i-2] == nums[j]:
                j += 1
            else:
                nums[i] = nums[j]
                i += 1
                j += 1
        
        return i

[LeetCode] 79. Word Search

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

Use DFS to traverse the board.

Temporarily mark the visited cell as '#' to avoid circuit traversal.

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        ROW = len(board)
        COLUMN = len(board[0])
        visited = defaultdict(int)
        
        def dfs(y, x, p):
            if p == len(word):
                return True
            
            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] and board[ny][nx] == word[p]:
                    visited[ny,nx] = True
                    if dfs(ny, nx, p + 1):
                        return True
                    visited[ny, nx] = False
            
            return False
        
        for y in range(ROW):
            for x in range(COLUMN):
                if board[y][x] == word[0]:
                    visited[y,x] = True
                    if dfs(y, x, 1):
                        return True
                    visited[y,x] = False
        
        return False

Edited on 10/07/2021. Refactor the DFS solution.

[LeetCode] 78. Subsets

Problem : https://leetcode.com/problems/subsets/

This looks like a follow-up problem of 77. Combinations

Use the same approach to generate the combinations with max length from 0 to len(nums).

Backtracking Solution:

Time Complexity = O ( N ** 2 * N )

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        result = []
        
        def backtracking(start, partial, maxLen):
            if len(partial) == maxLen:
                result.append(partial)
                
            
            for i in range(start, len(nums)):
                # pick nums[i]
                backtracking(i+1, partial + [nums[i]], maxLen)
                # not pick nums[i]
        
        
        # generate combination with max length from 0 to len(nums)
        for i in range(len(nums) + 1):
            backtracking(0, [], i)
        
        return result

DFS Solution :

Consider the code is traversing a tree. On each node it has 2 options to pick or not pick the number on this node.

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

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        
        result = []
        
        def dfs(start, partial):
            if start == len(nums):
                result.append(partial)
                return
            
            # not pick nums[start]
            dfs(start + 1, partial)
            
            # pick nums[start]
            dfs(start + 1, partial + [nums[start]])
            
        dfs(0, [])
        
        return result

Cascading Solution:

Get new subsets by append current number to the subsets generated by the last step.

Time Complexity = O ( N ** 2 * N )

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        
        result = [[]]
        
        for n in nums:
            for i in range(len(result)):
                # append current number to subsets 
                # generated by last step
                result.append(result[i] + [n])
        
        return result

[LeetCode] 77. Combinations

Problem : https://leetcode.com/problems/combinations/

Equivalent to traverse a tree constructed with number 1 ~ n. On each step the code may chose pick or not pick the number on this step.

Time Complexity : O ( N * (N - 1) .. (N-K) ) 

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        result = []
        
        def backtrack(x, partial):
            if len(partial) == k:
                result.append(partial)
                return
             
            if x <= n:
                # pick x
                backtrack(x+1, partial + [x])
                
                # not pick x
                backtrack(x+1, partial)
            
        backtrack(1, [])
        return result
        

Another backtracking solution:

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        result = []
        
        def backtrack(x, partial):
            if len(partial) == k:
                result.append(partial)
                return
             
            for i in range(x, n+1):
            	# pick number i
                backtrack(i+1, partial + [i])
                # not pick number i
            
        backtrack(1, [])
        return result

BFS solution:

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        if k == 0: return []
        if k == n: return [[i+1 for i in range(n)]]
                   
        result = []
        queue = deque([[i+1] for i in range(n)])
        
        while queue:
            combo = queue.popleft()
            
            if len(combo) == k:
                result.append(combo)
            else:
                for i in range(combo[-1] + 1, n+1):
                    queue.append(combo + [i])
        
        return result

[LeetCode] 76. Minimum Window Substring

Problem : https://leetcode.com/problems/minimum-window-substring/

Use sliding window based approach. Firstly expand window to find the longest substring contains all characters of target string. Then shrink window to find the valid shortest substring.

Time Complexity : O ( S + T ) 

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        counter = Counter(t)
        
        right = 0
        seen = defaultdict(int)
        count = 0
        
        windowStart = -1
        windowSize = 2 ** 31 - 1
        
        for left in range(len(s)):
            while right < len(s) and count < len(counter):
                seen[s[right]] += 1
                
                if seen[s[right]] == counter[s[right]]:
                    count += 1
                
                right += 1
            
            if count == len(counter):
                if windowSize > right - left:
                    windowStart = left
                    windowSize = right - left
            
            seen[s[left]] -= 1
            if seen[s[left]] == counter[s[left]] - 1:
                count -= 1
            
        
        if windowStart == -1: 
            return ""
        
        return s[windowStart:windowStart + windowSize]
                

[LeetCode] 75. Sort Colors

Problem : https://leetcode.com/problems/sort-colors/

Counting sort based solution.

Time Complexity : O ( 2N )

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        
        colors = [0] * 3
        
        for i in nums:
            colors[i] += 1
        
        j = 0
        for color, count in enumerate(colors):
            for i in range(count):
                nums[j + i] = color
                
            j += count

Two pointers based solution.

Have 'red' pointer moves forward from the first number and 'blue' pointer moves backward from the last number. Iterate from the first number.  If number[i] == 0, swap with red. When number[i] == 2, swap with blue.

Time Complexity : O ( N )

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        
        def swap(i, j):
            nums[i], nums[j] = nums[j], nums[i]
        
        red, blue = 0, len(nums) - 1
        i = 0
        
        while i <= blue:
            color = nums[i]
            if color == 0:
                swap(i, red)
                red += 1
                i += 1
            elif color == 2:
                swap(i, blue)
                blue -= 1
                # do not increase i
                # need to check the swapped color is red or not
            else:
            	# no need to swap for white color
                i += 1

[LeetCode] 74. Search a 2D Matrix

Problem : https://leetcode.com/problems/search-a-2d-matrix/

Since the given matrix rows are sorted in ascending order, we just flatten the matrix and use binary search to locate the target number.

Time Complexity : O ( Rows * Columns )

Space Complexity :  O ( 1 )

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        row = len(matrix)
        column = len(matrix[0]) if row > 0 else 0
       
        total = row * column
        
        left, right = 0, total
        
        while left < right:
            mid = left + (right - left) // 2
            
            i = mid // column
            j = mid % column
            
            if matrix[i][j] == target:
                return True
            
            if matrix[i][j] < target:
                left = mid + 1
            else:
                right = mid
        
        return False

[LeetCode] 73. Set Matrix Zeroes

Problem : https://leetcode.com/problems/set-matrix-zeroes/

Allocate extra space to record columns or rows have 0.

Space complexity O ( ROW + COLUMN ) solution. 

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        
        ROW = len(matrix)
        COLUMN = len(matrix[0])
        
        mark = [False] * (ROW + COLUMN)
        
        for y in range(ROW):
            for x in range(COLUMN):
                if matrix[y][x] == 0:
                    mark[y] = True
                    mark[ROW + x] = True
        
        # set zeros 
        for y in range(ROW):
            for x in range(COLUMN):
                if mark[y] or mark[ROW + x]:
                    matrix[y][x] = 0

Edited on 08/13/2021. Simplify the O(ROW + COLUMN) solution.