Array

Prefix-sum can solve many subarray related problems.

Backtracking

General framework for combaination problems:

    1. add result
    2. for element in set
    3.     patch result
    4.     dfs()
    5.     unpatch result
  • 22 Generate Parentheses
    • Patch result only when valid parentheses sequence.
  • 37 Sudoku Solver
    • Patch result only when valid sudoku.
  • 39 Combination Sum
    • Numbers w/o duplicate. DFS monoly on set.
  • 40 Combination Sum II
    • Numbers with duplicate. DFS monoly on sorted set, and skip duplicates before patching.
  • 46 Permutations
    • Numbers w/o duplicate. At each level try all numbers.
  • 47 Permutations II
    • Numbers with duplicate. DFS on sorted set, and skip duplicates.
  • 60 Permutation Sequence
    • Generate k-th permutation of 1…n.
    • O(n^2) time, enumerate digits from the most siginificant position.
    • O(nlog(n)) time if using BST or BIT to support log(n) looking up and updating for i-th digit.
  • 77 Combinations
    • Numbers w/o duplicate, generate (n, k) results. DFS monoly on sorted set.
  • 78 Subsets
    • Numbers w/o duplicate. DFS monoly on sorted set and add to result at each level.
  • 79 Word Search
    • Given a letter grid, search for target word’s path. Brute-force DFS.
  • 89 Gray Code
    • Gray code encodes 1 to n with 1 to n but each adjacent pair differs only in 1 bit.
    • Note that the gray codes can be divided into parts with most significants 1 or 0.
  • 90 Subsets II
    • Numbers with duplicate, generate (n, k) results. Solutions must not duplicate. Skip duplicates before patching.
  • 93 Restore IP Addresses
    • Given a digit string, split it into valid IP.
  • 131 Palindrome Partitioning
    • Given a string, return all palindrome partitions. Test whether palindrome before DFS.
  • 216 Combination Sum III
    • Numbers in 1-9 and exactly k numbers, w/o duplicate. DFS monoly, and return when there is not enough numbers.
  • 254 Factor Combinations
    • Given a number, generate all factor decompositions of it. First generate all factors and DFS on them. Can use "Humble Number" alike method to accelerate it.
  • 267 Palindrome Permutation II
    • Given a string, generate all its permutaions that are palindrome. Simple letter count.
  • 291 Word Pattern II
    • Given a pattern string like “abab” and a target string like “xxyyxxyy”, find if there is a bijection between pattern string’s single characters and target string’s non-empty segments.
    • Enumerate possible segments for each character and memo enumerated results.
  • 306 Additive Number
    • Given a string, find whether it can be parsed as a fibonacci sequence.
    • Enumerate start state and validate following states.
  • 320 Generalized Abbreviation
    • Given a word, generate its generalized abbreviations, e.g., “word”: “w1rd”, “w2d”, “3w”, “4”, etc.
    • DP or bit manipulation also work.
  • 351 Android Unlock Patterns
    • Calculate number of k-length Android unlock patterns.
    • DFS, reuse symmetric cases.

Linked List

Hash Table

Besides being an O(1) r/w table, hash tables are often used to save preprocessed results or find matching elements.

Two Pointers

Two pointers sometimes is an implementation of mono-stack or mono-queue. Mono here means that, under the problem’s condition, the optimal value of left pointer is a mono function of right pointer, and vice versa. One needs to find out the mover changing condition, this is typically when moving more won’t make things better.

String

KMP Template.

Next array calculation is linear time because each time p itself is right shifted, and at most p.length() times. Or we can consider k. k is always >= -1, and it’s increased only p.length() times. but k=next[k] always decreases k, which is at most p.length() times.

The next[i]=next[k] optimization needs no further loop. If p[i] == p[k] still holds, it conflicts with former assignments.

// caculate next
i = 0, k = -1;
while (i < p.length()) {
    while (k >= 0 && p[i] == p[k]) k = next[k];
    i++, k++;
    if (i == p.length()) break;
    if (p[i] == p[k]) next[i] = next[k];
    else next[i] = k;
}
// match, nearly the same with next calculation
i = 0, k = 0;
while (i < s.length() && k < p.length()) {
    while (k >= 0 && p[i] == p[k]) k = next[k];
    i++, k++;
}

Heap

  • 215 Kth Largest Element in an Array
    • O(n+klogk) time using heap sort.
    • O(nlogk) time using minimum heap.
    • Average O(n) using quick-sort-like quick-select.
    • Strict O(n) using divide & conquer.
    • O(32n) time using trie.
  • 295 Find Median from Data Stream
    • O(32) insertion and O(32) query by trie.
    • O(log(n)) insertion and O(1) query by maintaining small-half maxheap and large-half minheap.
  • 313 Super Ugly Number
    • O(kn) time. USACO humble number.
  • 347 Top K Frequent Elements
    • O(nlog(k)) using heap.
  • 355 Design Twitter
    • postTweet(userId, tweetId), getNewsFeed(userId), follow(srcId, tgtId), unfollowId(srcId, tgtId).
    • Use heap to implement getNewsFeed.
  • 373 Find K Pairs with Smallest Sums
    • Given two number array, find k-th smallest pairs formed by numbers from the two arrays.
    • O(klog(k)) time by heap + BFS.
  • 378 Kth Smallest Element in a Sorted Matrix
    • The matrix’s rows and columns are sorted.
    • O(nlog(n)) by binary search. O(klog(k)) by heap + BFS.
    • O(n) time algorithm presented in paper “Selection in X + Y and matrices with sorted rows and columns”, where n is number of rows.
  • 407 Trapping Rain Water II
    • Given a grid with heights, find how much rain water it can trap.
    • O(mnlog(mn)) time, each time floodfill from lowest grid that cannot trap any water. The cannot-trap set is maintained by a heap.
  • 630 Course Schedule III
    • Given semester days and courses with days needed and deadline, find maximum number of courses one can take in a semester.
    • Sort courses by deadline, use max-heap (days) to maintain optimal choice. Replace heap top when there is a course taking less time than top.
  • 692 Top K Frequent Words

Stack

Mono stack/queue can maintain min/max in average O(1) time, get in strict O(1) time.

Dynamic Programming

aD/bD: O(n^a) states, each update consumes O(n^b) time.

1D/0D, 1D/1D (optimization to O(nlog(n))), 2D/0D, 2D/1D (parallelogram inequation), etc.

Digit DP, Tree DP, Knapsack, Binary Optimization, State DP, etc.

Note: for dense problems, search with memo is much slower (~10x) than DP.

  • 10 Regular Expression Matching
    • '.' matches any single character, 'a*' matchs zero or more 'a', '.*' matches zero or more any character.

    • O(nk) time where k is pattern length and n is target length. 2D/0D.

        string s, pattern p
  F[M][N]: s[:M] matches p[:N]
  F[M][N] = (isDot(p[N]) || s[M] == p[N]) && F[M-1][N-1] ||
            isStar(p[N]) && (F[M][N-1] || (isDot(p[N]) || s[M] == p[N]) && F[M-1][N])
  Bound: F[0][N], true for N == 0 and prefix stars.
  • 44 Wildcard Matching
    • '?' matches any single character, '*' matches zero or more any character.

    • O(nk) time, 2D/0D.

        string s, pattern p
  F[M][N]: s[:M] matches p[:N]
  F[M][N] = (isDot(p[N]) || s[M] == p[N]) && F[M-1][N-1] ||
            isStar(p[N]) && (F[M][N-1] || F[M-1][N])
  Bound: F[0][N], true for N == 0 and prefix stars.
  • 53 Maximum Subarray
    • O(n) time and O(1) space.
  • 62 Unique Paths
    • Going from left-up to right-down.
    • O(mn) time, classical 2D/0D. O(min(m, n)) time if calculate (m + n, n), mind overflow.
  • 63 Unique Paths II
    • There will be some obstacles.
    • O(mn) time classical 2D/0D.
  • 64 Minimum Path Sum
    • Going from left-up to right-down, minimize path cost.
    • O(mn) time classical 2D/0D.
  • 70 Climbing Stairs
    • Fibonacci number.
  • 72 Edit Distance

    • O(mn) time classical 2D/0D. Use alignment to give a proof.

        F[M][N]: edit distance between s1[:M] and s2[:N]
  F[M][N] = min(F[M-1][N-1] + !(s1[M] == s2[N]), F[M][N-1] + 1, F[M-1][N] + 1)
  • 85 Maximal Rectangle
    • O(mn) time, classical 2D/0D.
    • Based on Largest Rectangle in Histogram.

    • For each point DP on maxHeight, maxLeft and maxRight.

        maxL/R: maximum left/right space expandable.
  H[x][y] = H[x-1][y] + 1 if R[x][y] == 1 else 0
  L[x][y] = min(L[x-1][y], maxL[x][y])
  R[x][y] = min(R[x-1][y], maxR[x][y])
  • 87 Scramble String
    • Strings can be represented by binary trees. Given two strings, determine if one can be transformed from the other one by flipping binary tree nodes.
    • O(n^4) time, each [i1, j1] can be mapped to any [i2, j2].
  • 91 Decode Ways
    • A->1, B->2, …, calculate number of ways to decode a digit string.
    • O(n) time 1D/0D.
  • 95 Unique Binary Search Trees II
    • Generate all valid binary search trees containing 1 to n.
    • O(catalan_number) time, aboue O(4^n/n^1.5) time.
  • 96 Unique Binary Search Trees
    • Generate number of valid binary search trees containing 1 to n.
    • O(n^2) or O(n) time by Catalan number deduction.
    • C(n) = (2n, n) / (n + 1)
    • C(n) = (2n, n) - (2n, n + 1)
    • C(n) = C(0)C(n - 1) + C(1)C(n - 2) … + C(n - 1)C(0)
    • C(n) = 2(2n - 1) / (n + 1) * C(n - 1)
  • 97 Interleaving String
    • Given string a and b, find whether c can be formed from the interleaving of a and b.
    • O(mnk) time, 3D/0D. F[m][n][k]: c[:k] can be formed from a[:m] and b[:n]. Use memo search.
  • 115 Distinct Subsequences
    • Given string a and b, find number of subsequences s of a i.e. s == b.

    • O(mn) time, 2D/0D

        F[m][n]: number of subsequences of a[:m] that matches b[:n].
  F[m][n] = F[m][n-1] + a[m] == b[n] ? F[m-1][n-1] : 0
  • 120 Triangle

    • Given a number triangle like

          2
   3 4
  6 5 7

      Find maximum path from root to leaf.

    • O(n^2) time, 2D/0D.

  • 123 Best Time to Buy and Sell Stock III
    • Complete at most two transactions.
    • O(n) time O(n) space by scanning from two ends, and for each point calculate maximum profit before/after this point.

    • O(n) time and O(1) space by DFA. Reuse former states by updating from higher states.

        0 -buy--> 1 -sell-> 2 -buy--> 3 -sell-> finale
  ^     |   ^     |   ^     |   ^     |
  |-rest-   |-rest-   |-rest-   |-rest-
  • 124 Binary Tree Maximum Path Sum
    • O(n) time, 1D/0D. Classical tree DP.
    • MaxPath[root] = rootVal + max(MaxPath[left], MaxPath[right]). Global max can be single/double paths.
  • 132 Palindrome Partitioning II
    • Given a string, calculate minimum times of cut to cut it into palindromes.
    • O(n^2) time, classical 1D/1D.
    • O(n) space if we update answer while enumerating all palindromes. Invariant: the prefix before current palindrome has been considered.
  • 139 Word Break
    • Given a dictionary and a string, judge whether the string can be cut into words from dictionary.
    • O(nm) time, where n is string length, m is maximum word length. typical 1D/1D. Need trie.
  • 140 Word Break II
    • Output all possible answers in Word Break. Save possible previous indices at each position.
  • 174 Dungeon Game
    • A maze with HP gem and Toxic area. Calculate minimum start HP.
    • O(mn) time, 2D/0D. start HP can be zero once HP gem is enough.
  • 188 Best Time to Buy and Sell Stock IV
    • Complete at most k transactions.
    • O(nk) time and O(k) space if use DFA.
    • This problem is similar to “maximum K segment sum”. The latter problem has an O(n+klog(n)) time solution. If there is more than K positive numbers, greedily throw minimum positive number or merge maximum negative number.
  • 213 House Robber II
    • Houses in a circle, cannot rob adjacent houses. Calculate the max score.
    • O(n) time. F[M]: maximum score when robbing houses <= M. All states can be divided into two cases: i-th house not robbed or (i+1)-th house not robbed.
  • 221 Maximal Square
    • O(mn) time. 2D/0D. F[M][N]: maximal square with right-down (M, N). F[M][N] = min(F[M-1][N-1]+1,F[M-1][N]+1,F[M][N-1]+1)
  • 241 Different Ways to Add Parentheses
    • Given a string of numbers and operators, return all possible results by adding parentheses.
    • Typical 2D/1D DP, catalan number on operators.
  • 264 Ugly Number II
    • O(n) time. Similar to USACO Humble Numbers.
    • Make the result buffer mono, and keep a pointer pointing to the smallest result R that R*P>maxResult.
  • 265 Paint House II
    • Given m houses in a row and n colors and a house-color cost matrix. Adjacent houses cannot be painted with the same color. Find minimum cost.
    • O(nk) time using mono queue to maintain minimum.
  • 279 Perfect Squares
    • Given n, find the least number of square numbers summing to n.
    • O(n^1.5) time. Typical knapsack.
  • 300 Longest Increasing Subsequence
    • O(nlog(n)) time achieved by maintaining lenToMinEnd.
  • 304 Range Sum Query 2D - Immutable
    • Given a matrix, query it’s subregion.
    • O(n^2) time by prefix (2D) sum.
  • 309 Best Time to Buy and Sell Stock with Cooldown
    • O(n) time with DFA method.
  • 312 Burst Ballons
    • Burst a ballon sequence, score is nums[left]*nums[i]*nums[right].
    • O(n^3) 2D/1D. In order to make sub-problems well-defined, intervals should be closed. F[left][right]: points get by eliminating nums[left + 1]…nums[right - 1].
  • 322 Coin Change
    • Complete knapsack, O(nk) time and O(k) space where n is number of objects and k is knapsack volume.
  • 329 Longest Increasing Path in a Matrix
    • "Ski". O(mn) time with memo search.
  • 333 Largest BST Subtree
    • Given a tree, find the BST with most nodes in it.
    • O(n) time, typical tree DP.
  • 335 Self Crossing
    • A point is moving in a cartesian coordinate system with [up, left, down, right] loops. Check whether the point will head into its own trail.

    • O(n) time by summarizing the problem into three cases:

        Case A: ----    Case B: ----    Case C: ----
          |  |            |  |            |  |
          -->S            |  S            |  S<--
                          |  ^            |     |
                          |  |            -------
                          ----
  • 338 Counting Bits
    • Given n, count all 1-bit presented from 0 to n, and return them as an array.
    • O(n) time (no O(n) * sizeof(int)), count[n] = count[n - lowbit(n)], highbit is also ok.
  • 343 Integer Break
    • Given a break n, break it into a1+a2+…+ak=n and maximize a1*a2*…*ak.
    • O(n^2) time 1D/1D.
    • O(n) time using math. Break the number into 3’s as many as possible.
  • 354 Russian Doll Envelops
    • O(n^2) with straightforward DFS solution, but DFS with memo can time out.
    • O(nlog(n)), sort by ascending height and descending width, then find LIS in width. Descending width is to prevent same height solution.
  • 357 Count Numbers with Unique Digits
    • Count number of numbers with unique digits between 0 and 10^n.
    • O(10n) time by knapsack. O(n) time by use combination math.
  • 361 Bomb Enemy
    • Given a grid with Wall, Enemy and Zero and a killing-cross bomb, find maximum enemy can be killed.
    • O(mn) time, maximum continous length. O(n) space, walk left-right and up-down and maintain up-down memo.
  • 363 Max Sum of Rectangle No Larger Than K
    • O(m^2 * nlog(n)) time using binary search in prefix sums.
  • 368 Largest Divisible Subset
    • Given a number array, find largest subset S that any Si, Sj in S have Si|Sj or Sj|Si.
    • Note that such subset must be a chain that S1|S2|…|Sn, i.e. linear order. O(n^2) 1D/1D.
  • 377 Combination Sum IV
    • Given a number array, find the number of combinations add up to a target. Order matters.
    • O(nk) time, 1D/1D. Enumerate sequence ends.
  • 403 Frog Jump
    • Given several stones, a frog can jump k-1, k, k+1 forward if last jump is k. First jump is 1. Find whether the frog the reach the last stone.
    • O(n^2) time and space, 1D/1D, for each stone maintain its reachable jump length.
  • 413 Arithmetic Slices
    • Given a number sequence, find all arithmetic subarray with length >= 3.
    • O(n) time and O(1) space, simple 1D/0D.
  • 416 Partition Equal Subset Sum
    • Given a number set, partition it into equal-sum parts. 0/1 knapsack.
  • 446 Arithmetic Slices II - Subsequence
    • Given a number sequence, find all arithmetic subsequences with length >= 3.
    • O(n^2) time. Find all deltas, for each delta build a DAG. Then DP on the DAG for path length >= 3.
  • 464 Can I Win
    • Two players take turns take number from 0…n without re-usage. Find whether player 1 always wins.
    • O(2^n) time, state DP.
  • 467 Unique Substrings in Wraparound String
    • Wraparound string is …abcd…xyzabcd…. Given a string, find how many of its substrings appear in it.
    • O(26n) time and O(26) space, for each character save maximum appeared length.
  • 471 Encode String with Shortest Length
    • Find minimum encode of a string, e.g. “abbbabbbcabbbabbbc” -> “2[2[abbb]c]”.
    • O(n^3) time, typical 2D/1D. Build string by two parts or internal repeating units. The latter can be optimized by 459.
  • 472 Concatenated Words
    • Given a word list, for each word judge whether it can be formed by other words.
    • DP with trie, similar with Word Break. Search is faster than DP.
  • 474 Ones and Zeroes
    • Given a list like [“01”,”110”,”1”,”0”] and m '0' and n'1', calculate maximum number of elements constructable.
    • O(mnl) time. Classical 0-1 knapsack.
  • 494 Target Sum
    • Given a number list, one can change their signs, find number of ways to sum to target.
    • O(2000n) time DP, for the sum of elements will not exceed 1000.
  • 514 Freedom Trail
    • Given a dail ring and a target string, find minimum cost to dail the target.
    • O(mn^2) time 2D/1D. F[M][N]: min cost to dail first M characters with ending top is N.
  • 516 Longest Palindromic Subsequence
    • F[m][n]: longest in s[m:n]. F[m][n] = max(F[m+1][n], F[m][n-1], F[m+1][n-1]+2 if s[m]==s[n])
  • 518 Coin Change 2
    • Complete knapsack.
  • 523 Continuous Subarray Sum
    • Given non-negative numbers, find subarray sum == target with size >= 2.
    • Save minimum index for each prefix sum.
  • 552 Student Attendance Record II
    • Find number of strings made by A, L, P. No two or more A, no consecutive L with length >= 2.
    • DP using state machine of last two characters.
  • 560 Subarray Sum Equals K
    • Count number of subarray with sum K. Prefix-sum.
  • 647 Palindromic Substrings
    • Similar to 516.
  • 678 Valid Parenthesis String
    • * can represent empty string or left/right parenthesis. Find whether a string made by left/right parenthesis and * is valid.
    • F[m][n]: first m character can form a string with n more left parenthesis.
  • 741 Cherry Pickup
    • Given an NxN maze, find maximum pickups from left-up to right-down and back to left-up.
    • DP on two paths. DP on x+y=t lines to eliminate repeat pickup problem.
  • 799 Champagne Tower
    • Treat rest champagne as a whole.
  • 879 Profitable Schemes
    • Multi-dimension 0/1 knapsack. DP on range instead of exact number, mind boundary condition.
  • 935 Knight Dialer
    • Count methods a knight can move on a phone numpad.
  • 940 Distinct Subsequences II
    • Given a sequence, find number of distinct subsequences.
    • O(26n) time and O(26) space: iterate on number of subsequences ended with M-th character in alphabet.
  • 943 Find the Shortest Superstring
    • Hamilton path.
  • 964 Least Operators to Express Number
    • Given n and k, give minimum operators (+ - * /) needed to represent k by n.

    • Radix problem.

        For any target < x^k, we can get the target or get x^k - target.
  Construct from the least significant position.
  pos = min(k * digit + pos, k * (digit + 1) + neg)
  e.g., 21 = 10 * 2 + 1 = 10 * 3 - 9 (x = 10)
  neg = min(k * (x - digit) + pos, k * (x - digit - 1) + neg)
  e.g., 79 = 10 * 8 - 1 = 10 * 7 + 9
  • 968 Binary Tree Cameras
    • Given a binary tree, a camera on the node can monitor its parent, its children and itself. Find minimum number of cameras to monitor the whole tree.
    • O(n) time, typical tree DP. Three states: camera, monitored w/o camera, not monitored.
    • Tree (special graph) covering can be solved by greedy algorithm. Put cameras on leaves’ parents and remove monitored nodes.
  • 974 Subarray Sums Divisible by K
    • O(n) time by shifting array.
    • O(n) time by “two sum” of prefix sums. Seems many subarray problems can be done by prefix sum.
  • 975 Odd Even Jump
    • Odd index jump to nearest non-less number, even index jump to nearest non-greater number. Find indices where end is reachable.
    • O(nlog(n)) time, binary search for valid index.
  • 978 Longest Turbulent Subarray
    • Find length of longest subarray such that A[i]<A[i+1]>A[i+2]… for odd i and vice versa for even i.
  • 979 Distribute Coins in Binary Tree
    • Given a tree and coins on nodes. There are in total N coins and nodes. Find minimum steps to make 1 node 1 coin.
    • Tree DP. For each node return its subtree’s redundant coins.
  • 982 Triples with Bitwise AND Equal To Zero
    • Given number array, find number of triples whose AND is zero. 0 <= number <= 65535.
    • O(65535n) time. Store pair AND count in an array and for each number try each number in the array.
  • 983 Minimum Cost For Tickets
    • Given days for visiting and 1-day, 7-day and 30-day pass and their costs, find minimum cost to cover the days.
    • Classical 1D/1D. O(n) time because optimal day is mono increasing.
  • 988 Smallest String Starting From Leaf
    • Given a binary tree, each node has a character, find smallest string from leaf to root.
    • Tree DP.
  • 996 Number of Squareful Arrays
    • Given a number array, find number of permutations that every pair of adjacent elements sums to a perfect square.
    • Typical Hamilton path with state DP.
  • 1000 Minimum Cost to Merge Stones
    • Merge N piles of stones, each time merge exactly K consecutive piles.
    • F[m][n][k]: minimum cost of m-th to n-th stone merged into k piles.
  • 1026 Maximum Difference Between Node and Ancestor
    • Tree DP on sub-tree min and max.
  • 1027 Longest Arithmetic Sequence
    • For each position maintain delta and maximum length.
  • 1048 Longest String Chain
    • Given a list of words, find maximum increase-one-letter sequence like a -> ab -> acb.
    • DP on different word-length layers.

Binary Search

Binary search can be used to optimize DP updating process.

Binary search on answer is a useful technique.

Binary Search Tree

Greedy

Two kinds of greedy policy: proovable by swapping or proovable by math induction.

  • 45 Jump Game II
    • Given an array with max jumping distance at each place. Caculate minimum step to the end.
    • O(n) time by greedy. Note that the minimum step to each index is mono increasing. Update jump number at each interval’s end. Intervals can be updated greedily.
  • 55 Jump Game
    • Given an array with max jumping distance at each place. Judge whether the end is reachable.
    • O(n) time by greedy.
  • 56 Merge Intervals
    • O(nlog(n)) time, sort by start position and merge.
  • 134 Gas Station
    • Given gas stations distributed on a circle, calculate whether one can travel around the circle once clockwise. Each gas station has limited gas volume.
    • O(n) time by greedy. Note that if SUM(cost) <= SUM(gas), there is always a solution, otherwise the circle can be divided into multiple parts where SUM(cost_part) > SUM(gas_part), contradiction. Then go around the circle and find the maximum point as start.
  • 135 Candy
    • Children in a line, each with a rating value. Higher rate has more candy than neighbors. Calculate minimum candy.
    • O(n) time and O(1) space by greedy. Find all mountains, mountain feets are all ones and mountain tops depends to the longer side.
  • 152 Maximum Product Subarray
    • O(n) time. Seperate the array by 0, and try positive greedily.
  • 253 Meeting Rooms II
    • Given some meeting times, find out minimum number of meeting rooms required.
    • O(nlog(n)) time by sorting and line sweeping.
  • 330 Patching Array
    • Given a sorted positive array, return minimum number of numbers needed to make any number in [1, n] is representable by sum of array numbers.
    • If [0, n) is filled, then [0, n + m) can be filled for any m <= n. Greedily choose m == n when there is no number from array.
  • 334 Increasing Triplet Subsequence
    • Given a number sequence, find if there is any i<j<k that nums[i]<nums[j]<nums[k].
    • O(n) time and O(1) space. Like LIS, maintain minimum end of different length (3 here).
  • 358 Rearrange String k Distance Apart
    • Given strings like “aabbcc”, re-arrange it i.e. the same characters are at least distance k from each other.
    • O(n) time, greedily choose most remaining character.
  • 376 Wiggle Subsequence
    • Give a sequence, caculate the maximum length of subsequence that S1 < S2 > S3… or S1 > S2 < S3…
    • O(n) by greedily update current value when the same inequality holds.
  • 392 Is Subsequence
    • Given S and T, judge whether T is a subsequence of S.
    • Follow up: lots of queries. Store T’s chracters’ indices and use binary search.
  • 406 Queue Reconstruction by Height
    • Given (h, k) pairs, k is the number of higher people before self, reconstruct the queue.
    • When h is same, smaller k is better. When k is same, smaller h is better. Greedily choose lowest valid element. Use BIT to save how many pairs before are higher.
    • This is a swap-invariant problem.
  • 435 Non-overlapping Intervals
    • Given intervals, determine minimum intervals needed removing to make intervals non-overlapping.
    • O(nlog(n)) time and O(n) space by DP in the order of interval ends. For each interval find the minimum of removing or not.

    • O(nlog(n)) time and O(1) space by greedy in the order of starts/ends. Two cases:

          ---- : remove the latter    ---   : remove the outer
  ----                        -------
  • 452 Minimum Number of Arrows to Burst Balloons
    • Given some segments, each time one can declare a point to erase all segments covering it. Find minimum declarations to erase all segments.
    • O(nlog(n)) time, greedily accumulate more segments before erasing. Any solution erasing the group by more than one declaration can be optimized to our method.
  • 456 132 Pattern
    • Given a number array, find whether there is i<j<k and nums[i]<nums[k]<nums[j].
    • O(n) time, greedily find maximum (nums[k], nums[j]) pairs from right. Much like Increasing Triplet Subsequence.
    • O(nlog(n)) time, use set to maintain right numbers and find smallest number > nums[i].
  • 484 Find Permutation
    • Given “DI” like sequence, where D is decrese and I is increase, find the lexicographically minimum number sequence. For “DI”, answer is 312.
    • Greedily build I+D+ sequence: put all but last I at the bottom, then ID+ top down.
  • 495 Teemo Attacking
    • Teemo attack at several time points and have poison buff. Calculate total buff time.
    • O(n) time and O(1) space, check at each timepoint whether the poison can last to the next.
  • 621 Task Scheduler
    • Given tasks, the machine must take a rest of L time units between two same tasks, find the minimum working time.
    • O(time) time, greedily choose task with most remaining. Can be optimized to O(n) if skip spare window.
  • 763 Partition Labels
    • Given a string, partition it into as many parts as possible such that each letter appears in at most one part.
    • Greedily find maximum index of encountered characters.
  • 767 Reorganize String
    • Same as 358.
  • 871 Minimum Number of Refueling Stops
    • There are some gas station with limited gas G[i]. Find minimum number of refueling stops to reach the end.
    • O(n^2) time by DP on maximum gas remaining with first M stations and N refuelings.
    • O(nlog(n)) time by greedily choose maximum G[i] in reachable range.
  • 945 Minimum Increment to Make Array Unique
    • Given an array, calculate minimum steps to make elements in A unique by incrementing elements.
    • O(n) time by greedily assigning lowest holes.
  • 948 Bag of Tokens
    • Given power bags, initial power P. If each bag earns 1 point, try to earn maximum points.
    • O(nlog(n)) time, greedily use lowest bags for points, and points for highest bags.
  • 976 Largest Perimeter Triangle
    • Given edge lengths, find maximum perimeter of valid triangles.
    • O(nlog(n)) time, sort then check maximum triples. Note that for optimal solution, given any longest edge, the other two edges must be maximum ones not longer than it.
  • 984 String Without AAA or BBB
    • Generate strings containint m A’s and n B’s without “aaa” or “bbb”.
  • 1005 Maximize Sum Of Array After K Negations
    • Given a number array, find maximum array sum with K negations.
    • Greedily find minimum negative and positive.
  • 1007 Minimum Domino Rotations For Equal Row
    • Given two rows of numbers, find minimum exchanges for numbers in either row become unique.
    • Just try two numbers at the head.

Math

Reservior sampling: Say sampling K items. Keep the first K items. In the N-th (N>K) sampling, keep the old items with probability 1 - K/N. Easy proof by math induction.

Fisher-Yates algorithm: Each time select one element from rest K elements. Selection is implemented by swapping.

Game theory: mini-max, NIM problem, Sprague-Grundy function, etc.

Expanded Euclid algorithm.

Sieve of Eratosthenes, Miller Rabin.

  • 7 Reverse Integer
    • Mind overflow!
  • 9 Palindrome Number
  • 29 Divide Two Integers
    • Do division without using *, \/ and mod. Generate binary representation of result.
  • 149 Max Points on a Line
    • O(n^2) time. For each point, sort other points into buckets according to their slopes.
    • O(n^3) method also works, uses dot product.
  • 166 Fraction to Recurring Decimal
    • Given x/y representation, calculate recurring decimal representation.
    • Be careful with overflow.
  • 168 Excel Sheet Column Title
    • 28 -> AB
    • Items within length N = 26 + 26^2 + 26^3 + … + 26^N
  • 171 Excel Sheet Column Number
  • 204 Count Primes
    • Given n, count how many primes there are from 1 to n.
    • Sieve of Eratosthenes, erase ik, stop at i = sqrt(n).
    • Miller-Rabin.
  • 223 Rectangle Area
    • Given two rectangles, find overall area.
    • Similar to a problem in USACO training, cut the other rectangle from up, down, left, right.
  • 233 Number of Digit One
    • Given a positive number n, count number of 1’s appearing in numbers from 1 to n.
    • O(n) time, classical digit DP.
  • 247 Strobogrammatic Number II
    • Find all numbers that would look the same after turning 180 degree, like 69, 11, 88, 0, etc.
    • Simple recursion.
  • 231 Power of Two
    • Determine whether an integer is a power of two. Use lowbit.
  • 248 Strobogrammatic Number III
    • Find all numbers between low and high.
    • Add a comparator.
  • 277 Find the Celebrity
    • N-person team, there is a person that doesn’t know others but others all know him. Find it by sending knows(A, B) queries.
    • O(n) time. Each query at least strikes out one person.
  • 292 Nim Game
  • 294 Flip Game II
    • Non-trivial O(n^2) solution by Sprague-Grundy function.
  • 319 Bulb Switcher
    • There is a bulb array. There is n operations, and the i-th operation will switch ki bulbs. Calculate whether k-th bulb is on.
    • Count factor numbers. Only square numbers are on.
  • 356 Line Reflection
    • Given several (x, y) points, find a vertical line made the pattern central symmetric.
    • O(n) time. The reflection line’s x is always (minX + maxX) / 2.
    • Double precision is not safe?
  • 360 Sort Transformed Array
    • Given f(x) = ax^2 + bx + c and a sorted array, given the sorted array mapped by f.
    • Find the root.
  • 365 Water and Jug Problem
    • Given two jugs with volume a and b, find whether water volume c can be measured.
    • Equivalant to solve ax + by = c (expand euclid algorithm), with a + b >= c.
    • x < 0 && y > 0: fill a with b, and pour a once full, vice versa.
  • 372 Super Pow
    • Caculate a^b mod 1337, where b is very large.
    • Use Chinese remainder theorem because 1337 = 7 * 191?
  • 375 Guess Number Higher or Lower II
    • Guess number, each time wrong pay $x where x is the guessing number. Find the cost that guarantees to win.
    • Minimax. Enumerate each split point and take the best cost, each best cost is the worst cost of left/right side.
    • Follow up: expected loss instead of worst loss. Use probability to multiply worst cost in DP?
  • 382 Linked List Random Node
    • Classic reservior sampling.
  • 384 Shuffle an Array
    • Classic Fisher-Yates algorithm.
  • 390 Elimination Game
    • Given an array from 1 to n, remove odd/even position numbers. Find the last number.
    • Each time all a mod b (b is 2^n) is eliminated. Infer “a” each time.
  • 396 Rotate Function
    • Given A, Bk is A’s rotation, find maximum F(k) = 0 * Bk[0] + 1 * Bk[1] + … + (n-1) * Bk[n-1]
  • 398 Random Pick Index
    • Use map + rand or origin vector + reservior sampling.
  • 412 Fizz Buzz
  • 423 Reconstruct Original Digits from English
    • Given a permutation of a string made up by 0-9’s english words’s, recover digits.
    • Use some unique character in the word.
  • 453 Minimum Moves to Equal Array Elements
    • Given number array, each time we can increase n-1 numbers, find minimum moves to make all elements equal.
    • Increase n-1 == decrease 1. Find minimum.
  • 462 Minimum Moves to Equal Array Elements II
    • Given number array, find minimum moves (+1/-1) to make all elements equal.
    • Find median.
  • 469 Convex Polygon
    • Find whether points sequence form a convex polygon.
    • Cross product is sufficient. No dot product validation needed.
  • 470 Implement Rand10() Using Rand7()
    • Rejection sampling. Pitfall: don’t use rand7() * rand7(), use 7 * rand7() + rand7() instead.
    • Can re-use redundant digits in next rejection sampling.
  • 477 Total Hamming Distance
    • Hamming distance of two numbers: bit number of XOR. Given a number array, count sum of all number pair hamming distance.
    • O(n) time, make use of prefix one/zero counts.
  • 483 Smallest Good Base
    • Given n, find minimum k that n’s representation is all-one-sequence in base k.
    • Enumerate one-sequence’s length and binary search for k. Need __u128int_t to avoid overflow.
  • 486 Predict the Winner
    • Two players fetch number from array’s two ends alternatively, judge whether player1 can win.
    • Typicial minimax.
  • 497 Random Point in Non-overlapping Rectangles
    • Area-weighted probability. Why only upper_bound works?
  • 528 Random Pick with Weight
    • Use map and lower_bound.
  • 593 Valid Square
    • Check 6 possible point orders with cross product and distance.
  • 670 Maximum Swap
    • Given a number, swap any two digits once to get maximum.
    • Find first non-largest digit and swap it with least significant largest.
  • 793 Preimage Size of Factorial Zeroes Function
    • Find how many number X are there i.e. X! has k trailing zeros.
    • Trailing zero number increases every 5 numbers.
  • 812 Largest Triangle Area
    • Given points, find maximum area of triangle formed by any of them.
    • Heron’s formula: S = sqrt(p(p-a)(p-b)(p-c)).
  • 829 Consecutive Numbers Sum
    • Find how many ways a number can be represented as an arithmetic sequence.
    • N=k(k+1)/2+k*M, enumerate k.
  • 878 Nth Magical Number
    • Given A and B, find k-th smallest number divisible by A or B.
    • Binary search on n*A array.
  • 891 Sum of Subsequence Widths
    • Given a number array, find sum of all (max-min) of subsequences.
    • Sort and count neighbor coverage times. It’s all about power of twos.
  • 899 Orderly Queue
    • Given a string, one can move any character in prefix of length N to the end of the string. Find the lexicographically minimum string reachable.
    • When N>=2, this is a insertion sort.
  • 949 Largest Time for Given Digits
    • Given four digits, make up largest HH:MM time.
  • 957 Prison Cells After N Days
    • Find loop.
  • 963 Minimum Area Rectangle II
    • Given (x, y) points, find minimum area rectangle formed by those points. Sides are not necessarily parallel to x or y.
  • 970 Powerful Integers
    • Given x and y, find all numbers x^i + y^i <= bound.
  • 972 Equal Rational Numbers
    • Given two rational numbers (like 7.3(9) == 7.4), judge whether they’are equal.
    • Shorten cycling part, then shorten fractional part, then process (9) case.
  • 977 Squares of a Sorted Array
  • 991 Broken Calculator
    • Given X and Y, one can do -1 and *2 to X, find minimum steps to Y.
    • Consider convert Y to X by doing +1 and /2. Greedily do /2 when even, +1 when odd.
  • 997 Find the Town Judge
    • Similar to 277.
  • 1006 Clumsy Factorial
    • clumsy(10) = 10 * 9 / 8 + 7 - 6 * 5 / 4 + 3 - 2 * 1, implement clumsy(N).
  • 1015 Smallest Integer Divisible by K
    • Find minimum length of 1-seq divisible by K if possible.
    • next_module = (10 * prev_module + 1) % K. There will be a loop.
  • 1025 Divisor Game
    • Given N, one can replace it with N - x where 0<x<N and N % x == 0. Given N, find whether first player will win.
    • Just return N % 2 == 0. All odd numbers are replaced to even numbers, while even numbers can be replaced to N - 1.

Divide and Conquer

Union-Find

Tree

Morris Traversal

hasLeft -> find left subtree's rightmost leaf
    leaf found -> link current node to its right child -> go left
    self found -> break connection and go right subtree
else go right subtree

Stack-Based Iterative Traversal

while !stack.empty()
    p = stack.top()
    if (p->right != nullptr)
        p = p->right
        while (p != nullptr) push p, update p as p->left; # get smallest
    else
        pop stack
        while (stack top's right is p) update p, pop stack; # while largest

Sort

Merge sort: O(nlog(n)) time. O(log(n)) space with recursion, O(1) space with bottom-up.

Heap sort: heapify O(n) time, poping O(nlog(n)). O(1) space.

Quick sort: O(nlog(n)) average time.

Quick selection: O(n) average time. Can do by nth_element in STL.

// Quick Selection
pivot = nums[right--];
l = left, r = right;
while (l - 1 < r) // invariant: <left:<pivot, >right:>=pivot
    if (nums[l] >= pivot) swap(nums[l], nums[r--]);
    else l++;
if (k == l - left + 1) return pivot;
else if (k <= l - left) right = l - 1;
else k -= left - l + 1, left = l;

Some sequences satisfy that swapping adjacent elements doesn’t affect other elements. This means that any answer can be optimized into the optimal one by swapping neighbors. Such problems can be solved by defining custom comparators.

  • 31 Next Permutation
    • O(n) time (worst case is reverse) and O(1) space by finding the least significant number a i.e. there is b less significant than b and a < b.
    • Simulating the DFS stack and judging at each depth whether the chose one is the maximum in possible number set also works.
  • 57 Insert Interval
    • O(nlog(n)) time by sorting and merge.
    • O(n) time by direct insert.
  • 148 Sort List
    • O(nlog(n)) time by merge sort. O(1) space by bottom-up sorting.
  • 179 Largest Number
    • Given a list of non-negative integers, concatenate them into the largest number.
    • O(nlog(n)) time by custom sorting. For any two numbers, compare which should be the first to form a larger number when they form a new number. For example, 30|309 vs. 309|30.
  • 274 H-Index
    • Given a citation list, find the author’s H-index.
    • O(nlog(n)) time by sorting.
    • O(n) time by radix sorting. Any citation larger than n can be treated as n.
  • 280 Wiggle Sort
    • Given a sorted array A, no replica, sort it i.e. A[0] < A[1] > A[2] < A[3] …
    • O(n) time by swapping neighbors.
  • 296 Best Meeting Point
    • Given points in a grid, find the point where sum of manhattan distance from given points to it is minimized.
    • Find the median.
  • 324 Wiggle Sort II
    • Given an array A, might with replica, sort it i.e. A[0] < A[1] > A[2] < A[3] …
    • Average O(n) time by quick selection and push >mid to left and < mid to right.
  • 370 Range Addition
    • Given a range [0, n] and several range updates, give final values of all points.
    • O(nlog(n)) time by sorting the ranges and line sweeping.
    • O(n) time and O(1) space by changing range bounds and using prefix sum.
  • 451 Sort Characters By Frequency
  • 493 Reverse Pairs
    • Given a number array, find all (i,j) pairs that num[i] > num[j] * 2.
    • Instrumented merge sort or BIT or BST(trie) with binary search. 315 and 327 are the same paradigm.
  • 539 Minimum Time Difference
    • Given timestamps, find minimum difference. Sort and scan.
  • 759 Employee Free Time
    • Sort and find holes in intervals.
  • 912 Sort an Array
  • 969 Pancake Sorting
    • Sort an array by reversing its prefixes.
    • The minimum number question is NP-hard. See Wikipedia
  • 973 K Closest Points to Origin
  • 1057 Campus Bikes
    • Given positions of bikes and persons, match shortest manhattan distances.
    • Sort bike-person pairs according to their distances.

Bit Manipulation

  • 136 Single Number
    • XOR.
  • 137 Single Number II
    • In such a problem, use bit DFA to substitude XOR operation. Such bit DFA should become 0 if 1 is met M times, where M is the occurence time of most elements.
  • 187 Repeated DNA Sequences
    • Given a DNA sequence (ATCG), find all 10-length substring occuring more than once.
    • Use bitset to accelerate.
  • 201 Bitwise AND of Numbers Range
    • Find the most significant bit that two numbers differ.
  • 260 Single Number III
    • Given an array, all elements appear twice except two elements appear once. Find the two numbers.
    • O(n) time and O(1) space. The two numbers must differ in some bit. Divice the whole array according to the bit, and the subproblem is Single Number I.
  • 318 Maximum Product of Word Lengths
    • Given a list of words, find maximum length product of two words having no common characters.
    • O(n^2) time, use bit manipulation for acceleration.
  • 393 UTF-8 Validation
    • Emulation using bit manipulation.

Search

Graph

BFS on priority queue can be a variant for Dijkstra. Visited set or update on smaller distance both works. The former will visit each node, thus each edge only once. The latter will never visit the same node because priority queue ensures that first visit is smallest distance.

Trie

Design

Segment Tree & Binary Index Tree