LeetCode

Array and Hashing

• Contains Duplicate ✅ 2023-06-06
• Valid Anagram ✅ 2023-06-06
• Two Sum ✅ 2023-06-06
• Group Anagrams ✅ 2023-07-28
• Top K Frequent Elements ✅ 2023-07-29
• Product of Array Except Self ✅ 2023-07-29
• Valid Sudoku ✅ 2023-07-29
• Encode and Decode Strings
• Longest Consecutive Sequence ✅ 2023-07-30

Two Pointers

• 3Sum ✅ 2023-07-25
• Valid Palindrome ✅ 2023-08-04
  • Two pointers to compare left and right character
• Container With Most Water ✅ 2023-08-04
  • Two pointers to reduce container width while maintaining highest height

Sliding Window

• Best Time to Buy and Sell Stock ✅ 2023-07-23
• Longest Substring Without Repeating Characters ✅ 2023-08-04
  • Map/Set for checking duplicate
• Longest Repeating Character Replacement ✅ 2023-08-05
  • Keep track of the maximum character count (max_frequency)
  • Substring is valid if r - l + 1 - MaxFrequency <= k
  • result = maxFrequency + k
  • No need to recompute/reduce max_frequency since a smaller value must results in a shorter substring
• Minimum Window Substring ✅ 2023-08-12
  • Hash map to keep track of the characters of target substring
  • Expand right pointer until substring is valid, then expand left pointer until substring is invalid, at the same time updating the result
  • sCount to determine if the substring is valid by increasing sCount only if sMap[s[r]] <= tMap[s[r]], i.e. sCount is the number of characters in sMap that satisfy the requirement in tMap.
  • sCount == tCount can be used to control the while loop for increasing the left pointer, we decrease sCount if it no longer meets the requirement in tMap

Stack

• Valid Parentheses ✅ 2023-07-30
  • Stack and map to pop opening parentheses when they matched
  • Stack would be empty if it is valid
• Min Stack ✅ 2023-07-31
  • Linked list implementation of stack
  • Extra variable to store the minimum value at a specific level
• Evaluate Reverse Polish Notation ✅ 2023-09-02
  • Pop operands when operator is met, push the result back to the stack
• Generate Parentheses ✅ 2023-09-01
  • DFS and maintain the number of available open and close parentheses
  • Recurse if there are available open parentheses or an open parentheses can be closed by an close parentheses, i.e. openCount > closeCount, i.e. openAvailable < closeAvailable
• Daily Temperatures ✅ 2023-09-02
  • Maintain a stack of indices, pop while new temperature is greater than top, i.e. a monotonic decreasing stack in terms of temperature
  • When a higher temperature is met, the required days can be calculated by currentIndex - topIndex

Binary Search

• Binary Search ✅ 2023-08-03
• Search a 2D Matrix ✅ 2023-08-03
  • Binary search on column then row, or mapping indices from 2d to 1d
• Find Minimum In Rotated Sorted Array ✅ 2023-08-05
  • Find the pivot point between the left and right sorted array with binary search
  • nums[mid] > nums.back() if pivot is on the right side
  • nums[mid] <= nums.back() if pivot is on the left side or pivot is nums[mid]
• Search In Rotated Sorted Array ✅ 2023-08-06
  • A good way to visualize this problem would be to draw a dotted plot, this makes differentiating the left and right sorted halves and comparing pointers easier
  • nums[mid] > nums.back() and nums[mid] <= nums.back() also works for checking which sorted halves the middle is at
  • nums[mid] >= nums[left] (in left sorted part)
    • target >= nums[left] && target < nums[mid]
      • search left
    • target < nums[left] || target > nums[mid]
      • search right
  • nums[mid] < nums[left] (in right sorted part)
    • target <= nums[right] && target > nums[mid]
      • search right
    • target > nums[right] || target < nums[mid]
      • search left

Linked List

• Reverse Linked List ✅ 2023-07-31
• Merge Two Sorted Lists ✅ 2023-07-31
• Linked List Cycle ✅ 2023-08-01
  • Floyd’s Cycle Detection Algorithm
• Reorder List ✅ 2023-08-01
  • Slow and fast pointer to find the center of the linked list
  • Reversing the second-half of the linked list
  • Merging the two linked list with two operations in a single loop
• Remove Nth Node From End Of List ✅ 2023-08-02
  • Maintains two pointers with a gap of n + 1 (including dummy node)
  • Delete the node by assigning its next pointer to its 2nd next pointer
• Copy List with Random Pointer ✅ 2023-08-02
  • Mapping old node to copied node
  • Linking the nodes by referencing them by the map
• Add Two Numbers ✅ 2023-08-02
  • Maintains a carry variable
  • Its modulo is the new digit
  • Its quotient is the new carry
• Find the Duplicate Number ✅ 2023-08-02
  • Floyd’s Cycle Detection Algorithm
  • Find the intersection of the two pointers, then find the entrance of the cycle
• Merge K Sorted Lists

Trees

• Invert Binary Tree ✅ 2023-07-25
• Maximum Depth of Binary Tree ✅ 2023-07-25
• Diameter of Binary Tree ✅ 2023-07-26
• Balanced Binary Tree ✅ 2023-07-27
• Same Tree ✅ 2023-07-27
• Subtree of Another Tree ✅ 2023-07-28
• Lowest Common Ancestor of BST ✅ 2023-07-28
• Binary Tree Level Order Traversal ✅ 2023-08-06
  • Recursive BFS with level parameter
  • Iterative BFS with queue
• Validate Binary Search Tree ✅ 2023-08-07
  • Recursive DFS with minNode and maxNode parameters
  • Update minimum boundary if searching to left
  • Update maximum boundary if searching to right
• Kth Smallest Element in a BST ✅ 2023-08-07
  • Recursive/Iterative inorder traversal
• Construct Binary Tree from Preorder and Inorder Traversal ✅ 2023-08-25
  • Pivot should be the first element of preorder
  • Find pivot index in inorder, divide into two subarrays
    • Left/Right subarray of inorder must contains all nodes in left/right subtree
  • Divide preorder into left/right subarray excluding the processed node, they must have the same size as the inorder left/right subarray
  • Recursively build the tree with the preorder/inorder subarrays
• Binary Tree Maximum Path Sum
• Serialize and Deserialize Binary Tree

Tries

• Implement Trie Prefix Tree ✅ 2023-08-13
  • Using TrieNode with isWord and children variables to construct the trie
  • Insertion and search can be done recursively by maintaining a temporary TrieNode and iterating through the given word
• Design Add And Search Words Data Structure
• Word Search II

Heap/Priority Queue

• Kth Largest Element In a Stream ✅ 2023-08-03
  • Priority queue with ascending order (min heap)
  • Pop (smallest element) when size > k
• Last Stone Weight ✅ 2023-08-03
  • Priority queue with descending order (max heap)
  • Pop and push according to rules
• K Closest Points to Origin ✅ 2023-08-03
  • Min heap with custom comparator
• Kth Largest Element In An Array ✅ 2023-08-03
  • Min heap
  • Or Quick Select, the k-th largest element would be at the index n - k
• Task Scheduler
• Design Twitter
• Find Median From Data Stream

Backtracking

• Combination Sum ✅ 2023-08-17
  • Maintain a pointer indicating that the elements at that point and after can be used as a candidate, for avoiding duplicate in the recursion tree
  • DFS through the candidates and backtrack, add to result if we reached target, return if target cannot be reached or pointer exceeds the size of candidates
• Word Search ✅ 2023-08-17
  • Keeping track of word index to know if the path is valid
  • Mark visited path and reverting it after DFS

Graphs

• Number of Islands ✅ 2023-08-09
  • Flood Fill Algorithm
• Max Area of Island ✅ 2023-08-10
  • Same idea as Number os Islands
• Clone Graph ✅ 2023-08-10
  • BFS or DFS while keeping track of copied nodes in a hash map
• Pacific Atlantic Water Flow ✅ 2023-08-10
  • BFS or DFS from Pacific/Atlantic to mark positions that can reach them
  • The intersection of the two sets are the result
• Course Schedule ✅ 2023-08-16
  • Topological Sort$
• Number of Connected Components In An Undirected Graph
• Graph Valid Tree

Advanced Graphs

• Alien Dictionary

1D Dynamic Programming

• Climbing Stairs ✅ 2023-08-08
  • Bottom-up, same as fibonacci sequence
• House Robber ✅ 2023-08-08
  • Bottom-up, can be optimized using two variables
• House Robber II ✅ 2023-08-09
  • Cannot rob the first and last house at the same time
  • Divide into two ranges [0, len(nums) - 1) and [1, len(nums))
• Longest Palindromic Substring ✅ 2023-08-20
  • Checking all substrings from longest to shortest and early returning $O(n^3)$ $O(1)$
  • Dynamically programming $O(n^2)$ $O(n^2)$
  • Expanding from center $O(n^2)$ $O(1)$
  • Manacher’s algorithm $O(n)$ $O(n)$
• Palindromic Substrings ✅ 2023-08-20
  • Check odd and even palindromes by expanding from center $O(n^2)$ $O(1)$
• Decode Ways ✅ 2023-08-30
  • Solving the subproblem for the number of ways the string can be decoded at index i
  • Branching the search to i + 1 and i + 2 if we decode a two-digit number
• Coin Change ✅ 2023-08-29
  • Recursion, memoization, dynamic programming
  • Solving the subproblem for the fewest number of coins required
• Maximum Product Subarray
• Word Break
• Longest Increasing Subsequence

2D Dynamic Programming

• Unique Paths ✅ 2023-09-01
  • Maintain a m x n matrix to store the unique ways to navigate to the end at a given point
  • Iterate from the end, adding the memoized unique ways together
  • Further optimization can be done by using a dynamic programming array of only two rows, since we only need those information
• Longest Common Subsequence

Greedy

• Maximum Subarray ✅ 2023-08-13
  • Kadane’s Algorithm, i.e. dynamic programming by solving the maximum subarray at index i
  • The maximum subarray at index i is max(dp[i - 1] + nums[i], nums[i]), i.e. start a new subarray if we cannot obtain a larger subarray by including the current index
  • The result would be the largest value in the dp array, we could also run the algorithm in-place to obtain O(1) space complexity
• Jump Game ✅ 2023-09-01
  • Dynamic programming from the back, memoizing whether the back can be reached at index i
  • Greedy algorithm from the back, shifting the goal forward if the previous goal can be reached, return true if the goal can be shifted to start
  • Greedy algorithm from the front, maximizing the farthest index, if farthest is less than current index, return false, otherwise return true after iteration

Intervals

• Insert Interval ✅ 2023-08-14
  • newInterval is after intervals[i], i.e. (newInterval[0] > intervals[i][1])
    • Push intervals[i] into result
  • newInterval overlaps intervals[i], i.e. `(newInterval[0] ⇐ intervals[i][1] && newInterval[1] >= intervals[i][0])
    • Update newInterval with minimum start and maximum end
    • Push newInterval into result after all merging
  • Push the remaining intervals into result
• Merge Intervals ✅ 2023-08-14
  • Sort the intervals first, then merge if overlap, otherwise push into result
• Non Overlapping Intervals ✅ 2023-08-14
  • Sort intervals by start
  • Maintain a prevEnd variable that greedily choose to keep the smaller end if intervals overlaps, i.e. to maximize the number of non-overlapping intervals by allowing more choices
  • If intervals does not overlap, move preEnd to the next interval
• Meeting Rooms
• Meeting Rooms II

Math & Geometry

• Happy Number ✅ 2023-07-31
  • Floyd’s Cycle Detection Algorithm, slow and fast pointers
  • Integer division and modulo operation to obtain the unit digit
• Rotate Image ✅ 2023-08-13
  • Clockwise: transpose and swap columns
  • Anti-clockwise: Transpose and swap rows
• Spiral Matrix ✅ 2023-08-15
  • Maintain bounds in four directions, iterate until bounds overlap
  • Or extract the first element of the matrix, recursively do the same operation on the remaining matrix with negative 90 degree rotation
• Set Matrix Zeroes ✅ 2023-08-15
  • O(1) space can be achieved by using first row and first column plus one extra variable for flagging
  • Note that the iteration step must start from the bottom-right hand corner to avoid crashing with flags

Bit Manipulation

• Number of 1 Bits ✅ 2023-08-07
  • n = n & (n - 1) to remove one digit of 1 at a time, so we only have to loop as many times as there are 1s.
• Counting Bits ✅ 2023-08-18
  • Maintaining offset for dynamic programming, which corresponds to the power of 2
  • Number of 1’s can be deduced from the previous significant integers, i.e. dp[i] = dp[i - offset] + 1
• Reverse Bits ✅ 2023-08-18
  • Initialize result to 0
  • For every bit in n, figure out whether it is 0 or 1, i.e. (n >> i) & 1
  • Insert the bit to the left side of result by res |= (bit << (31 - i))
  • Or by the recursive approach https://leetcode.com/problems/reverse-bits/solutions/54741/o-1-bit-operation-c-solution-8ms/
• Missing Number ✅ 2023-08-08
  • XOR is commutative and associative (order doesn’t matter)
  • XOR a number with itself would result in 0 (e.g. 10 ^ 10 = 00)
  • XOR a number with 0 would result in itself (e.g. 10 ^ 00 = 10)
  • We XOR all the numbers in the range [0, nums.size()] twice except missing_number, what is left is 0 ^ missing_number since everything else cancels to 0, and 0 ^ missing_number is the missing_number
• Sum of Two Integers ✅ 2023-09-01
  • XOR to figure out the sum without carry, i.e. a ^ b
  • AND to figure out the carry bits, i.e. (a & b) << 1
  • Loop until there is no carry bits