problem_set.md

Problem Set

Arrays & Hashing

Problems	Difficulty	Tips	Solutions	Complexity
88. Merge Sorted Array	Easy	3 Pointers + Backward Move	Code	Time $O(n)$ Space $O(1)$ in-place array modification
217. Contains Duplicate	Easy	Hash Set Alternative: Sort & then takes $O(n)$ to compare, but sorting costs $O(nlogn)$		Time $O(n)$ Space $O(n)$
242. Valid Anagram	Easy	Hash Set		Time $O(n)$ Space $O(n)$
49. Group Anagrams	Medium	Sorting + Hash Set		Time: $O(n * (a*log(a))$ where a is max length of strings in the list, where n is the length of the list of string

Sliding Windows

Problems	Difficulty	Solutions	Description
121. Best Time to Buy and Sell Stock	Easy	Code	Need to keep track on buy price with the next days
3. Longest Substring Without Repeating Characters	Medium	Code	Need to have a start pointer along with i to loop through each element and a hash table to store the location
438. Find All Anagrams in a String	Medium	Code	Need to have hash_map to store the counts of s and p, and comparing the count

Linked List

Problems	Difficulty	Solutions	Description
206. Reverse Linked List	Easy	Code
141. Linked List Cycle	Easy	Code	Floyd's Tortoise and Hare Algorithm: Use 2 pointers slow fast to traverse, if slow meets fast, meaning it is a cycle linked list
21. Merge Two Sorted Lists	Easy	Code	Use 2 pointers to traverse the two lists
160. Intersection of Two Linked Lists	Easy	Code	Please refer the comment
203. Remove Linked List Elements	Easy	Code	Create a dummy head and connect it the head, to prevent the case that we need to remove the head
143. Reorder List	Medium	Code	Step 1: Find the middle point of the linked list Step 2: Reverse the second half of the linked list Step 3: Merge first & second half alternatively
83. Remove Duplicates from Sorted List	Easy	Code

Stack

Problems	Difficulty	Solutions	Description
20. Valid Parentheses	Easy	Code	Using Stack

Tree

Problems	Difficulty	Solutions	Description
94. Binary Tree Inorder Traversal	Easy	Code	Using Recursion
100. Same Tree	Easy	Code
101. Symmetric Tree	East	Code
110. Balanced Binary Tree	East	Code

Binary Search (Tree)

• Hints: sorted arrays

Problems	Difficulty	Solutions	Description
704. Binary Search	Easy	Code
278. First Bad Version	Easy	Code	Using the binary search to narrow down the search space

BFS

BFS Tree

Problems	Difficulty	Solutions	Description
102. Binary Tree Level Order Traversal	Medium	Code	Using BFS

BFS Graph

Problems	Difficulty	Solutions	Description
200. Number of Islands	Medium	Code	Need to go through all the cells in the grid and then search adjacent location (top, down, left, right) of the "1" cell to find the maximum size of an island, then can continue

Dynamic Programming

Problems	Difficulty	Solutions	Description
509. Fibonacci Number	Easy	Code
70. Climbing Stairs	Easy	Code	At T(n): first step = 1, remaining steps = T(n-1) or first step = 2, remaing steps = T(n-2). This recurrence relationship is similar to Fibonacci number
746. Min Cost Climbing Stairs	Easy	Code	Recurrence relationship: total_cost[i] = min(total_cost[i-1], total_cost[i-2]) + cost[i] Final Cost: total_cost[n] = min(total_cost[n-1], total_cost[n-2]) as no need to include the cost[n]
64. Minimum Path Sum	Medium	Code	Recurrence relationship: grid[i][j] = min(grid[i-1][j], grid[i][j-1]) + grid[i][j] Note: Need to update the first row grid[0][j] and first column grid[i][0] before can start the recurrence relationship

Backtracking

Problems	Difficulty	Tips	Solutions	Complexity
17. Letter Combinations of a Phone Number	Medium	Back-tracking	Code	Time: $O(n * 4^n)$ Space: where n = len of digits, and m is len of character set that corresponding to each digit, in this case max m = 4
78. Subset	Medium	Back-tracking	Code	Time: $O(n * 2^n)$ where $2^n$ is total number of subsets and $n$ is to copy each subset to res Space: $O(n)$ as we need a temp array and curr_subset where n = length of nums
494. Target Sum	Medium	Back-tracking