LeetCode Problem Summary
Array
Prefixsum can solve many subarray related problems.
 41 First Missing Positive
 O(n) time and O(1) space, put i in ith place.
 48 Rotate Image
 Rotate a matrix in place. Unionpilling.
 54 Spiral Matrix
 Return matrix elements in spiral order.
 59 Spiral Matrix II
 Fill matrix in spiral order.
 66 Plus One
 73 Set Matrix Zeros
 Given a matrix, if there is a zero, it’s row and column are set to zero.
 O(mn) time and O(1) space. Save tainted rows/cols in 0 row/col, and record whether 0 row/col is cleared.
 163 Missing Ranges
 Given a number array, return missing ranges.
 Mind overflow.
 169 Majority Element
 O(n) time and O(1) space achieved by Boyer Moore Vote algorithm.
 228 Summary Ranges
 Given a sorted number array, convert them into intervals.
 229 Majority Element II
 Boyer Moore Vote can be extended to O(n) time and O(k) space in general [n/k] case.
 Each time throw k different elements.
 238 Product of Array Except Self
 Given an array, for each element compute array product except itself.
 O(n) time and O(1) space by prefix product.
 245 Shortest Word Distance III
 Given word list and two words, find minimum distance of their indices.
 O(n) time and O(1) space, simple scan through.
 283 Move Zeros
 Given a array containing zeros, move these zeros to the end of the array.
 289 Game of Life
 Emulate a game of life grid.
 311 Sparse Matrix Multiplication
 Given two sparse matrices, multiply them.
 O(mne) time where m and n is the result matrix’s dimensions and e is related to sparsity. Convert rows and columns into (number, index) pairs and multiply them.
 419 Battleships in a Board
 A battleship in a grid is XXXX sequence horizontal or vertical. Any two battleships won’t intersect. Count them.
 O(n) time (one pass) and O(1) space. Find battleship’s leftup heads.
 442 Find All Duplicates in an Array
 Given a number array with length n and elements from 1 to n, some elements appear exactly twice while others exactly once.
 O(n) time and O(1) space, put numbers in their place, and find mismatched ones.
 487 Max Consecutive Ones II
 Given 01 string, one can turn a 0 to 1. Find maximum consecutive 1 string.
 O(n) time and O(1) space, scan through 1 strings and try to connect 0connecte ones.
 Can use 424’s method.
 498 Diagonal Traverse
 Walk matrix (0,0), (0,1), (1,0), (2,0), (1,1), (0,2), …
 531 Lonely Pixel I
 Given WB matrix, find number of B’s that there is no other B in the same row or column.
 533 Lonely Pixel II
 Given WB matrix and K, find number of B’s that 1) there is exactly K B’s in the same row and column, and 2) for all rows that have B at column C, they should be exactly the same with current row.
 Put same rows in one group, then check each column.
 723 Candy Crush
 755 Pour Water
 Use stack to decrease simulation time.
 794 Valid TicTacToe State
 807 Max Increase to Keep City Skyline
 950 Reveal Cards In Increasing Order
 961 NRepeated Element in Size 2N Array
 Boyer Moore Vote.
 962 Maximum Width Ramp
 Given a number array, find maximum i, j i.e. A[i] <= A[j] and i < j.
 O(nlog(n)), prefixmin.
 985 Sum of Even Numbers After Queries
 Keep track of even numbers only.
 989 Add to ArrayForm of Integer
 Add two arrayform integers.
 995 Minimum Number of K Consecutive Bit Flips
 Given a 01 array, one can flip a consecutive K bits at a time. Find minimum flip steps to make all elements 1.
 O(n) time and O(K) space by queue.
 O(1) space by counting current flip number in the Kwindow. If flip number & 1 == A[i], we need to flip. Make use of input array to record whether a position is flipped.
 999 Available Captures for Rook
 1013 Partition Array Into Three Parts With Equal Sum
 1014 Best Sightseeing Pair
 Given a number array, find maximum i < j such that maximizes A[i] + A[j] + i  j.
 Store All A[i]+i and find maximum of them.
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 kth 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 ith 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. Bruteforce 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 19 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 nonempty 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 klength Android unlock patterns.
 DFS, reuse symmetric cases.
Linked List
 General scheme to reverse linked list
 before = nullptr
 oldHead = head, head = head>next, oldHead>next = before, before = oldHead
 need update result when before == nullptr
 2 Add Two Numbers
 Add two numbers represented by linked list.
 19 Remove Nth Node From End of List
 O(n) time and O(1) space in one pass: two pointers, the distance between which is N.
 21 Merge Two Sorted Lists
 23 Merge k Sorted Lists
 O(nlog(k)) using heap.
 O(nlog(k)) time (from merge tree) and O(1) space using merge sort.
 24 Swap Nodes in Pairs
 before>p1>p2>head.
 25 Reverse Nodes in kGroup
 Similar to swap nodes in pairs, but do reverse instead of swap.
 61 Rotate List
 82 Remove Duplicates from Sorted List II
 86 Partition List
 Partition linked list nodes by value with threshold K.
 92 Reverse Linked List II
 Given a linked list, reverse mth to nth nodes.
 109 Covert Sorted List to Binary Search Tree
 Converted a sorted linked list into a balanced BST.
 138 Copy List with Random Pointer
 O(1) space in 3 steps: 1) merge two lists into one and set random pointers in new nodes 2) walk list and modify random nodes 3) split list into origin lists.
 141 Linked List Cycle
 142 Linked List Cycle II
 O(n) time and O(1) space achieved by Floyd’s circle finding algorithm.
 143 Reorder List
 L(1)>L(2)>…>L(n1)>L(n) => L(1)>L(n)>L(2)>L(n1)…
 O(n) time and O(1) space. Reverse the second half and merge.
 147 Insertion Sort List
 206 Reverse Linked List
 328 Odd Even Linked List
 L(1)>L(2)>…>L(n1)>L(n) => L(1)>L(3)>…L(2)>L(4)…
 O(n) time and in place. Invariant: oddeven list + origin list.
 369 Plus One Linked List
 430 Flatten a Multilevel Doubly Linked List
 Preorder traversal.
 445 Add Two Numbers II
 708 Insert into a Cyclic Sorted List
 First find min/max of linked list. Then find maxmin or some increasing tuple.
Hash Table
Besides being an O(1) r/w table, hash tables are often used to save preprocessed results or find matching elements.
 1 Two Sum
 Given a number array, find all number pairs that sum to k.
 O(n) time.
 18 4Sum
 O(n^3) worst time because there might be Theta(n^3) answers.
 36 Valid Sudoku
 Validate a 9x9 sudoku.
 O(81) time.
 128 Longest Consecutive Sequence
 Given a number array, find the maximum length of a consecutive sequence.
 O(n) time. Unionfind also works.
 249 Group Shifted Strings
 Given a list of strings, sort them according to shifting equivalance classes.
 O(nk) time, where k is the maximum length of string element.
 299 Bulls and Cows
 4digit number guessing game, generate hints (correct numbers & correct places).
 325 Maximum Size Subarray Sum Equals k
 O(n) time. Classical prefixsum.
 438 Find All Anagrams in a String
 Sliding window, maintain rest character set.
 454 4Sum II
 Given four number arrays, count number of quadruples that sum up to zero.
 O(n^2) time by count two sums first.
 532 Kdiff Pairs in an Array
 Find number of (a,b) pairs in an array that ab is k.
 567 Permutation in String
 Similar to 438.
 609 Find Duplicate File in System
 939 Minimum Area Rectangle
 Given (x, y) points, find minimum area of square constructed by four of them.
 O(n^2) time by checking point pairs as diagonal points. Find rest in hashset.
 966 Vowel Spellchecker
 Implement a dictionary supporting capitalization and vowel corrections.
 Store normalized representations in a hashset.
 1001 Grid Illumination
 Given lights on a board, shutting off a light will shut down eight lights around it. A light will enlight x axis, y axis and a cross. Finish light shut offs and enlighted or not queries.
 Sort lights into four classes: x, y, x+y, xy.
 1002 Find Common Characters
 Find common characters in given words.
Two Pointers
Two pointers sometimes is an implementation of monostack or monoqueue. 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.
 3 Longest Substring Without Repeating Characters
 O(n) time and O(1) space. Mono function is increasing. When there is repeat, moving is bad.
 11 Container With Most Water
 Given several plunks standing on an Xaxis, calculate the maximum volume of bucket formed by two plunks.
 O(n) time and O(1) space. The function is goingtocenter mono.
 15 3Sum
 O(n^2) time. Sort then use two pointers.
 16 3Sum Closest
 3Sum but return the triplet whose sum is closest to a target.
 O(n^2) time. Sort and two pointers.
 26 Remove Duplicates from Sorted Array
 27 Remove Element
 30 Substring with Concatenation of All Words
 Given a string and a word (all same length) list, find all substrings that are made up of the whole word list.
 O(nm) time and O(m) space, where n is length of string and m is length of word. Wordlevel two pointer, start from 0  m1.
 DP is also possible. For each index, save the longest valid substring ended with it, and corresponding word usages.
 42 Trapping Rain Water
 Given several plunks standing on an Xaxis, caculate the maximum volume of water it can trap.
 O(n) time by monostack.
 O(n) time by DP. The amount of water loadable at each point is determined by leftMax and rightMax.
 O(1) space by two pointers from two ends. leftMax and rigthMax is goingtocenter mono, thus volume is mono.
 75 Sort Colors
 Sort sequences consisting of 1, 2, 3.
 O(n) time and one pass by two pointers. Not related to mono things.
 76 Minimum Window Substring
 Given S and T, find minimum window in S containing AT LEAST all letters in T.
 O(n) time by two pointers.
 80 Remove Duplicates from Sorted Array II
 Given a sorted array, remove redundant elements such that no element appears more than 2 times.
 O(n) time by two pointers. Not related to mono things.
 159 Longest Substring with At Most Two Distinct Characters
 Easy O(n) time two pointers.
 209 Minimum Size Subarray Sum
 O(n) time by two pointers.
 O(nlog(n)) time by binary search the minimum size.
 259 3Sum Smaller
 O(n^2) time by sorting first. Similar to 3Sum Closest.
 287 Find the Duplicate Number
 O(n) time and O(1) space by Floyd Cycle Detection Algorithm. No mono things.
 340 Longest Substring with At Most K Distinct Characters
 O(n) time and O(1) space, typical sliding window.
 424 Longest Repeating Character Replacement
 Given a string, one can at most alter k characters. Find the maximum length of repeat character string.
 O(n) time. Note that these k characters must be in a sliding window.
 Use percharacter queue also works.
 O(26) space, maintaining maximum character count ever encountered in the sliding window. The length of sliding window is mono increasing.
 457 Circular Array Loop
 Find circles in integer array. Floyd Cycle Detection Algorithm.
 Pitfall: only mark elements as zero when the case is confirmed invalid.
 481 Magical String
 Build recursive string: 1221121… > 1 22 11 2 1 > 12211…
 Generate string according to its prefix.
 611 Valid Triangle Number
 Sort and use two pointers to find solve “two sum > nums[largestIdx]”
 713 Subarray Product Less Than K
 828 Unique Letter String
 Define UNIQ(s) is the number of unique letters in a string. Find sum of UNIQ of all substrings of S.
 At each step, calculate UNIQ of substrings ending by that character. Maintain a character index map.
 904 Fruit Into Baskets
 Find longest subarray with at most 2 distinct numbers.
 986 Interval List Intersections
 Given two nonintersect interval lists, calculate their intersected result.
 Merge sort. Always throw the interval with lower end and keep the rest interval.
 992 Subarrays with K Different Integers
 Prefixsumlike method, Find number of subarrays with AT MOST K different integers.
 1004 Max Consecutive Ones III
 Given a 01 array, one can change 0 to 1 at most K times. Find maximum consecutive ones.
 1031 Maximum Sum of Two NonOverlapping Subarrays
 Given a number array, find maximum of two nonoverlapping Mlength and Llength subarray.
 Maintain last M and L length sum and maximum sum of M and L length arrays.
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.
 5 Longest Palindromic Substring
 O(n^2) time easy solution.
 O(nlog(n)) time suffix array.
 O(nlog(n)) string hash.
 6 ZigZag Conversion
 8 String to Integer (atoi)
 12 Integer to Roman
 13 Roman to Integer
 Scan right to left, keep maximum roman digit accessed, do add or minus according to the maximum.
 Roman numbers are actually mono stacks.
 14 Longest Common Prefix
 17 Letter Combinations of a Phone Number
 28 Implement strStr()
 38 Count and Say
 1 > one one > 11 > two one > 21 > one two one one > 1211 > one one one two two one > 111221 …
 43 Multiply Strings
 49 Group Anagrams
 If word A is word B’s permutation, then they’re anagrams of each other.
 58 Length of Last Word
 Scan from the end.
 65 Valid Number
 First remove space, then check invalid characters, finally sequentially try to grab sign, int, dot, frac and enum part.
 67 Add Binary
 68 Text Justification
 151 Reverse Words in a String
 158 Read N Characters Given Read4 II  Call multiple times
 Buffer reads in a queue.
 161 One Edit Distance
 165 Compare Version Numbers
 214 Shortest Palindrome
 Given a string, find minimum length of palindrome formed by adding characters in front of it.
 KMP, match from tail using head as pattern.
 227 Basic Calculator II
 Evaluate expression without parentheses.
 387 First Unique Character in a String
 418 Sentence Screen Fitting
 Similar to text justification. Need to find endposition circles.
 459 Repeated Substring Pattern
 Find whether a string is made up by smaller repeating units.
 Validate whether s is in (s+s)[1:1]. This basically checks if the s can be represented by a rotation of itself. If yes, then s is repeated. (GCDlike proof)
 Use KMP cyclic segment (i  next[i] for 1 <= i <= sLen).
 468 Validate IP Address
 680 Valid Palindrome II
 Find whether a string can become a palindrome if at most one character can be deleted.
 722 Remove Comments
 937 Reorder Log Files
 1016 Binary String With Substrings Representing 1 To N
 Given a 01 sequence, find minimum N whose binary representation is not substring of it.
 Just enumerate all numbers presented in the sequence.
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 quicksortlike quickselect.
 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 smallhalf maxheap and largehalf 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 kth 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 cannottrap 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 maxheap (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.
 20 Valid Parentheses
 32 Longest Valid Parentheses
 O(n) time, expand by context free grammar: <exp> = (<exp>)  <exp><exp>  null
 O(n) time, simple scan from two ends.
 71 Simplify Path
 Simplify a UNIX path. Use stack to handle /../../ == / cases.
 84 Largest Rectangle in Histogram
 Mono stack.
 150 Evaluate Reverse Polish Notation
 224 Basic Calculator
 Evaluate expressoin containing parentheses and +.
 239 Sliding Window Maximum
 Mono queue, similar with Largest Rectangle in Histogram.
 O(nk) time using trie, where k is the length of int.
 316 Remove Duplicate Letters
 Given a sequence, remove duplicate letters to get a lexicographical smallest subsequence.
 O(n) time using mono stack. Similar to Create Maximum Number. Do not stackin character that already exists in answer because that will never make answer better.
 321 Create Maximum Number
 Given two digit arrays, create maximum klength number using digits from them. Order is preserved.
 O(nk) time by mono stack. Enumerate number of digits picked from the two array. Bigger digit is always better to come first, leading to mono stack solution.
 331 Verify Preorder Serialization of a Binary Tree
 O(n) time and space using stack.
 O(1) space, maintain binary tree’s capacity. Leaf (nullptr) decreases capcity while other decrease one then increase two.
 385 Mini Parser
 Parse JSON like strings containing only numbers and lists.
 388 Longest Absolute File Path
 394 Decode String
 Decode strings like “3[a2[c]]” > accaccacc.
 402 Remove K Digits
 Simplified Create Maximum Number on a single number.
 439 Ternary Expression Parser
 Evaluate nested ternary expression, like F?1:T?3:4 == 3.
 503 Next Greater Element II
 Given a number array, for each number find circular first next larger number.
 Loop twice.
 636 Exclusive Time of Functions
 Implement a tiny perf tool.
 726 Number of Atoms
 Calculate number of atoms in molecular expression, like K4(ON(SO3)2)2 > K4N2O14S4.
 Store atom count as stack element. Do sum for digits after atoms and multiplication after ‘)’s.
 735 Asteroid Collision
 Given asteroids with left/right speed, calculate final state.
 739 Daily Temperatures
 Given temperature array, for each day find first higher temprature index.
 772 Basic Calculator III
 Calculator supporting +,  (including unary), *, / and ().
 Use lastIsNumber to identify unary operators.
 853 Car Fleet
 Sort by arrival time, and use mono stack.
 946 Validate Stack Sequences
 O(n) space by stack emulation, O(1) space reuse input.
 1003 Check If Word Is Valid After Substitutions
 If S is a valid string and X+Y=S, then X+”abc”+Y is valid as well. Find whether a string is valid.
 1019 Next Greater Node In Linked List
 Given a linked list, for each node find first value larger than it and after than it.
 Use mono stack.
 1028 Recover a Tree From Preorder Traversal
 Recover tree from sequences like “12–3–45–6–7”.
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[M1][N1]  isStar(p[N]) && (F[M][N1]  (isDot(p[N])  s[M] == p[N]) && F[M1][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[M1][N1]  isStar(p[N]) && (F[M][N1]  F[M1][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 leftup to rightdown.
 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 leftup to rightdown, 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[M1][N1] + !(s1[M] == s2[N]), F[M][N1] + 1, F[M1][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[x1][y] + 1 if R[x][y] == 1 else 0 L[x][y] = min(L[x1][y], maxL[x][y]) R[x][y] = min(R[x1][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][n1] + a[m] == b[n] ? F[m1][n1] : 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: ith house not robbed or (i+1)th house not robbed.
 221 Maximal Square
 O(mn) time. 2D/0D. F[M][N]: maximal square with rightdown (M, N). F[M][N] = min(F[M1][N1]+1,F[M1][N]+1,F[M][N1]+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 housecolor 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 subproblems welldefined, 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 1bit 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 killingcross bomb, find maximum enemy can be killed.
 O(mn) time, maximum continous length. O(n) space, walk leftright and updown and maintain updown 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 SiSj or SjSi.
 Note that such subset must be a chain that S1S2…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 k1, 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 equalsum 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 reusage. 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 01 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][n1], F[m+1][n1]+2 if s[m]==s[n])
 518 Coin Change 2
 Complete knapsack.
 523 Continuous Subarray Sum
 Given nonnegative 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. Prefixsum.
 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 leftup to rightdown and back to leftup.
 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
 Multidimension 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 Mth 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 nonless number, even index jump to nearest nongreater 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 1day, 7day and 30day 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 mth to nth stone merged into k piles.
 1026 Maximum Difference Between Node and Ancestor
 Tree DP on subtree 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 increaseoneletter sequence like a > ab > acb.
 DP on different wordlength layers.
Binary Search
Binary search can be used to optimize DP updating process.
Binary search on answer is a useful technique.
 4 Median of Two Sorted Arrays
 O(log(min(m, n))) time. Determine array B’s index using array A’s index.
 33 Search in Rotated Sorted Array
 No duplicate, four cases: <<, <>, ><, and >> (not possible).
 34 Find First and Last Position of Element in Sorted Array
 35 Search Insert Position
 50 Pow(x, n)
 69 Sqrt(x)
 74 Search a 2D Matrix
 The matrix is a sorted array if rows are concatenated.
 81 Search in Rotated Sorted Array II
 With duplicate, O(n) worst time.
 Nine cases combined by <, = and >. >> is not possible and == is unknown.
 153 Find Minimum in Rotated Sorted Array
 154 Find Minimum in Rotated Sorted Array II
 162 Find Peak Element
 Peak element is greater than its neighbors. nums[i] != nums[i + 1]. nums[1] = nums[n] = inf.
 Invariant: search interval’s two ends are always lower ones.
 222 Count Complete Tree Nodes
 Binary search on leaf positions according to depth.
 240 Search a 2D Matrix II
 The matrix’s rows and columns are sorted.
 O(m + n) time, walk from rightup.
 O(min(m, n)) time divide & conquer.
 275 HIndex II
 Given citations sorted in ascending order, find Hindex.
 302 Smallest Rectangle Enclosing Black Pixels
 O(mlog(n)) time by binary search. Project black pixels onto x and y dimensions, and search the bound.
 327 Count of Range Sum
 Given a number array, count different range sums.
 O(nlog(n)) time by using balanced BSTalike data structure. Trie is also ok.
 By introducing prefix sums, this is a typical 1D/1D DP problem whose updating process can be optimized by BIT. Need discretization.
 410 Split Array Largest Sum
 Given a number array, split it into m subarrays, find the minimum of the maximum of subarray sum.
 O(n*sumofarray) time, binary search on answer.
 O(nmlog(n)) time, 2D/1D DP, updating process optimized with binary search.
 436 Find Right Interval
 Given intervals, for each interval find smallset one who is at the right of it.
 O(nlog(n)) time, use set’s lower_bound.
 540 Single Element in a Sorted Array
 Given array like 1 1 2 2 3 4 4 5 5, find 3.
 Binary search on 2*k indices. Find whether nums[i] == nums[i + 1].
 658 Find K Closest Elements
 Binary search for origin and expand.
 1011 Capacity To Ship Packages Within D Days
 Packages are given in a number array.
Binary Search Tree
 218 The Skyline Problem
 O(nlog(n)) time using line sweeping and map.
 220 Contains Duplicate III
 Given a number array, find if there are two elements nums[i] and nums[j] i.e. abs(ij)<=k and (nums[i]nums[j])<=t.
 Use set::lower_bound. Enumerate window at size K.
 230 Kth Smallest Element in a BST
 Save count in node to keep log(n) query time.
 352 Data Stream as Disjoint Intervals
 Given number stream, merge them into intervals.
 450 Delete Node in a BST
 480 Sliding Window Median
 Use cpp multiset.
 938 Range Sum of BST
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”, rearrange 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 swapinvariant problem.
 435 Nonoverlapping Intervals
 Given intervals, determine minimum intervals needed removing to make intervals nonoverlapping.
 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 Nth (N>K) sampling, keep the old items with probability 1  K/N. Easy proof by math induction.
FisherYates algorithm: Each time select one element from rest K elements. Selection is implemented by swapping.
Game theory: minimax, NIM problem, SpragueGrundy 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).
 MillerRabin.
 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
 Nperson 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
 Nontrivial O(n^2) solution by SpragueGrundy function.
 319 Bulb Switcher
 There is a bulb array. There is n operations, and the ith operation will switch ki bulbs. Calculate whether kth 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 FisherYates 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] + … + (n1) * Bk[n1]
 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 09’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 n1 numbers, find minimum moves to make all elements equal.
 Increase n1 == 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 reuse 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 allonesequence in base k.
 Enumerate onesequence’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 Nonoverlapping Rectangles
 Areaweighted 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 nonlargest 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(pa)(pb)(pc)).
 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 kth 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 (maxmin) 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 1seq 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
 273 Integer to English Words
 Divide integer to 3length segments.
 395 Longest Substring with At Least K Repeating Characters
 O(n) time, recursively expell letters with count less than target.
UnionFind
 261 Graph Valid Tree
 Given edges, judge whether it’s a tree.
 305 Number of Islands II
 Islands are popping out of a grid sea. Give number of islands after each popping.
 Maintain a parent set, do erase and insert during each union.
 323 Number of Connected Components in an Undirected Graph
 547 Friend Circles
 721 Accounts Merge
 785 Is Graph Bipartite?
 For each node, merge all adjacent nodes. Then check for each edge.
 803 Bricks Falling When Hit
 Reversetime unionfind.
 947 Most Stones Removed with Same Row or Column
 Given stones on a 2D plane, one can remove a stone if there are other stones sharing the same row or column. Find maximum removes.
 Union points by row or column.
 952 Largest Component Size by Common Factor
 Find the largest connected component of a graph, where there is an edge if two nodes share a common factor > 1.
 O(N*sqrt(W)) time, where W is the maximum value in input array.
 990 Satisfiability of Equality Equations
 Given equations like a==b, b!=c, a==c, find whether the equation set is satisfiable.
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
StackBased 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
 94 Binary Tree Inorder Traversal
 98 Validate Binary Search Tree
 99 Recover Binary Search Tree
 Two elements of a BST is swapped. Find them out.
 O(1) space by Morris Traversal.
 100 Same Tree
 Check whether two binary trees are the same.
 102 Binary Tree Level Order Traversal
 Sort tree’s nodes into different depths.
 103 Binary Tree Zigzag Level Order Traversal
 Sort tree’s nodes into different depths, but switch direction on each depth level.
 105 Construct Binary Tree from Preorder and Inorder Traversal
 O(n) time and O(n) space, record val’s inorder index.
 106 Construct Binary Tree from Inorder and Postorder Traversal
 113 Path Sum II
 Find all root to leaf paths that nodes sum to a target.
 114 Flatten Binary Tree to Linked List
 Flatten binary tree to preorder linked list.
 O(n) time and O(1) space, use Morris Traversal and link left/right subtree when root is met again.
 116 Populating Next Right Pointers in Each Node
 Given a perfect binary tree, link siblings together.
 Invariant: upper level is already linked.
 117 Populating Next Right Pointers in Each Node II
 Binary tree not perfect.
 129 Sum Root to Leaf Numbers
 Each node is a digit, find sum of numbers formed by rootleaf paths.
 144 Binary Tree Preorder Traversal
 145 Binary Tree Postorder Treversal
 Morris Traversal. Reverse of leftright mirrored preorder is postorder.
 156 Binary Tree Upside Down

Do the following transformation recursively: (all right nodes are whether leaf with sibling or nullptr)
1 4 2 3 => 5 2 4 5 3 1

 173 Binary Search Tree Iterator
 Average O(1) time and O(h) memory for next() and hasNext().
 Can delete visited nodes, since it’s single directional visiting.
 199 Binary Tree Right Side View
 236 Lowest Common Ancestor of a Binary Tree
 250 Count Univalue Subtrees
 Find the number of univalue subtrees, where all nodes are of the same value.
 255 Verify Preorder Sequence in Binary Search Tree
 O(n) time by iterative traversal.
 O(1) space by monostack and reuse input vector. Mono stack saves nodes not visited yet, thus all nodes less than current value must be visited (popped), because they can only be in left trees.
 Preorder sequence: DDDDIIIDDDDIIIIDDD…, keep a lowest bound for popped ones, they’re left subtrees already visited.
 272 Closest Binary Search Tree Value II
 Given a BST and target value, find k nearest neighbor.
 O(klog(n)) time using stackbased iterative traversal.
 Cannot delete visited nodes, because it’s bidirectional visiting.
 285 Inorder Successor in BST
 297 Serialize and Deserialize Binary Tree
 298 Binary Tree Longest Consecutive Sequence
 Given a binary tree, find the length of longest consecutive sequence going from up to down.
 O(n) time, simple tree DP.
 314 Binary Tree Vertical Order Traversal

Given a binary tree, output its vertical order traversal. For example:
2 3 4 => 1 3 2 5 0 4 6 1 50 6

Traverse the tree and emit (node, position) pairs. O(n) time can be achieved if using hashmap.

 337 House Robber III
 Rob on a tree, adjacent nodes cannot be robbed.
 O(n) time, typical tree DP.
 366 Find Leaves of Binary Tree
 Remove leaves of a binary tree step by step.
 Tree DP. for each node calculate it’s shortest path to leaf.
 404 Sum of Left Leaves
 426 Convert Binary Search Tree to Sorted Doubly Linked List
 Convert BST to a sorted list, left=prev, right=next.
 Simple divide and conquer.
 428 Serialize and Deserialize Nary Tree
 Simple recursion.
 431 Encode Nary Tree to Binary Tree
 Left(first) children and rightsibiling.
 449 Serialize and Deserialize BST
 Use 1,,1,,, like preorder traversal string.
 545 Boundary of Binary Tree
 Maintain isLeftBound and isRightBound in preorder traversal.
 742 Closest Leaf in a Binary Tree
 Find the value of nearest leaf to some target node.
 Save nearest leaf for nodes on the roottotarget path.
 Convert tree to graph.
 951 Flip Equivalent Binary Trees
 965 Univalued Binary Tree
 971 Flip Binary Tree To Match Preorder Traversal
 987 Vertical Order Traversal of a Binary Tree
 Similar to 314.
 993 Cousins in Binary Tree
 Two nodes are cousins if they are at the same depth but have different parents. Find whether two nodes are cousins.
 998 Maximum Binary Tree II
 A maximum tree is whose root is alwasy the largest. Given a number array, a max tree can be constructed by recursively pick maximum and build left/right sub arrays. Now append a new number to origin array, insert the number into the origin maximum tree.
 1008 Construct Binary Search Tree from Preorder Traversal
Sort
Merge sort: O(nlog(n)) time. O(log(n)) space with recursion, O(1) space with bottomup.
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.
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 bottomup sorting.
 179 Largest Number
 Given a list of nonnegative 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, 30309 vs. 30930.
 274 HIndex
 Given a citation list, find the author’s Hindex.
 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 NPhard. See Wikipedia
 973 K Closest Points to Origin
 1057 Campus Bikes
 Given positions of bikes and persons, match shortest manhattan distances.
 Sort bikeperson 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 10length 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 UTF8 Validation
 Emulation using bit manipulation.
Search
 51 NQueens
 52 NQueens II
 126 Word Ladder II
 Output all shortest transformations. Record previous nodes leading to shortest path in BFS. Kind of like DP.
 127 Word Ladder
 Given equallength word list and beginWord and endWord, find minimum steps to change beginWord to endWord. Each change is at most one character.
 130 Surrounded Regions
 Given grids filled by X and O, turn all surrounded O into X.
 133 Clone Graph
 Deep copy a graph.
 200 Number of Islands
 Flood filling.
 286 Walls and Gates
 Given grids made by walls, gates and empty room, fill each room with shortest path length to any gate.
 O(mn), start from all zero points.
 301 Remove Invalid Parentheses
 Caculate invalid left and right brackets first by simple scanning. Then brute force DFS.
 317 Shortest Distance from All Buildings
 Given a grid with several buildings and obstacles. Find the best home location with minimum sum of distances to buildings.
 BFS from all buildings and sum the distances.
 364 Nested List Weight Sum II
 Given a nested list, find weighted sum of all nodes. Weight is depth.
 386 Lexicographical Numbers
 Generate lexicographical ordered number list from 1 to n.
 Do multiply 10 or plus one each time. After plus one, remove trailing zeros.
 397 Integer Replacement
 Given a number n, if n is even can do n » 1, else can do n+1 or n1. Find least step to 1.
 Simple BFS.
 Can do greedy except for n == 3.
 417 Pacific Atlantic Water Flow
 Given a grid, water flows to nongreater grids. Find all grids that can flow to both upleft and rightdown.
 Simple BFS. Memo search is not valid because states are not strictly mono.
 433 Minimum Genetic Mutation
 Same as word ladder.
 440 Kth Smallest in Lexicographical Order
 Given 1 and n, find kth smallest in lexicographical order.
 Walk on a decimal tree, find subtree sizes limited in upper bound.
 465 Optimal Account Balancing
 People have debts among each other. Find minimum steps to clear the debt.
 O(n!) time, calculate perperson surplus/deficit, then DFS.
 473 Matchsticks to Square
 Multiple knapsacks.
 478 Generate Random Point in a Circle
 Rejection sampling.
 488 Zuma Game
 Zuma game like “WRRBBW” > “WRR(R)BBW” > “WBBW”… Given start state and balls in hand, find minimum steps to eliminate all balls.
 Simple DFS, memo state and balls in hand.
 489 Robot Room Cleaner
 Given an unknown maze and a robot with move() and turnRight(), clean the room.
 DFS with relative position visited memo.
 490 The Maze
 Ball rolling in a maze. Given start and end point, judge whether the ball can stop at end point.
 Simple BFS.
 491 Increasing Subsequences
 Given a number list, find all increasing subsequences.
 For each position find possible next indices, then DFS.
 529 Minesweeper
 Simple BFS out all mines.
 542 01 Matrix
 Given 01 matrix, find distance of nearest 0 for each 1.
 BFS from all 0, or DP from four directions.
 679 24 Game
 Save results that can be calculated from a certain number set.
 694 Number of Distinct Islands
 Use relative offset of points as island ID.
 695 Max Area of Island
 698 Partition to K Equal Sum Subsets
 Similar to “Sticks” in POJ.
 773 Sliding Puzzle
 The eightdigit problem.
 797 All Paths From Source to Target
 909 Snakes and Ladders
 Maze with portals.
 958 Check Completeness of a Binary Tree
 Maintain a noChild during BFS. Mark it when first nonfull node is encountered.
 967 Numbers With Same Consecutive Differences
 980 Unique Paths III
 Hamiltonian path.
 994 Rotting Oranges
 There are oranges on a grid, and a rotting orange causes four neighbors to rot. Find minimum time for all oranges are rot.
 1091 Shortest Path in Binary Matrix
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.
 207 Course Schedule
 210 Course Schedule II
 Topological sort.
 269 Alien Dictionary
 Given a sorted word list of a new alphabet, recover character sequence.
 Topological sort.
 310 Minimum Height Trees
 Given a tree, find the root set where it has minimum height.
 Topological sort, remove leaves.
 332 Reconstruct Itinerary
 O(n) time since the problem is finding Eularian path.
 399 Evaluate Division
 Use floyd. Similar to currency exchange.
 Unionfind is also ok. For each a/b=x, assume a=x and b=1. If a and b already have assumed values, update them. Unionfind is used for this update.
 444 Sequence Reconstruction
 Given some sequences, judge whether a supersequence S can be uniquely constructed from those sequences.
 Topological sort.
 743 Network Delay Time
 Given a network and source node, find time for all nodes to receive a message.
 BFS on priority queue or Dijkstra.
 787 Cheapest Flights Within K Stops
 BFS on priority queue.
 863 All Nodes Distance K in Binary Tree
 Convert tree to a graph.
 1136 Parallel Courses
 Topological sort.
 1066 Campus Bikes II
 Similar to 1057, but requires overall manhattan distance sum minimum.
 DFS or use max flow. Note for cost x we can use max_costx to replace x because there are ways personnum edges.
Trie
 164 Maximum Gap
 Given a number array, find maximum gap in sorted array.
 O(32n) time with trie.
 O(n) time by pigeon hole principle. Make buckets i.e. at least one bucket is empty, then the empty bucket(s) must be maximum adjacent. Also maintain min/max for each bucket.
 208 Implement Trie (Prefix Tree)
 211 Add and Search Word  Data structure design
 Given word dict, support lookup supporting dot wildcard. Trie with DFS.
 212 Word Search II
 Given a word list, find all words appearing in the grid.
 Use Trie to build a dict, then DFS.
 336 Palindrome Pairs
 Given a word list, find all word pairs that can be combined into a palindrome.
 O(nk^2) time, using trie to find the other end of a palindrome.
 Use hashset to find also works.
 411 Minimum Unique Word Abbreviation
 Given a word and a dictionary, find the smallest abbr. of the word (“apple”>“a4”, etc.) that doesn’t conflict with the dictionary. A number’s length is 1.
 O(mn*2^m) time, where n*2^m <= 2^20. BFS with trie. BFS all nodes when in number region.
 421 Maximum XOR of Two Numbers in an Array
 O(n) time, DFS on trie.
 425 Word Squares

Given a word list, find all word squares constructable. A word square is like
ball area lead lady

Backtracking with validation by trie.

 616 Add Bold Tag in String
 Add bold tag for all words appearing in dictionary.
 KMP on all words in dictionary is OK too.
 642 Design Search Autocomplete System
 Store most frequent items on Trie nodes.
 677 Map Sum Pairs
 Insert(key, val), Sum(prefix)
Design
 146 LRU Cache
 Double linked list + hashmap.
 244 Shortest Word Distance II
 Given word list and two words, find minimum distance of their indices. There might be many queries.
 O(n) time and space with hashmap and merge list.
 251 Flatten 2D Vector
 hasNext and next on a 2D vector.
 271 Encode and Decode Strings
 281 Zigzag Iterator
 Given two number lists, the iterator should return their elements alternatively.
 284 Peeking Iterator
 Create a temporary iterator and find its next.
 Cache next element.
 288 Unique Word Abbreviation
 341 Flatten Nested List Iterator
 hasNext and next. Use stack to store iterators.
 346 Moving Average from Data Stream
 348 Design TicTacToe
 O(1) time for each move and O(n) space. Save rowCount, colCount and crossCount.
 353 Design Snake Game
 362 Design Hit Counter
 hit(timestamp), getHits(<=timestamp). Only 5minute valid interval.
 O(1) time for both operations. Use prefix counts and deleted counts.
 379 Design Phone Directory
 get(), check(), release() on an array.
 Use a heap pointer and a free list.
 380 Insert Delete GetRandom O(1)
 Swap deleted one with the last one.
 381 Insert Delete GetRandom O(1)  Duplicates allowed
 Keep a set of indices instead of a single index.
 432 All O`one Data Structure
 Inc(key), Dec(key), GetMaxKey(), GetMinKey().
 460 LFU Cache
 Use double linkedlist for frequency list and recent list. Each frequency list node contains a recent list.
 push_front for frequencylist put new key, earse for get key, insert for frequency list change. Use get in put to add frequency.
 535 Encode and Decode TinyURL
 Use (26+26+10)base number.
 622 Design Circular Queue
 635 Design Log Storage System
 Given logs coming in timestamp order, support storage and range query by different granularity.
 Use trie, maintain isUpperBound and isLowerBound.
 855 Exam Room
 Implement seat() and leave() for a row of chairs. seat() will choose the seat that maximize the distance to others.
 Maintain intervals sorted by maximum distance possible for seat() and by left end for leave().
 981 Time Based KeyValue Store
 Design a keyvalue store, supporting read latest value before some timestamp.
 O(1) set and O(log(n)) read. use map’s lower_bound to search timestamp.
Segment Tree & Binary Index Tree
 307 Range Sum Query  Mutable
 308 Range Sum Query 2D  Mutable
 Quad tree.
 2D BIT.
 315 Count of Smaller Numbers After Self
 Instrumented merge sort also do.
 Maintain a sorted array and do binary search in it also do.
 391 Perfect Rectangle
 Check whether several small rectangles exactly merge into a bigger one.
 O(nlog(n)) time by line sweeping and segment tree.
 O(n) by counting corners.
 427 Construct Quad Tree