Important mind tags

  • Prefix-sum.
  • Greedy by sorting.
  • For dense problems, search with memo is much slower (~10x) than DP.

Array

Backtracking

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. Union-find 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
    • 4-digit number guessing game, generate hints (correct numbers & correct places).
  • 325 Maximum Size Subarray Sum Equals k
    • O(n) time. Classical prefix-sum.
  • 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 mono-stack or mono-queue. Mono here means that, under the problem’s condition, the optimal value of left pointer is a mono function of right pointer, and vice versa. One needs to find out the mover changing condition, this is typically when moving more won’t make things better.

  • 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 X-axis, calculate the maximum volume of bucket formed by two plunks.
    • O(n) time and O(1) space. The function is going-to-center 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. Word-level two pointer, start from 0 - m-1.
    • 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 X-axis, caculate the maximum volume of water it can trap.
    • O(n) time by mono-stack.
    • 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 going-to-center 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

Heap

Stack

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.

Binary Search

Binary Search Tree

Greedy

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

  • 45 Jump Game II
    • Given an array with max jumping distance at each place. Caculate minimum step to the end.
    • O(n) time by greedy. Note that the minimum step to each index is mono increasing. Update jump number at each interval’s end. Intervals can be updated greedily.
  • 55 Jump Game
    • Given an array with max jumping distance at each place. Judge whether the end is reachable.
    • O(n) time by greedy.
  • 56 Merge Intervals
    • O(nlog(n)) time, sort by start position and merge.
  • 134 Gas Station
    • Given gas stations distributed on a circle, calculate whether one can travel around the circle once clockwise. Each gas station has limited gas volume.
    • O(n) time by greedy. Note that if SUM(cost) <= SUM(gas), there is always a solution, otherwise the circle can be divided into multiple parts where SUM(cost_part) > SUM(gas_part), contradiction. Then go around the circle and find the maximum point as start.
  • 135 Candy
    • Children in a line, each with a rating value. Higher rate has more candy than neighbors. Calculate minimum candy.
    • O(n) time and O(1) space by greedy. Find all mountains, mountain feets are all ones and mountain tops depends to the longer side.
  • 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 k-length 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 N-th (N>K) sampling, keep the old items with probability 1 - K/N. Easy proof by math induction.

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

Game theory: NIM problem, Sprague-Grundy 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
    • N-person team, there is a person that doesn’t know others but others all know him. Find it by sending knows(A, B) queries.
    • O(n) time. Each query at least strikes out one person.
  • 294 Flip Game II
    • Non-trivial O(n^2) solution by Sprague-Grundy function.
  • 319 Bulb Switcher
    • There is a bulb array. There is n operations, and the i-th operation will switch ki bulbs. Calculate whether k-th bulb is on.
    • Count factor numbers. Only square numbers are on.
  • 356 Line Reflection
    • Given several (x, y) points, find a vertical line made the pattern central symmetric.
    • O(n) time. The reflection line’s x is always (minX + maxX) / 2.
    • Double precision is not safe?
  • 360 Sort Transformed Array
    • Given f(x) = ax^2 + bx + c and a sorted array, given the sorted array mapped by f.
    • Find the root.
  • 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 Fisher-Yates algorithm.
  • 390 Elimination Game
    • Given an array from 1 to n, remove odd/even position numbers. Find the last number.
    • Each time all a mod b (b is 2^n) is eliminated. Infer ‘a’ each time.
  • 396 Rotate Function
    • Given A, Bk is A’s rotation, find maximum F(k) = 0 * Bk[0] + 1 * Bk[1] + … + (n-1) * Bk[n-1]
  • 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

Union-Find

Minimax

Tree

Sort

Merge sort: O(nlog(n)) time. O(log(n)) space with recursion, O(1) space with bottom-up. Heap sort: heapify O(n) time, poping O(nlog(n)). O(1) space. Quick sort: O(nlog(n)) average time.

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

  • 31 Next Permutation
    • O(n) time (worst case is reverse) and O(1) space by finding the least significant number a i.e. there is b less significant than b and a < b.
    • Simulating the DFS stack and judging at each depth whether the chose one is the maximum in possible number set also works.
  • 57 Insert Interval
    • O(nlog(n)) time by sorting and merge.
    • O(n) time by direct insert.
  • 148 Sort List
    • O(nlog(n)) time by merge sort. O(1) space by bottom-up sorting.
  • 179 Largest Number
    • Given a list of non-negative integers, concatenate them into the largest number.
    • O(nlog(n)) time by custom sorting. For any two numbers, compare which should be the first to form a larger number when they form a new number. For example, 30|309 vs. 309|30.
  • 274 H-Index
    • Given a citation list, find the author’s H-index.
    • O(nlog(n)) time by sorting
    • O(n) time by radix sorting. Any citation larger than n can be treated as n.
  • 280 Wiggle Sort
    • Given a sorted array A, 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 NP-hard. 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 10-length substring occuring more than once.
    • Use bitset to accelerate.
  • 201 Bitwise AND of Numbers Range
    • Find the most significant bit that two numbers differ.
  • 260 Single Number III
    • Given an array, all elements appear twice except two elements appear once. Find the two numbers.
    • O(n) time and O(1) space. The two numbers must differ in some bit. Divice the whole array according to the bit, and the subproblem is Single Number I.
  • 318 Maximum Product of Word Lengths
    • Given a list of words, find maximum length product of two words having no common characters.
    • O(n^2) time, use bit manipulation for acceleration.
  • 393 UTF-8 Validation
    • Emulation using bit manipulation.

Search

Graph

  • 399 Evaluate Division
    • Union-find is also ok. For each a/b=x, assume a=x and b=1. If a and b already have assumed values, update them. Union-find is used for this update.

Trie

Design

Segment Tree & Binary Index Tree