LeetCode Problem Summary
Important mind tags
 Prefixsum.
 Greedy by sorting.
 For dense problems, search with memo is much slower (~10x) than DP.
Array
 34 Find First and Last Position of Element in Sorted Array
 41 First Missing Positive
 Put numbers in their place.
 48 Rotate Image
 54 Spiral Matrix
 59 Spiral Matrix II
 73 Set Matrix Zeros
 O(mn) time and O(1) space.
 163 Missing Ranges
 Mind overflow.
 169 Majority Element
 O(n) time and O(1) space achieved by Boyer Moore Vote algorithm.
 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.
 245 Shortest Word Distance III
 289 Game of Life
 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.
 950 Reveal Cards In Increasing Order
 961 NRepeated Element in Size 2N Array
 Boyer Moore Vote.
 962 Maximum Width Ramp
Backtracking
 Permutations and combinations on unique/repeating number sets
 22 Generate Parentheses
 37 Sudoku Solver
 39 Combination Sum
 40 Combination Sum II
 46 Permutations
 47 Permutations II
 60 Permutation Sequence
 77 Combinations
 78 Subsets
 79 Word Search
 89 Gray Code
 90 Subsets II
 93 Restore IP Addresses
 131 Palindrome Partitioning
 211 Add and Search Word  Data structure design
 216 Combination Sum III
 254 Factor Combinations
 267 Palindrome Permutation II
 320 Generalized Abbreviation
 DP or bit manipulation also work.
 351 Android Unlock Patterns
Linked List
 General scheme to reverse linked list
 before = nullptr
 oldHead = head, head = head>next, oldHead>next = before, before = oldHead
 2 Add Two Numbers
 Add two numbers represented by linked list.
 19 Remove Nth Node From End of List
 O(n) in one pass: two pointers, the distance between which is N.
 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
 25 Reverse Nodes in kGroup
 61 Rotate List
 82 Remove Duplicates from Sorted List II
 86 Partition List
 92 Reverse Linked List II
 109 Covert Sorted List to Binary Search Tree
 138 Copy List with Random Pointer
 O(1) space by making origin>new single lists.
 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.
 147 Insertion Sort List
 328 Odd Even Linked List
 369 Plus One 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.
 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.
 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.
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.
 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.
 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.
String
 5 Longest Palindromic Substring
 O(n^2) time easy solution.
 O(nlog(n)) time suffix array.
 6 ZigZag Conversion
 8 String to Integer (atoi)
 12 Integer to Roman
 17 Letter Combinations of a Phone Number
 43 Multiply Strings
 49 Group Anagrams
 68 Text Justification
 151 Reverse Words in a String
 161 One Edit Distance
 165 Compare Version Numbers
 227 Basic Calculator II
 937 Reorder Log Files
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.
 347 Top K Frequent Elements
 355 Design Twitter
 373 Find K Pairs with Smallest Sums
Stack
 71 Simplify Path
 84 Largest Rectangle in Histogram
 O(n) time in another DP solution, for each stick save lessThanLeft and lessThanRight.
 94 Binary Tree Inorder Traversal
 103 Binary Tree Zigzag Level Order Traversal
 144 Binary Tree Preorder Traversal
 150 Evaluate Reverse Polish Notation
 173 Binary Search Tree Iterator
 Average O(1) time and O(h) memory for next() and hasNext().
 224 Basic Calculator
 239 Sliding Window Maximum
 Monotonic queue, similar with 84.
 O(nk) time using trie, where k is the length of int.
 316 Remove Duplicate Letters
 O(n) time using monoincreasing stack.
 331 Verify Preorder Serialization of a Binary Tree
 341 Flatten Nested List Iterator
 388 Longest Absolute File Path
 394 Decode String
 946 Validate Stack Sequences
 Rule based solution.
Dynamic Programming
1D/0D, 1D/1D (optimization to O(nlog(n))), 2D/0D, 2D/1D (parallelogram inequation), etc.
Digit DP, Tree DP, Knapsack, State compression, etc.
 10 Regular Expression Matching
 32 Longest Valid Parentheses
 Simple scan from two ends also works.
 44 Wildcard Matching
 There is also an O(1) space greedy solution, greedily matches strings containing ‘az’ and ‘?’.
 62 Unique Paths
 63 Unique Paths II
 64 Minimum Path Sum
 72 Edit Distance
 85 Maximal Rectangle
 Based on Largest Rectangle in Histogram or for each point DP on maxHeight, maxLeft and maxRight.
 87 Scramble String
 91 Decode Ways
 95 Unique Binary Search Trees II
 96 Unique Binary Search Trees
 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
 115 Distinct Subsequences
 120 Triangle
 123 Best Time to Buy and Sell Stock III
 O(n) time O(n) space by scanning from two ends, O(1) space by DFA.
 124 Binary Tree Maximum Path Sum
 132 Palindrome Partitioning II
 O(n^2) time.
 O(n) space if we use palindrome info immediately instead of saving their positions.
 139 Word Break
 O(nm) time, where n is string length and m is maximum word length.
 140 Word Break II
 152 Maximum Product Subarray
 O(n) time.
 174 Dungeon Game
 188 Best Time to Buy and Sell Stock IV
 O(n) time and O(n) space by greedy and quick selection.
 213 House Robber II
 O(n) time.
 221 Maximal Square
 264 Ugly Number II
 O(n) time. Similar to USACO Humble Numbers.
 279 Perfect Squares
 300 Longest Increasing Subsequence
 O(nlog(n)) time achieved by 1D/1D update optimization, i.e. monotonous stack.
 304 Range Sum Query 2D  Immutable
 309 Best Time to Buy and Sell Stock with Cooldown
 O(n) time with DFA method.
 312 Burst Ballons
 In order to make subproblems welldefined, intervals should be closed.
 322 Coin Change
 329 Longest Increasing Path in a Matrix
 333 Largest BST Subtree
 Typical tree DP.
 334 Increasing Triplet Subsequence
 O(n) time and O(1) space.
 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
 O(n) time (no O(n) * sizeof(int)).
 343 Integer Break
 O(log(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.
 Easy optimization to O(nlog(n)), like LIS. Mind boundary conditions when sorting.
 357 Count Numbers with Unique Digits
 361 Bomb Enemy
 363 Max Sum of Rectangle No Larger Than K
 O(n^2 * mlog(m)) time using binary search in prefix sums.
 368 Largest Divisible Subset
 377 Combination Sum IV
 446 Arithmetic Slices II  Subsequence
 O(n^2) time.
 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.
 799 Champagne Tower
 Process rest champagne as a whole.
 940 Distinct Subsequences II
 O(1) space: iterate on number of subsequences ended with Mth character in alphabet.
 964 Least Operators to Express Number
 Radix problem.
 968 Binary Tree Cameras
 Typical tree DP.
 Tree (special graph) covering can be solved by greedy algorithm.
 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
Binary Search
 4 Median of Two Sorted Arrays
 Determine array B’s index using array A’s index.
 29 Divide Two Integers
 33 Search in Rotated Sorted Array
 50 Pow(x, n)
 74 Search a 2D Matrix
 81 Search in Rotated Sorted Array II
 O(n) worst time because of duplicate numbers.
 153 Find Minimum in Rotated Sorted Array
 154 Find Minimum in Rotated Sorted Array II
 162 Find Peak Element
 222 Count Complete Tree Nodes
 228 Summary Ranges
 230 Kth Smallest Element in a BST
 238 Product of Array Except Self
 240 Search a 2D Matrix II
 O(m + n) time.
 O(min(m, n)) time divide & conquer.
 275 HIndex II
 327 Count of Range Sum
 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.
 378 Kth Smallest Element in a Sorted Matrix
 O(n) time algorithm presented in paper “Selection in X + Y and matrices with sorted rows and columns”, where n is number of rows.
Binary Search Tree
 218 The Skyline Problem
 220 Contains Duplicate III
 Use set::lower_bound is sufficient.
 352 Data Stream as Disjoint Intervals
 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.
 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. If the time range is not big, O(n) time is possible by prefix sum.
 321 Create Maximum Number
 Given two digit arrays, create maximum klength number using digits from them. Order is preserved.
 O(nk) time by greedy. Enumerate number of digits picked from the two array. Bigger digit is always better to come first, leading to mono stack solution.
 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.
 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.
 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.
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: NIM problem, SpragueGrundy function, etc.
 7 Reverse Integer
 Mind overflow!
 9 Palindrome Number
 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.
 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.
 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.
 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.
 372 Super Pow
 Caculate a^b mod 1337, where b is very large.
 Use Chinese remainder theorem because 1337 = 7 * 191?
 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]
 949 Largest Time for Given Digits
 Given four digits, make up largest HH:MM time.
 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.
Divide and Conquer
 241 Different Ways to Add Parentheses
 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
 323 Number of Connected Components in an Undirected Graph
 947 Most Stones Removed with Same Row or Column
 952 Largest Component Size by Common Factor
 O(N*sqrt(W)) time, where W is the maximum value in input array.
Minimax
 375 Guess Number Higher or Lower II
 Follow up: expected loss instead of worst loss. Use probability to multiply worst cost in DP?
Tree
 98 Validate Binary Search Tree
 99 Recover Binary Search Tree
 Morris Traversal.
 102 Binary Tree Level Order Traversal
 105 Construct Binary Tree from Preorder and Inorder Traversal
 106 Construct Binary Tree from Inorder and Postorder Traversal
 113 Path Sum II
 114 Flatten Binary Tree to Linked List
 116 Populating Next Right Pointers in Each Node
 117 Populating Next Right Pointers in Each Node II
 129 Sum Root to Leaf Numbers
 145 Binary Tree Postorder Treversal
 Morris Traversal. Reverse of leftright mirrored preorder is postorder.
 156 Binary Tree Upside Down
 199 Binary Tree Right Side View
 236 Lowest Common Ancestor of a Binary Tree
 250 Count Univalue Subtrees
 255 Verify Preorder Sequence in Binary Search Tree
 O(n) time by iterative traversal
 O(1) time by monostack (this is a binary search tree) and reuse input vector.
 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
 366 Find Leaves of Binary Tree
 951 Flip Equivalent Binary Trees
 965 Univalued Binary Tree
 971 Flip Binary Tree To Match 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.
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, sort it i.e. A[0] < A[1] > A[2] < A[3] …
 O(n) time by swapping neighbors.
 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.
 969 Pancake Sorting
 Sort an array by reversing its prefixes.
 The minimum number question is NPhard. See Wikipedia
 973 K Closest Points to Origin
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
 127 Word Ladder
 130 Surrounded Regions
 133 Clone Graph
 200 Number of Islands
 207 Course Schedule
 210 Course Schedule II
 286 Walls and Gates
 O(mn), start from all zero points
 301 Remove Invalid Parentheses
 Caculate redundant left and right brackets first.
 332 Reconstruct Itinerary
 O(n) time since the problem is finding Eularian path.
 364 Nested List Weight Sum II
 386 Lexicographical Numbers
 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.
 967 Numbers With Same Consecutive Differences
Graph
 399 Evaluate Division
 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.
Trie
 164 Maximum Gap
 O(n) time.
 208 Implement Trie (Prefix Tree)
 212 Word Search II
 336 Palindrome Pairs
 O(nk^2) time, using trie to find the other end of a palindrome.
 Use hashset to find also works.
Design
 146 LRU Cache
 244 Shortest Word Distance II
 251 Flatten 2D Vector
 271 Encode and Decode Strings
 281 Zigzag Iterator
 284 Peeking Iterator
 Create a temporary iterator and fint its next.
 Cache next element.
 288 Unique Word Abbreviation
 348 Design TicTacToe
 O(1) time for each move and O(n) space.
 353 Design Snake Game
 362 Design Hit Counter
 O(1) time for both operations.
 379 Design Phone Directory
 380 Insert Delete GetRandom O(1)
 381 Insert Delete GetRandom O(1)  Duplicates allowed
Segment Tree & Binary Index Tree
 307 Range Sum Query  Mutable
 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.