Math. Take a look at all digits from 0 to 9. 0,1,8 are strobogrammatic no matter what. 6 and 9 can form a strobogrammatic pair, which means they must

Use an integer counter as a Stack. Make sure there are more left parens than right ones. Increase the counter when there is a left paren. If there is

Stack. Use stack to check pair. Whenever there is a valid pair, pop from stack since it is already valid. Quick check: If string length not even, retu

Stack. Push closing parens onto stack instead of opening ones. This way match function can be saved. When it is a right paren: | If the stack is empty

Sort num array first

BFS. Level-order Traversal. Search from begin word to end word. Use an integer to track ladder length. Add begin word to queue. Remove begin word from

BFS, search from both ends.

Create a comparator for sorting Convert num to String and compare the concatenated result of them Note {0, 0} is a special case

Only height is smaller do update happens Stack for indices add a zero height into the group

DP. O(nlogn) time. O(n) space. Store the tail of a LIS at a specific length. dp[0] means the tail value of array at length 1. Current number can eithe

DP. O(n^2) time, O(n) space. We can store the longest increasing subseqence lengths of [0, i-1]. Now at index i, if nums[i] is larger than nums[x], it

Traverse the string Get current character Update start point Update max Put current char in map

DP d[i][j] = max{d[i+1][j], d[i-1][j], d[i][j+1], d[i][j-1]} + 1

Set. Add numbers into a set first. Then for each number i: 1) Make sure it's the start of a sequence by check i - 1. 2) If it's the start, check i + 1

Union Find. O(n) Time. View consecutive sequence as connected component. Use a map to store value to connected component id mapping. For each number n

Manacher's Algorithm, O(n) Time. Insert a special character between each character in a string, and also both at the start and the end. S = “abba” =>

Backtracking. Maintain a max length, a current length and current values. When at a leaf node, compare with existing max to see if the path is longest

Recursive. Recurrence relation: Search for p and q in left and right subtrees. If both are found, it means the two nodes are in different subtrees, ro

Iterative. Two stacks. First, DFS for p or q. If we found anyone of them, copy current stack to a new stack, which keeps all its ancestors. Then we tr

Check if both trees are the same

Recursive. By definition we should compare the height of each node. Tree's height range from -1 to h. -1 is null, 0 is root's height. So instead of he

Find max sum contiguous subsequences

DP. Bottom-up. Space optimized. O(n) Time, O(1) Space. Recurrence Relation: max profit of ith day = a[n] - min > max(i-1) ? a[n] - min : max(i-1). To

DP. Goes forward to build single transaction max profit Then goes backward to build max since day i profit Find the max of the sum of these two

Sell whenever there is profit. If next value is bigger, add the difference up to the profit

DP. Bottom-up. Optimized. O(n) Time, O(1) Space. Maximum profit is the maximum price - minimum price. So loop from second day to last day, track min p

DP. Bottom-up. O(n) Time, O(n) Space. Store max profit of each day using an integer array. Profit of next day can only be same as last day or update b

DP. More compact version. sell is skipped on day 1 since we don't have any share. hold is initialized as MIN since we have negative values, 0 will be

DP. Bottom-up. O(n) Time. O(n) Space. Keep track of minimum price of the stock. Keep track of the maximum profit before today. Get the maximum profit

DP. O(n) Time, O(1) Space. State: the max subarray sum ending at i. Recurrence Relation: Since the sub array is contiguous, nums[i] must be included.

A: [1,2,1,2,6,7,6,1] -> B: [3,3,3,8,13,13,7] B is the k-interval sum. The index of element in B is the starting index of the subarray in A. It makes t

O(n) Time, O(n) Space Find max and min in one traverse Calculate bucket length and divide numbers into buckets Traverse buckets to find max gap

Math. Swap the digit that is: 1. larger. 2. max amongst all larger ones. Build a digit to last index of the digit mapping to get the last position of

Copy items from low to high to a helper array Init 2 pointers Compare value of 2 pointers, and overwrite original array, and move on Stop when left re

Cut into two halves Sort left half first, move to right half's pre head and sort right Merge two halves Insert node in latter part if its smaller than

DP, bottom-up Fill a table in diagonal direction

Modification of maxKadane to find min sum contiguous subsequence

DP. bottom-up row by row, use an array to store values

Dynamic Programming. The result is guaranteed to be possible. So either both are already increasing, or the increasing can be fixed with swapping. Mod

Two Pointers. Hash Table. Two pointers to represent a moving window. Hash table to record count of letters in S and T. To know whether all T's letters

DP. State: The starting index (+1) of the valid window in S where T has length i and S has length j. Base case: T is empty, starting index is always j

Hash Table. Two Pointers. <p> 1. Use two pointers: start and end to represent a window. 2. Move end to find a valid window. 3. When a valid window is

Hash Table. Pre-computing. Find the index of the next character in T in S. Instead of searching in S every time, we may iterate S once to pre-compute

DP Math.min(result.get(i), result.get(i + 1)) + triangle.get(curLv).get(i) Pick the smaller one of next row and add it up to current level

Morris Traversal, link null left node to its inorder predecessor link null right node to its inorder successor Initialize current as root While curren

Two Pointers. One-pass. Track the end of non-zero elements with a pointer. Swap non-zero elements to the front. For each number n in the array: | If n

Two pointers. One pointer goes through the array and find positive numbers. The other tracks the next position to be filled up. Move all positive numb

Binary Search. Validate input first. If x < 0 , invalid. Special cases: If x = 0 or 1, return x. <p> Binary Search from 1 ~ x/2. While lo < hi: | Roun

Why return hi not lo in the end? The loop breaks when lo > hi. So the previous loop lo = hi = mid. Now, mid != t, because it didn't return. If mid < t

e.g.: 1234 -> 1243, 1243 -> 1324 Traverse backward to get 3 Then traverse forward to get furthest number bigger than 3 Swap these two digits and rever

use ax + by = c to represent a line and a|b|c as a key for that line a, b, c should be normalized, how? <p> special case, vertical, horizontal

use ax + by = c to represent a line and a|b|c as a key for that line a, b, c should be normalized, how? special case, vertical, horizontal

DP, Bottom Up. State: # of ways to decode string's substring from [0, i], ways[i]. Base case: ways[0] = 1. Only 1 way to decode empty string. ways[1]

DP, Optimized Space. Reduce space usage from O(n) array to O(1) variables since we are only using the previous two values to calculate.

BFS. DFS. Start from the top-left corner of the grid. Go through each grid row by row and check if it is a land. If it is not, skip. If it is, BFS / D

Union find. Find the # of connected components. Union find can mark the grids. But to find out # of connected components, we must understand that: 1.

A natural number is... <p> 1. a square if and only if each prime factor occurs to an even power in the number's prime factorization. 2. a sum of two s

DP, bottom-up

If we find an arithmetic array of length n, the number of slices it has is: (n - 2) (n - 1) / 2 E.g. [1, 2, 3, 4], n = 4, # of arithmetic slices = (4-

Same idea. Slightly different implementation. We skip the first 2 integers in A and start directly from the 3rd. Record the count of integers that can

DP. Space Optimized. State: dp[i]: # of arithmetic slices with integer A[i]. Recurrence Relation: Suppose we have x arithmetic slices in A[0...i-1]. I

Math. String. Try to find the pattern first. The numbers less than 1000, e.g. xyz, can be x Hundred y"ty" z. The numbers larger than 1000, we need to

Hash Table. Several cases: 1. If s1 is a blank string, then for any string s2 that is a palindrome, s1+s2 and s2+s1 are palindrome. 2. If s2 is the re

Trie. Checking whether 2 words form a palindrome can be optimized. By checking whether the current word's prefix is some others' suffix. Adding the re

Find max from from start to end If max is not at the end, filp it to first and flip it to end Reduce array size by one Stop till size reduced to 1

Choose mid value as pivot Move two pointers Swap and move on Return left pointer