1
Two Sum
Python Java
1. Hash O[n] and O[n] space.
2. Sort and search with two points O[n] and O[1] space.
2
Add Two Numbers
Python Java
Take care of the carry from lower digit.
3
Longest Substring Without Repeating Characters
Python Java
1. Check every possible substring O[n^2]
2. Remember the character index and current check pos, if character index >= current pos, then there is duplicate
4
Median of Two Sorted Arrays
Python Java
1. Merge two sorted lists and compute median, O[m + n] and O[m + n]
2. An extension of median of two sorted arrays of equal size problem
5
Longest Palindromic Substring
Python Java
Background knowledge
1. DP if s[i]==s[j] and P[i+1, j-1] then P[i,j]
2. A palindrome can be expanded from its center
3. Manacher algorithm
7
Reverse Integer
Python Java
Overflow when the result is greater than 2147483647 or less than -2147483648.
8
String to Integer [atoi]
Python Java
Overflow, Space, and negative number
9
Palindrome Number
Python Java
Get the len and check left and right with 10^len, 10
11
Container With Most Water
Python Java
1. Brute Force, O[n^2] and O[1]
2. Two points, O[n] and O[1]
12
Integer to Roman
Python Java
Background knowledge Just like 10-digit number, divide and minus
13
Roman to Integer
Python
Add all curr, if curr > prev, then need to subtract 2 * prev
15
3Sum
Python
1. Sort and O[n^2] search with three points
2. Multiple Two Sum [Problem 1]
16
3Sum Closest
Python
Sort and Multiple Two Sum check abs
18
4Sum
Python
The same as 3Sum, but we can merge pairs with the same sum
19
Remove Nth Node From End of List
Python Java
1. Go through list and get length, then remove length-n, O[n] and O[n]
2. Two pointers, first pointer goes to n position, then move both pointers until reach tail, O[n] and O[n]
20
Valid Parentheses
Python
1. Stack
2. Replace all parentheses with '', if empty then True
21
Merge Two Sorted Lists
Python
Add a dummy head, then merge two sorted list in O[m+n]
23
Merge k Sorted Lists
Python
1. Priority queue O[nk log k]
2. Binary merge O[nk log k]
24
Swap Nodes in Pairs
Python
Add a dummy and store the prev
28
Implement strStr[]
Python
1. O[nm] comparison
2. KMP
35
Search Insert Position
Python
Binary Search
46
Permutations
Python
1. Python itertools.permutations
2. DFS with swapping, O[n^2] and O[n^2]
3. iteratively generate n-permutations with [n-1]-permutations, O[n^3] and O[n^2]
47
Permutations II
Python
1. DFS with swapping, check duplicate, O[n^2] and O[n^2]
2. iteratively generate n-permutations with [n-1]-permutations, O[n^3] and O[n^2]
53
Maximum Subarray
Python
1. Recursion, O[nlgn], O[lgn]
2. Bottom-up DP, O[n] and O[n]
3. Bottom-up DP, f[x] = max[f[x-1]+A[x], A[x]], f[x] = max[f[x-1]+A[x], A[x]],O[n] and O[1]
54
Spiral Matrix
Python
O[nm] 1. Turn in the corner and loop
2. [0, 1] -> [1, 0] -> [0, -1] -> [-1, 0]
62
Unique Paths
Python
1. Bottom-up DP, dp[i][j] = dmap[i-1][j] + dmap[i][j-1], O[mn] and O[mn]
2. Combination [m+n-2, m-1]
63
Unique Paths II
Python
Bottom-up DP, dp[i][j] = dmap[i-1][j] + dmap[i][j-1] [if block, then 0], O[mn] and O[mn]
65
Valid Number
Python
1. strip leading and tailing space, then check float using exception, check e using split
2. check is number split by . or e, note that number after e may be negative
66
Plus One
Python
Check if current digit == 9.
70
Climbing Stairs
Python
Bottom-up DP, dp[i] = dp[i - 2] + dp[i- 1]
1. O[n] and O[n]
2. Only two variables are needed, O[n] and O[1]
72
Edit Distance
Python
Background
1. DP O[n^2] space
2. DP O[n] space
78
Subsets
Python
1. DFS Recursion, O[2^n] and O[2^n]
2. Recursion on a binary number, O[2^n] and O[2^n]
3. Sort and iteratively generate n subset with n-1 subset, O[n^2] and O[2^n]
90
Subsets II
Python
1. DFS Recursion with duplicate check, O[2^n] and O[2^n]
2. Recursion on a binary number, O[2^n] and O[2^n]
3. Sort and iteratively generate n subset with n-1 subset, note that if nums[index] == nums[index - 1] then generate from last end to curr end, O[n^2] and O[2^n]
94
Binary Tree Inorder Traversal
Python
1. Recursion, O[n] and O[1]
2. Stack and check isinstance[curr, TreeNode], O[n] and O[n]
3. Stack and check left and right, O[n] and O[n]
98
Validate Binary Search Tree
Python
1. Stack O[n] and O[n]
2. Recursion O[n] and O[n]
104
Maximum Depth of Binary Tree
Python
Recursion max[left, right] + 1
108
Convert Sorted Array to Binary Search Tree
Python
Recursion O[n] and O[nlgn]
109
Convert Sorted List to Binary Search Tree
Python
1. Two points fast [next next] and slow [next] O[nlgn] and O[n]
2. Bottom-up recursion O[n] and O[lgn]
110
Balanced Binary Tree
Python
Recursion 1. Top-down O[n^2] and O[n], Bottom-up recursion with sentinel -1 O[n] and O[n]
111
Minimum Depth of Binary Tree
Python
1. Recursion, note that when size of left [ld] or right [rd] is 0, then min = 1 + ld + rd
2. BFS check by level [right most], which is much faster than recursion
124
Binary Tree Maximum Path Sum
Python
Recursion O[n] and O[n], max [left + node, right + node, left + node + right]
125
Valid Palindrome
Python
Exclude non-alphanumeric characters and compare O[n]
128
Longest Consecutive Sequence
Python
Set or hash, pop adjacency, O[n] and O[n]
133
Clone Graph
Python
Hash and DFS or BFS
136
Single Number
Python
1. Hash or set, O[n] and O[n]
2. xor O[n] and O[1]
137
Single Number II
Python
1. ctypes 32 % 3 and &, O[n] and O[1]
2. ones, twos, threes as bitmask [e.g. ones represents ith bit had appeared once], O[n] and O[1]
138
Copy List with Random Pointer
Python
1. Hash O[n] and O[n]
2. Modify original structure: Original->Copy->Original, then node.next.random = node.random.next, O[n] and O[1]
141
Linked List Cycle
Python
1. Hash or set
2. Two points [fast and slow]
3. Add a max and check if reach the max
142
Linked List Cycle II
Python
Two points, a+b=nr
143
Reorder List
Python
1. List as index to rebuild relation, O[n] and O[n]
2. Two points, O[n] and O[1]
144
Binary Tree Preorder Traversal
Python
1. Recursion, O[n] and O[n]
2. Stack, O[n] and O[n]
145
Binary Tree Postorder Traversal
Python
1. Recursion, O[n] and O[n]
2. Stack and queue [insert 0], O[n] and O[n]
3. Stack and isinstance[curr, TreeNode], O[n] and O[n]
146
LRU Cache
Python
1. Queue and dict
2. OrderedDict
150
Evaluate Reverse Polish Notation
Python
Stack
151
Reverse Words in a String
Python
1. Python split by space
2. Reverse all and reverse words
152
Maximum Product Subarray
Python
DP, f[k] = max[f[k-1] * A[k], A[k], g[k-1] * A[k]], g[k] = min[g[k-1] * A[k], A[k], f[k-1] * A[k]], O[n] and O[1]
153
Find Minimum in Rotated Sorted Array
Python
Binary search with conditions, A[l] > A[r]
154
Find Minimum in Rotated Sorted Array II
Python
Binary search with conditions, A[l] > A[r], A[l]=A[mid]=A[r]
155
Min Stack
Python Java
Add another stack for min stack, maintance this stack when the main stack pop or push: 1. Only push min, such that len[minStack]= 2
166
Fraction to Recurring Decimal
Python
% and Hash to find duplicate
167
Two Sum II - Input array is sorted
Python
Two points O[n] and O[1]
170
Two Sum III - Data structure design♥
Python
1. Hash, O[1] for add, O[n] for find, O[n] space
2. sorted list, O[logn] for add, O[n] for find, O[n] space
3. Sort before find, O[1] for add, O[nlogn] for find, O[n] space
179
Largest Number
Python Java
Define a comparator with str[x] + str[y] > str[y] + str[x], O[nlgn] and O[n]
186
Reverse Words in a String II♥
Python
Reverse all and reverse each words
198
House Robber
Python
f[k] = max[f[k – 2] + num[k], f[k – 1]], O[n] and O[1]
200
Number of Islands
Python
1. Quick union find, O[nlogn] and O[n^2]
2. BFS with marks, O[n^2] and O[1]
204
Count Primes
Python Java CPP
Sieve of Eratosthenes, O[nloglogn] and O[n]
206
Reverse Linked List
Python Java CPP
1. Stack, O[n] and O[n]
2. Traverse on prev and curr, then curr.next = prev, O[n] and O[1]
3. Recursion, O[n] and O[1]
207
Course Schedule
Python
Cycle detection problem
213
House Robber II
Python
f[k] = max[f[k – 2] + num[k], max[dp[0ls-2],dp[1ls-1], O[n] and O[1]
215
Kth Largest Element in an Array
Python Java
1. Sort, O[n] and O[n]
2. Heap, O[nlgk] and O[n]
3. Quick selection, O[klgn] and O[n]
216
Combination Sum III
Python
Generate all combinations of length k and keep those that sum to n
217
Contains Duplicate
Python
1. Set and compare length
2. Sort and check i,i +1
219
Contains Duplicate II
Python
1. Brute force
2. Maintenance a set that contains previous k numbers, and check if curr in set
220
Contains Duplicate III
Python
1. Sort and binary Search
2. Bucket sort
221
Maximal Square
Python
1. Brute force
2. dp[i][j] = min[dp[i-1][j], dp[i-1][j-1], dp[i][j-1]] + 1, O[mn] and O[mn]
3. dp[j] = min[[j], dp[j-1], prev] + 1, O[mn] and O[n]
223
Rectangle Area
Python Java
Rectangle A + B - common area, O[1] and O[1]
228
Summary Ranges
Python
Detect start and jump, O[n] and O[1]
236
Lowest Common Ancestor of a Binary Tree
Python Java
1. Recursive check left, val and right, LCA is the split paths in tree, O[n] and O[n]
2. Store parents during traversing tree, reverse check their lowest common parent, O[n] and O[n]
238
Product of Array Except Self
Python Java
The ans is [0,i -1] * [i+1, len- 1]. We can twice for left and right [reverse], O[n] and O[n]
243
Shortest Word Distance
Python
Update index1 and index2, and check distance, O[n] and O[1]
246
Strobogrammatic Number♥
Python
Hash table and reverse string, O[n] and O[n]
249
Group Shifted Strings♥
Python
Hash and generate hash code for each string, O[n] and O[n]
252
Meeting Rooms
Python
1. Sort and compare intervals[i].end with intervals[i+1], O[nlogn] and O[1]
2. Sort and check intervals when count >= 2, O[nlogn] and O[n]
253
Meeting Rooms II♥
Python Java
1. Priority queue and sort, O[nlogn] and O[n]
2. Go through timeline. If it's a start then meeting + 1, else meeting - 1. The ans is the max[meeting] in timeline. O[nlogn] and O[n]
259
3Sum Smaller
Python
1. Reduce to two sum smaller, then binary search, O[n^2lgn] and O[1]
2. Reduce to two sum smaller, then two points, O[n^2] and O[1]
266
Palindrome Permutation♥
Python
Compute frequency, check number of odd occurrences 2] = [ways[i-1] + ways[i-2]] * [k - 1], O[n] and O[1]
280
Wiggle Sort♥
Python
1. Sort and insert [n - 1] / 2 from tail to correct position, O[nlogn] and O[1]
2. Sort and swap[i, i + 1] from 1 to n - 1, O[nlogn]
3. Iteratively check order and reverse order, if not satisfied, then swap i with i + 1, O[n]
286
Walls and Gates
Python
BFS with queue, O[mn] and O[mn]
288
Unique Word Abbreviation♥
Python
hash
293
Flip Game♥
Python
Python string slicing
294
Flip Game II♥
Python
1. Backtracking to ensure that next step is False, O[n!!] and O[n!!]
2. Backtracking with memo, O[n!!] and O[n!]
3. DP based on Sprague-Grundy Function
296
Best Meeting Point♥
Python
Think hard about Manhattan Distance in 1D case. Sort and find mean, O[mnlogmn] and O[1]
298
Binary Tree Longest Consecutive Sequence♥
Python
Bottom-up or top-down recursion, O[n] and O[n]
305
Number of Islands II
Python
Quick union find with weights, O[nlogn] and O[n]
322
Coin Change
Python
Bottom-up or top-down DP, dp[n] = min[dp[n], dp[n - v_i]], where v_i is the coin, O[amount * n] and O[amount]
336
Palindrome Pairs
Python Java
1. Create a reverse word to index map, then for each word, check prefix and posfix, O[nk^2] and O[n]
2. Tire tree, O[nk^2] and O[n]
337
House Robber III
Python
1. Recursion with hash map, O[n] and O[n]
2. Recursion on two steps, O[n] and O[1]
339
Nested List Weight Sum♥
Python
Depth-first recursion
340
Longest Substring with At Most K Distinct Characters♥
Python
Maintain a sliding window with at most k distinct characters and a count for this window. Note that the start position need a loop to update.
346
Moving Average from Data Stream♥
Python
fix-sized queue or dequeue, O[1] and O[n]
347
Top K Frequent Elements
Python Java
1. Sort by frequency, O[nlogn] and O[n].
2. we can build a min heaq [based on frequency], then pop min until there are k element, O[klgn] and O[n]
351
Android Unlock Patterns♥
Python
Backtracking, O[n!] and O[n]
359
Logger Rate Limiter♥
Python
1. hash which stores the latest timestamp, O[1] and O[n]
2. Using Priority queue to remove older logs, O[n] and O[n]
366
Find Leaves of Binary Tree♥
Python
1. Set or hash to check leaft, O[n^2] and O[n]
2. Recursively check level and return them, O[n] and O[n]
367
Valid Perfect Square
Python Java
Integer square root
1. 1+3+…+[2n-1] = n^2
2. Binary search
3. Newton's method
368
Largest Divisible Subset
Python
Sort and generate x subset with previous results, O[n^2] and O[n^2]
369
Plus One Linked List♥
Python
1. Stack or list that store the list, O[n] and O[n]
2. Two points, the first to the tail, the second to the latest place that is not 9, O[n] and O[1]
370
Range Addition♥
Python
Interval problem with cumulative sums, O[n + k] and O[n]
380
Insert, Delete, Get Random
Python
Uses both a list of nums and a list of their locations
383
Ransom Note
Python Java
Get letter frequency [table or hash map] of magazine, then check randomNote frequency
384
Shuffle an Array
Python
Fisher–Yates shuffle, O[n] and O[n]
387
First Unique Character in a String
Python Java
Get frequency of each letter, return first letter with frequency 1, O[n] and O[1]
388
Longest Absolute File Path
Python
Store last length and rindex, O[n] and O[n]
389
Find the Difference
Python Java
1. Imaging letter a as 0, then the sum[t]-sum[s] is the result
2. Based on solution 1, bit manipulate
400
Nth Digit
Python Java
islands * 4 - overlaps * 2
401
Binary Watch
Python Java
Note that 12 * 60 is much less than 2^n or n^2.
404
Sum of Left Leaves
Python Java
1. Recursively DFS with root.left.left and root.left.right check
2. The same DFS based on stack
405
Convert a Number to Hexadecimal
Python Java
Two's complement 1. Bit manipulate, each time handle 4 digits
2. Python [hex] and Java API [toHexString & Integer.toHexString]
408
Valid Word Abbreviation♥
Python
Go over abbr and word, O[n] and O[1]
409
Longest Palindrome
Python Java
Length of Palindrome is always 2n or 2n + 1. So, get all possible 2*n, and choose a single one as 1 if it exists.
412
Fizz Buzz
Python Java Cpp
1. From 1 to n, condition check
2. Condition check and string connect
414
Third Maximum Number
Python Java
1. Keep max 1-3 then compare, O[n] and O[1]
2. PriorityQueue, O[n] and O[1]
415
Add Strings
Python Java
Two points, careful abour carry, O[n] and O[n]
416
Partition Equal Subset Sum
Python
DP, Check if sum of some elements can be half of total sum, O[total_sum / 2 * n] and O[total_sum / 2]
421
Maximum XOR of Two Numbers in an Array
Python
Check 0~32 prefix, check if there is x y in prefixes, where x ^ y = answer ^ 1, O[32n] and O[n]
422
Valid Word Square♥
Python
Compare row with column, O[n^2]
434
Number of Segments in a String
Python Java
1. trim &split
2. Find segment in place
437
Path Sum III
Python Java
1. Recursively travese the whole tree, O[n^2]
2. Cache sum in Hash based on solution 1. Note that if sum[A->B]=target, then sum[root->a]-sum[root-b]=target.
438
Find All Anagrams in a String
Python Java
Build a char count list with 26-256 length. Note that this list can be update when going through the string. O[n] and O[1]
441
Arranging Coins
Python
O[n] time.
443
String Compression
Python Java
Maintain curr, read, write and anchor [start of this char].
448
Find All Numbers Disappeared in an Array
Python Java
Value [1, n] and index [0, n-1]. Mark every value postion as negative. Then, the remain index with positive values are result. O[n]
453
Number of Segments in a String
Python Java
Each move is equal to minus one element in array, so the answer is the sum of all elements after minus min.
458
Poor Pigs
Python Java
2 pigs for 5 * 5 metric
461
Hamming Distance
Python Java
Hamming Distance is related to XOR for numbers. So, XOR then count 1. O[n]
463
Island Perimeter
Python Java
math, find the area, actual number, then find the digit
475
Heaters
Python Java
1. Binary search hourse in heater array, O[nlogn] and O[1]
2. Two points, O[nlogn] and O[1]
479
Largest Palindrome Product
Python Java
1. Product max palindrome than check, O[n^2] and O[1]
2. Math
482
License Key Formatting
Python Java
String processing, lower and len % K, O[n] and O[n]
485
Max Consecutive Ones
Python Java
Add one when encounter 1, set to 0 when encounter 0, O[n] and O[1]
509
Fibonacci Number
Python Java
1. Recursive, O[n]
2. DP with memo, O[n]. Note that N