leetcode_craker

This is a project tackling Leetcode questions for tech interview. Solutions comes with python

Algorithmic Strategies

1. Divide-and-Conquer

• Divide a larger problem into smaller non-overlapping problems that can be solved independently of each other (top-down).
• The subsolutions produced by these subproblems are then combined to grenerate the overall solution of the problem.
• Example:
  • Apache Spark Map-Reduce
  • Merge / quick sort
  • Binary search

2. Dynamic Programming

• Starting with the smallest overlapping subproblem and keep on combining the solutions, until the final solution is reached (bottom-up).
• Applicable when the subproblems are not independent (in contrast to Divide and Conquer).
• Two main approaches:
  • Memoiztion (Top-Down): Solve the problem recursively, and store the results of subproblems to reuse them.
  • Tabulation (Bottom-Up): Solve the problem iteratively, starting from the smallest subproblems and building up to the solution.

Key Characteristics:

1. Optimal substructure and Overlapping Subproblems: the solution of a problem depends on the solutions of its subproblems.
2. Uses additional space to store intermediate results (e.g., a hashmap or array) to avoid calculating same thing for several times.

How to use DP to approach a problem:

1. What is the method for bruteforce searching?
2. How to do it recursively with Memorization?
3. Turn recursion into interation to get more direct view of the complexity.

Steps for solution:

1. Consider edge cases (optional)

2. Define the state variables (optional)

3. Define the dp array (depending on the state variables)

   1. a single or several variants - O(1) extra space
   2. a 1D array - O(N) extra space
   3. a multi-dimensional array - O(N^2) extra space

   Note: We may always think about whether we could reduce the size of dp (if the previous solutions no longer neccesary after they have been used)

4. Define the initial values

   1. Matrix:
      1. the top-left / bottom-right corner be the same as the original matrix
      2. the first row and column be the same as the original matrix

5. Define the state transition functions (trickest part)

LeetCode questions

Buy and Sell Stock

121.Best time to buy and sell stock (Easy)

122.Best time to buy and sell stock II (Medium)

123.Best time to buy and sell stock III (Hard)

188.Best time to buy and sell stock IV (Hard)

309.Best time to buy and sell stock with cooldown (Medium)

714.Best time to buy and sell stock with transaction fee (Medium)

House Robber

198.House robber (Medium)

213.House robber II (Medium)

String

Multi-dimensional DP

5.Longest palindromic substring (Medium)

72.Edit distance (Medium)

1143. Longest Common Subsequence (Medium)

97. Interleaving String (Medium)

139. Word Break (Medium) (very tricky) Tiktok

140.Word break II (Hard)

Matrix (Multi-dimensional)

Bottom-up

64. Minimum Path Sum (Medium)

120. Triangle (Medium)

Top-down

221. Maximal Square (Medium)

3. Greedy Algorithm

• Solves problems by making the locally optimal choice at each step, hoping that these local choices will lead to the globally optimal solution.
• It does not backtrack or reconsider previous decisions.
• Approach:
  • Pick the best option available at the current step (based on a greedy criterion).
  • Move to the next step.
  • Repeat until the problem is solved.

Key Characteristics:

1. Works when the problem exhibits the greedy choice property (making a locally optimal choice leads to a globally optimal solution).
2. Requires a mathematical proof or reasoning to verify that the greedy approach works for a given problem.

Binary Search

When to use Binary Search:

1. In the simplest case, when we have a sorted array, and we want to find a target value in it, we can use Binary Search.
   • e.g. 374.Guess Number Higher or Lower (Easy)
2. In the general case: if we can define a function (if condition) that map elements in left half to True and the other half to False or vice versa, we can use Binary Search.
   • e.g. 33.Search in Rotated Array (Medium); 162.Find Peak Element (Medium)
3. If the question ask you to search a target with logarithmic TC, it's highly possible to be a binary search question.

Steps for solving Binary Search question:

1. Initialize left and right pointers (the first index and last index of the sequence)
2. Use a while loop to continue the search until the low pointer is less than or equal to the high pointer
3. Calculate the mid point.
   • Use mid = left + (right - left) // 2 rather than mid = (right + left) // 2. The latter one might cause overflow while the former one will never. For example, in C++ and Javaa, int type fits values up to around 2^31, if two such values are added, the sum will overflow.
4. Update the two pointers to find the target.

Complexity

TC: O(log n)

Pseudo Code

l, r = 0, n - 1
while l <= r:
  mid = l + (r - l) // 2
  if array[mid] == target:
    return mid
  if array[mid] < target:  # the target is in the right part of the array
    l = mid + 1  # update left bound
  else:  # the target is in the left part of the array
    r = mid - 1  # update right bound
return -1

LeetCode Questions

374.Guess Number Higher or Lower (Easy)

33.Search in Rotated Array (Medium)

162.Find Peak Element (Medium)

2300.Successful Pairs of Spells and Potions (Medium)

875.Koko Eating Bananas (Medium)

4.Median of Two Sorted Arrays

Binary Search Tree (BST)

Definition of BST: In a BST, the left subtree of a node contains only nodes with keys less than the node's key, and the right subtree contains only nodes with keys greater than the node's key.

The reason we need a data structure as BST is that, to perform deletion and insertion in a sorted array requires TC of O(n), whereas in BST, the operations requires TC of O(log n).

Key operations:

1. Insertion

2. Deletion

   • Node with one child: Replace the node with its child.

   • Node with two children: find the minimum value in the right tree (keep traversing left), recursively delete the right child.

     450. Delete Node in a BST

Property of the tree

235. Lowest Common Ancestor of a Binary Search Tree

DFS (Depth-First Search)

Depth-First Search (DFS) is a versatile algorithm that is commonly used to traverse or search through data structures like graphs and trees. When tackling coding questions that involve DFS, follow these general steps:

1. Define data structures and necessary variables:
   • Tree (comes with the problem)
   • Matrix (comes with the problem)
   • Graph (use dictionary or adjacency lists to build)
2. Keep track of visited nodes to avoid infinite loops:
   • Set: if we only need to track one node is visited or not (two status)
   • List: if we need to track one node is visited (1), not visited (0) and being visited in current dfs (-1) (three status)
     • e.g. find a cycle in the graph 207.Course Schedule (Medium); 210 Course Schedule II (Medium)
   • Binary tree doesn't need visited track
3. Define main function to ensure what we want our dfs do:
   • If the input structure has multiple components (disconnected graphs or trees, diffrent grid in matrix), make sure to visit all components.
4. Define base cases to ensure the recursion terminates correctly:
   • Tree: reaching a leaf node.
   • Matrix: getting out of the matrix or visited
   • Graph: visited
5. Process Current Node:
   • Perform the necessary operations on the current node, update any relevant information or data structures.
   • (tricky) Sometimes we also need to process current node after dfs the neighbors
     • e.g. 207.Course Schedule (Medium); 210 Course Schedule II (Medium)
6. Explore Neighbors:
   • Tree: visit left child and right child
   • Matrix: visit adjacent cells in for directions
   • Graph: visit nodes directed by current node
7. Backtrack (if needed):
   • Depending on the problem, you might need to undo certain changes made during the DFS to backtrack and explore other paths.
8. Optimizations (if needed):
   • Depending on the problem, you might need to optimize your solution. This could involve pruning unnecessary branches or using additional data structures.

DFS in Binary Tree

1. Pre-order traversal / 前序遍历 = 根左右
   • 通常如果题目对遍历位置不敏感，就用前序遍历，没什么特别的。
   • 一棵二叉树的前序遍历结果 = 根节点 + 左子树的前序遍历结果 + 右子树的前序遍历结果
   • Time complexity O(N), space complexity O(h) where h is height of tree. If we don't consider call stack, then space complexity is O(1).
   • e.g. Quick sort
2. In-order traversal / 中序遍历 = 左根右
   • 主要用于Binary search tree (BST)
   • BST 的中序遍历结果为 non-decreasing order
   • Time complexity O(N), space complexity O(h) where h is height of tree. If we don't consider call stack, then space complexity is O(1).
   • e.g. Binary search tree
3. Post-order traversal / 后序遍历 = 左右根
   • 后续遍历十分特殊，因为 post-order operations have access to information passed up from the children (sub-trees).
   • 一旦题目和子树有关，大概率要给函数设置一个返回值，然后用后续遍历。
   • Use cases: e.g. merge sort, delete a node from a binary tree, subtree problems

DFS in Graphs

DFS in Matrix

LeetCode Questions

Tree

100.Same Tree (Easy)

101.Symmtric Tree (Easy)

104.Maximum Depth of Binary Tree (Easy)

236.Lowest Common Ancestor of a Binary Tree (Medium)

1448.Count Goodd Nodes in Binary Tree (Medium)

437.Path Sum III (Medium)

1372.Longest ZigZag Path in a Binary Tree (Medium)

814.Binary Tree Pruning

Graph

207.Course Schedule (Medium)

210 Course Schedule II (Medium)

841.Keys and Rooms (Medium)

547.Number of Provinces (Medium)

1466.Recorder Routes to Make All Paths Lead to the City Zero (Medium)

399.Evaluate Division (Medium) (A bit hard actually)

Matrix

200.Number of Islands (Medium)

130.Surrounded Regions (Medium)

329.Lonegest Increasing Path in a Matrix (Hard)

947.Most Stones Removed with Same Row or Column (Hard)

Other

365.Water and Jugs (Medium)

BFS (Breadth-First Search)

BFS algorithms start from a source node and visits all its neighbors before moving on to the next level of neighbors. BFS guarantees that it visits nodes in increasing order of their distance from the source node. BFS is often used to find the shortest path in an unweighted graph.

1. Start from a Source Node
2. Enqueue the Source Node: Add the source node to a queue (First In First Out) data structure.
   • Use the deque methods from collections
3. Mark the Source Node as Visited
   • Use set() to keep track of visited node
   • In some cases, we can directly modify the cell to mark it as visited
4. While the Queue is Not Empty
   • Dequeue a node from the front of the queue.
   • Visit and process the dequeued node.
   • Enqueue all unvisited neighbors of the dequeued node.
   • In some cases, we want a for loop inside the while loop so that we finish processing all node at this level
5. Repeat Until the Queue is Empty: Continue the process until the queue becomes empty. This ensures that all reachable nodes are visited.
6. Check for Unvisited Nodes: After the BFS is complete, check if there are any unvisited nodes. If yes, repeat the process for those nodes to cover the entire graph.

Pseudo Code

from collections import deque

​	def bfs(graph, start_node):    

​		# Initialize a queue for BFS   

​		queue = deque([start_node])     

​		# Mark the start node as visited

​		visited = set([start_node])

​		while queue:

​			# Dequeue a node from the front of the queue

​			current_node = queue.popleft()

​			# Process the current node (e.g., print, store, or manipulate data)

​			# Enqueue unvisited neighbors

​			for neighbor in graph[current_node]:

​				if neighbor not in visited:

​					# Mark the neighbor as visited

​					visited.add(neighbor)

​					# Enqueue the neighbor 

​					queue.append(neighbor)

When to use DFS? When to use BFS?

• Space Complecity:

  • BFS uses O(w) extra space, where w is the maximum width of the tree
    • Maximum width of a binary tree is 2^(h), where h is the height of the tree and h starts from 0
    • Worst case: when a binary tree is a linked list (only one branch), then h is equal to N
    • h of a balanced tree is O(log N)
  • DFS uses O(h) extra space because of the functional call stack
  • If a tree is balanced, then BFS requires more space；if a tree is a linked list，then DFS needs more space

• Time Complexity: The time complexity for both DFS and BFS is essentially the same ( O(V + E), where V is the number of vertices and E is the number of edges ), but the choice depends on the specific problem requirements and the nature of the graph.

• Use DFS when memory is a concern, and you want to explore deep into the graph.

• Use BFS when finding the shortest path or exploring the graph level by level is important.

LeetCode Questions

Tree

Binary Tree Rigth Side View (Medium)

1161.Maximum Level Sum of a Binary Tree (Medium)

Graph

1926. Nearest Exit from Entrance in Maze (Medium)

994.Rotting Oranges (Medium)

286. Walls and Gates (Medium)

934. Shortest Bridge

1293.Shortest Path in a Grid with Obstacles Elimination (Hard)

Other

127.Word Ladder (Hard) Tiktok

[322.Coin Change (Medium)](322. Coin Change)

Linked List

Code template

1. Basic operations: insertion, deletion, traversal

# Insert node c (head -> b, head -> c -> b)
c.next = head.next
head.next = c

# Delete node c (head -> c -> b, head -> b)
head.next = head.next.next

# Traverse linked list
while head:
  head = head.next

2. Reverse linked list

curr = head
prev = None
while curr:
  nxt = curr.next
  curr.next = prev
  prev = curr
  curr = nxt

3. Dummy head

dummy.next = head
while head:
  # operations of delete, insert...
  head = head.next
return dummy.head

4. Slow and fast pointers

This method is usually used in problems which require: a) finding a middle node in a linked list; b) detecting a cycle in a linked list

LeetCode Questions

Reverse Linked List

25. Reverse Nodes in k-Group (Hard)

Slow and Fast Pointers

2095. Delete the Middle Node of a Linked List (Medium)

142. Linked List Cycle II (Medium)

Array / String

1. Two Pointers

Why do we want to use Two Pointers:

When we want to search for two elements from an array, the brute force solution could lead to nested loops. Two pointers can often solve problems in linear or linearithmic time.

Types of Two Pointers:

1. Left and right pointers: the pointers are initialized at the beginning and the end of the array; both pointers move towards the middle

   • In this case, we don't care about the elments between the two pointers

   Code template:

   def template(array):
   	left, right = 0, len(array) - 1
     
     while left < right:
       if ...:
          left += 1
       if ...:
          right -= 1

2. Slow and fast pointers: the pointers are initialized at the beginning of the array; the fast pointer moves along the array by for loop, while the slow pointer moves only under certain conditions; for each loop, check the subarray [slow : fast] to see whether it meets certain condition

   • In this case, we DO care about the elments between the two pointers
   • Subtypes:
     • Remove duplicates
     • Sliding Window

LeetCode Questions

Left and right pointers

11. Container With Most Water (Medium)

581. Shortest Continuos Unsorted Subarray (Medium) => Monotonic stack

Slow and fast pointers

Move pointers conditionally

1868. Product of Two Run-Length Encoded Array

2. Sliding Window

Common scenarios for using Sliding Window: finding the maximum/minimum subarray, longest substring with distinct characters, or a subarray with a given sum.

Common constraints: some problems have specific conditions or restrictions on the window size or elements inside the window.

How to Slide the Window:

Set up variables to represent the window (left and right pointers) and any other necessary information.

• every SW problem needs left and right pointers to represent the window
• if the window size is fixed as k:
  • left, right = 0, k - 1 (use for i in range(k) to traverse the first window)
  • for sliding the window, use for i in range(k, len(arr)), where left, right = i - k, i
• if the window size is not fixed, and the constraints are on the elements inside the window:
  • left, right = 0, 0
  • for right in range(len(arr)), update left according to the constraint

LeetCode Questions

Fixed window size

456. Maximum Number of Vowels in a Substring of Given Length

Other constraints

1004. Max Consecutive Ones III (Medium) Similar question: 1493. Longest Subarray of 1's After Deleting One Element

76. Minimum Window Substring (Hard)

3. Prefix Sum

When to use Prefix Sum:

1. Subarray Sum or Range Queries:
   • If the problem involves finding the sum of elements in a subarray or handling range queries (queries about subarray sums), prefix sum is often a good choice. It allows you to calculate subarray sums efficiently.
2. Cumulative Operations:
   • If the problem involves cumulative operations on an array, such as finding the running sum or cumulative frequency, prefix sum can simplify and optimize these calculations.
3. Optimizing Time Complexity:
   • If the problem can be solved with a time complexity of O(N) or better using prefix sum, it might be a suitable approach. Prefix sum allows you to perform certain calculations in constant time, improving overall efficiency.
4. Reduction to a Known Problem:
   • If the problem can be reduced to a known problem that involves subarray sums or cumulative operations, consider using prefix sum as a tool to solve the problem efficiently.
5. Avoiding Repeated Calculations:
   • If there are repeated calculations of cumulative sums or subarray sums, using a prefix sum array can help avoid redundant computations and improve performance.
6. Requirements Involving Differences:
   • If the problem involves finding the difference between two subarray sums or handling queries related to differences between elements, prefix sum can be useful.

Complexity:

TC: O(N)

SC: O(N) when we need an array to store the prefix sums / O(1) when we only need a running sum

LeetCode Questions

560. Subarray Sum Equals K (Medium) (Combine with Sliding Window)

2483. Minimum Penalty for a Shop (Medium)

1658. Minimum Operations to Reduce X to Zero (Medium) (Combine with two sums)

Queue / Stack

1. Heap / Priority Queue

2. Monotonic Stack