After grinding LeetCode for several days, I finally finished. Code is here.

  • Reverse Words in a String Simulation on strings

  • Evaluate Reverse Polish Notation Simulation — evaluate postfix expressions

  • Max Points on a Line Given N points in the plane, find a line that passes through the most points. Enumerate each point as the origin, compute relative coordinates, then compute y/x and use a hash table to count duplicates and find the maximum. O(N^2)

  • Sort List Linked-list versions of QuickSort and MergeSort. O(NlogN). Worth noting: when all elements are equal, if quicksort partitions left to right, it degrades to O(N^2).

  • Insertion Sort List Insertion sort on a linked list. O(N^2)

  • LRU Cache LRU cache algorithm. Ideally each get/set is O(1). Doubly linked list + hash map. Using C++11 STL list and map gives get/set at O(logN)

  • Binary Tree Postorder Traversal Took me forever to write a stack-based iterative postorder traversal. There are much cleaner versions online.

void postOrderTraversalIterativeTwoStacks(BinaryTree *root) {
  if (!root) return;
  stack<BinaryTree*> s;
  stack<BinaryTree*> output;
  s.push(root);
  while (!s.empty()) {
    BinaryTree *curr = s.top();
    output.push(curr);
    s.pop();
    if (curr->left)
      s.push(curr->left);
    if (curr->right)
      s.push(curr->right);
  }
  while (!output.empty()) {
    cout << output.top()->data << " ";
    output.pop();
  }
}

  • Binary Tree Preorder Traversal

  • Reorder List Reverse the second half of the list, then interleave with the first half. O(N)

  • Linked List Cycle II Use a slow pointer and a fast pointer. The slow pointer moves one step, the fast pointer two steps. If there is a cycle, the fast pointer must meet the slow pointer at some node on the cycle. Then prove that after finding the meeting point, walking the same number of steps from the head and from the meeting point finds the cycle start.

  • Linked List Cycle Same as above.

  • Word Break II Given a dictionary and a string, determine whether the string can be split into words from the dictionary. Clearly DP, but you need backtracking. I wrote recursive backtracking. Complexity O(N^3).

  • Word Break Same as above

  • Copy List with Random Pointer Clever solution: for a list a->b->c, insert a copy of each node after the original: a->A->b->B->c->C. Then set random pointers on A, B, C, and finally extract the A->B->C list.

  • Binary Tree Maximum Path Sum Each node has a weight. Find a path maximizing the sum of node values. DP + tree traversal

  • Single Number II Align 32-bit binary representations, sum each bit across N numbers, mod 3, convert the resulting binary to decimal — that is the answer.

  • Single Number XOR is commutative and associative. XOR all numbers directly.

  • Candy Algorithm 1: Each time pick a valley, sort valleys ascending, then distribute candy along each uphill route. O(N*logN) Algorithm 2: Scan left for uphill segments and store in an array; scan right and take the max with the left scan. O(N) Made a dumb mistake:

int a[3] ; memset(a, 0, sizeof(a)) ; // OK 
int *a = new int(3) ; memset(a, 0, sizeof(a)) ; // ERROR 
int *a = new int(3) ; memset(a, 0, sizeof(int) * 3 ) ; // OK 

dp[root] = max(root->val,
               root->val + dp[root->left],
               root->val + dp[root->right],
               root->val + dp[root->left] + dp[root->right]);
maxsum[root] = max( maxsum[root->left], maxsum[root->right], dp[root]);

dp[0,j] = 1 ; (0<=j<=strlen(T))
dp[i,0] = 1 ; (0<=i<=strlen(S))
if(s[i-1] == s[j-1])
    dp[i,j] = dp[i-1,j-1] + dp[i-1,j]
else
    dp[i,j] = dp[i-1,j]

  • Flatten Binary Tree to Linked List Tree traversal + list splicing. When flattening subtrees, keep both head and tail of the resulting list; otherwise joining left and right subtree lists costs O(N) and the overall algorithm becomes O(N^2).

  • Path Sum II Given SUM and a tree, find all root-to-leaf paths whose node values sum to SUM. DFS all nodes and use a vector to store the current path.

  • Path Sum Same as above

  • Minimum Depth of Binary Tree Minimum depth of a tree. Implement with a stack?

  • Balanced Binary Tree Check whether a tree is balanced (heights of subtrees differ by at most 1)

  • Convert Sorted List to Binary Search Tree Convert a sorted list to a height-balanced BST. Traversing the list to find the midpoint and recursing gives O(N*logN). There is a better O(N) approach:

TreeNode* buildTree(ListNode * &list, int start, int end){
	if(start > end ) return NULL ;
	int mid =  (start + end ) >> 1;
	TreeNode* left = buildTree(list, start, mid-1);
	TreeNode* root = new TreeNode(list->val);
	root->left = left;
	list=list->next;
	TreeNode *right = buildTree(list, mid+1, end);
	root->right = right;
	return root;
}

TreeNode *sortedListToBST(ListNode *head) {
    int n = 0 ; 
    for(ListNode *p = head ; p != NULL ; p=p->next , ++n);
   	if(n == 0) return NULL;
    return buildTree(head, 0, n-1);
}

dp[0,0] = 1 
dp[0,j] = (s3[j-1] == s2[j-1] && dp[0,j-1]) ; when (1<=j<=len2); 
dp[i,0] = (s3[i-1] == s1[i-1] && dp[i-1,j]) ; when (1<=i<=len1);
dp[i,j] = (s3[i+j-1] == s1[i-1] && dp[i-1][j]) |
          (s3[i+j-1] == s2[j-1] && dp[i][j-1]) ; 
          when (1<=i<=len1 && 1<=j<=len2 )

h[0] = 1 
h[1] = 1
h[n] = h[0]*h[n-1] + h[1]*[n-2] + ... + h[n-1] * h[0] ;

Monotonic stack:

int largestRectangleArea(vector<int> &height) {
	stack<int> s ; 
	height.push_back(0);
	int i = 0, maxArea = 0 ;
	while( i < height.size() ){
		if(s.empty() || height[s.top()] <= height[i]){
			s.push(i++);
		}else{
			int t = s.top(); s.pop();
			maxArea = max(maxArea, height[t] * (s.empty() ? i: i-s.top()-1));
		}
	}
	return maxArea;
}

Union-find:

for(i = 1 ; i<=n; ++i)  scanf("%d",&h[i]);
for(i = 1 ; i<=n; ++i)  r[i] = l[i] = i;
h[0] = h[n +1] = -1;
for(i = 1 ; i<=n; ++i)
    while( h[i] <= h[ l[i] - 1 ] ) l[i] = l[ l[i] - 1 ];
for(i = n ; i>= 1 ; --i)
    while( h[i] <= h[ r[i] + 1 ] )  r[i] =r[ r[i] + 1 ];
__int64 ans = 0;
for( i = 1 ; i<=n; ++i)
   ans  = max( ans , (__int64)(r[i] - l[i] + 1 ) * (__int64)h[i] );
  • 3Sum Given a sequence, count triples with a+b+c=0. Sort the array, enumerate c, then in the remaining sorted sequence find two numbers summing to −c. Two methods:
  1. Put values in a hash table and check whether C−a is present.
  2. Two pointers lptr and rptr. If their sum > −C, move rptr left; if < −C, move lptr right. Tricky case for -2 0 1 1 2 2: at the first 1, -2 0 1 cannot form a zero sum, but -2 0 1 1 can. So for runs of equal elements, only consider the last element in the run.

  • 3Sum Closest Similar to 3Sum. It can be proved: when lptr + rptr > C, moving lptr left cannot decrease abs(lptr+rptr−C); only moving rptr right can. Implementation same as 3Sum.

  • Insert Interval

  • Wildcard Matching KMP + greedy. With K asterisks, complexity O(K*N). A naive backtracking solution is full of traps — e.g. pattern *? against suffix hi: the * must not greedily match hi. In short, the last * cannot be greedy; only require the suffix after * to match the end of the text strictly. For more detailed solutions, see decades of work by one veteran.

  • Pow(x, n) Binary exponentiation for x^n. Note: when int n = −2147483648, calling abs(n) = 2147483648 overflows INT. The pitfalls of calling abs on int are endless.

  • Container With Most Water Key insight: for sequence 3 5 2 4 3 5 with endpoints 3 and 5, the best partner for 3 must be 5 — 3 cannot pair with anything else for the optimum. So discard 3 and move the left endpoint right — a smaller subproblem. O(N)

  • Merge k Sorted Lists Two approaches: pairwise merge O(KN) where K is list count and N is total elements; or a size-K heap holding the head of each list — O(NlogK).

Spent a while on heap comparator overloading. C++ default priority_queue is a max-heap.

class classcmp{
public:
	bool operator() (const ListNode* a, const ListNode* b)const{
		return a->val > b->val ;
	}
};
priority_queue<ListNode*, vector<ListNode*>, classcmp> que ;

  • Combination Sum DFS

  • Combination Sum II DFS: for sequence 1 1 1 2 5 6 7 10, avoid duplicate combinations like 1 1 2. Ensure chosen 1’s all come from the front of the 1 1 1 run. At depth, when taking the branch that skips Element[depth], skip all later elements equal to Element[depth]; when taking Element[depth], recurse normally. Guarantees no duplicate solutions.

  • Multiply Strings Big integer multiplication

  • Permutations Generate all permutations of [1,2,3..,n].

  • permutations-ii Permutations with duplicates, no repeated output. My approach: a count for each value; at each depth, try all values with count > 0.

  • N-Queens N-queens — enumerate all solutions.

  • N-Queens II N-queens — count solutions. Tried DFS, iteration, bit manipulation. Bit ops are shortest (call dfs(0,0,0,n,sum); sum is the answer):

#define LOWBIT(x) ((x)&(-x))
void dfs(int row, int ld, int rd, int n, int &sum){
    int M = (1<<n)-1, pos, p;
    if(row == M) {  ++ sum; return;} 
    pos = ((row|ld|rd) & M) ^ M; 
    while(pos){
        p = LOWBIT(pos);
        dfs(row|p, (ld|p)<<1, (rd|p)>>1, n, sum);
        pos -= pos & p;
    }
}

(temp & 1) + '0' // a = temp & 1 ; b = a + '0'  ;
temp & 1 + '0'   // a = 1 + '0'  ; b = temp & 1 ;

Clever two-pointer problem. Three pointers r, w, b: [0,r) are 0, [r,w) are 1, [b,+∞) are 2. For the value at w: (0) If 0, swap w and r, advance both r and w. (1) If 1, advance w; (2) If 2, move b left and swap w and b.

void sortColors(int A[], int n) {
    for (int r = 0, w = 0, b = n; w < b; )
      if (A[w] == 0)
        swap(A[r++], A[w++]);
      else if (A[w] == 2)
        swap(A[--b], A[w]);
      else
        w++;
  }

The background is intimidating

# start
0001111********2222
   ^   ^       ^
   r   w       b 

# case.0
00001111*******2222
    ^   ^      ^
    r   w      b 

# case.1
00011111*******2222
   ^    ^      ^
   r    w      b 

# case.2
0001111*******22222
   ^   ^      ^
   r   w      b
  • First Missing Positive Clever: first missing positive in an unsorted array, O(N) time, O(1) space. Place each integer i in 1..N at index A[i−1], then scan. Each swap in the while loop places one number in its correct index; at most N swaps total, so amortized O(1) per index — overall O(N).
int firstMissingPositive(int A[], int n) {
	for(int i = 0 ; i < n ; ++ i)
		while(A[i] > 0 && A[i] <= n && A[A[i]-1] != A[i])
			swap(A[A[i]-1], A[i]);
	for(int i = 0 ; i < n ; ++ i)
		if(A[i] != i + 1)
			return i + 1;
	return n + 1;
}

  • Anagrams “Anagram” is an odd word — two words with the same character counts, e.g. aaaab and baaaa, aaaba. Sort each word to a canonical form and hash for duplicates. O(NMlogM) for N words of max length M.

  • Edit Distance Minimum edit distance from S to T: insert, delete, replace. dp[i,j] = min distance from s[1..i] to t[1..j]:

dp[0,0] = 0 ; 
dp[0,j] = j (1<=j<=len(t))
dp[i,0] = i (1<=i<=len(s))
dp[i,j] = min(dp[i-1,j] + 1, dp[i,j-1] + 1, dp[i-1,j-1] + 1) // delete, insert, replace
if(s[i] == t[j]) dp[i,j] = min(dp[i,j], dp[i-1,j-1]);

  • Trapping Rain Water Key: sum each index i’s contribution. One pass, O(1) space? Also a sad story

  • Set Matrix Zeroes Use matrix[0,i] and matrix[i,0] to record whether matrix[i,j] is zero; two extra flags for row 0 and column 0.

  • Median of Two Sorted Arrays K-th smallest in sorted A[0..M−1] and B[0..N−1]. If A[k/2−1] < B[k/2−1], A[k/2−1] ranks below K in the merge, so discard A[0..k/2−1] when searching for K. Median is (m+n)/2-th smallest; halving each step → O(log(m+n)).

double findKth(int a[], int m, int b[], int n, int k){
	//always assume that m is equal or smaller than n
	if (m > n)
		return findKth(b, n, a, m, k);
	if (m == 0)
		return b[k - 1];
	if (k == 1)
		return min(a[0], b[0]);
	//divide k into two parts
	int pa = min(k / 2, m), pb = k - pa;
	if (a[pa - 1] < b[pb - 1])
		return findKth(a + pa, m - pa, b, n, k - pa);
	else if (a[pa - 1] > b[pb - 1])
		return findKth(a, m, b + pb, n - pb, k - pb);
	else
		return a[pa - 1];
}

s = abbbbbbbbbbbbbbbbbb
     ^
t = acd

s = abbbbbbbbbbbbbbbbbb
      ^
t = a cd

s = abbbbbbbbbbbbbbbbbb
       ^
t = a  cd

s = abbbbbbbbbbbbbbbbbb
        ^
t = a   cd
  • Scramble String DFS — Catalan-style search space with pruning: equal lengths; equal unordered hashes; equal character counts.

Complexity:

h[n] = 2 * sum( h[i] * h[n-i] ) (1<= i < n )

Suppose a sequence where 8 and 14 were swapped. The inorder walk has two inversions >; record the predecessor of the first and successor of the second, then swap.

# noraml
  < < <  <  <  <
1 5 8 10 11 14 23 

# missing swap
  < <  >  <  > < 
1 5 14 10 11 8 23
    ^        ^

# after
  < <  >  <  > < 
1 5 8 10 11 14 23
    ^        ^