Tips: keep two points and shrink from left and right to center, check to meet certain requirement (sum equals a target number) until left index is over right one.
Problems: Two Sum, 3Sum, 3Sum Closest, 4Sum, etc.
- combine with other data structure like tree, min heap
- combine with other algorithms like merge and quick sort
- most time use two pointers (slow and fast) to check circular or not, sometimes to find the middle point in linked list
- most interview questions emphasize changing node position and keep linking
- Take into account whether the change is taking place at the head of the list or someplace else.
Problems: Add Two Numbers, Convert Sorted List to Binary Search Tree, Merge Two Sorted Lists, Partition List, Remove Duplicates from Sorted List, Remove Duplicates from Sorted List II, Remove Nth Node From End of List, Reverse Linked List II, Reverse Nodes in k-Group, Rotate List, Swap Nodes in Pairs
Tips: Input is reversal order of output (Stacks can provide a reversal characteristic.)
Problems: binary tree inorder/preorder/postorder traversal (stack can hold temp node and queue has to deal with it immediately)
Dynamic Programming (DP)
- divide the problem into smaller pieces (smallest as base case)
- solve the smaller pieces in some way (toward base case)
- reassemble the whole problem to get the result
- most times it can be abstracted as: subproblem is moving from a point with 2 directions (right, down), which starts from a certain point (base case) whose condition is fixed, either it’s the destination (bottom right node in a matrix) or elements in last row or level of a tree.
Problems: unique path, triangle, maximal rectangle, minimum path sum, etc.
Binary tree preorder traversal: easiest one, it could process the current, current left and right nodes immediately, so it doesn’t have to put current node in while loop condition as in-order and take care of previous node.
Binary tree inorder traversal: it has to take care of the current node (record left, self and right order as well, can replace with set) or it can use stack peek method and set (current node is visited or not) to check and then deal with left, self, right node in order.
Binary tree postorder traversal: it has to use a stack and two pointers (current, previous) to check left node, left and right have been visited or not, if not push left and right one by one in stack, then process the current node, if yes, process the current node directly.
Clone Graph: BFS traversal all nodes in neighborhood and store in a queue, then process these nodes one by one. Set to store visited nodes to avoid unlimited cycling, HashMap to store all existing nodes to avoid duplicates and Queue to store nodes in neighborhoods.
Best Time to Buy and Sell Stock: get the min number and the larger one after it (only trade once), or if the current one is larger than previous then trade (trade unlimited times), get max profit so far and max profit from current to the end (trade twice)
Search in Rotated Sorted Array: check which half is sorted, and then narrow the range based on the target number in certain half, skip duplicate input numbers if necessary.
Subsets: recursive, when reach the required number limitation and then return the current subset, skip duplicate input numbers if necessary.
Recursion (recursion as a form of iteration)
- Recursion is a method of solving problems that involves breaking a problem down into smaller and smaller subproblems until you get to a small enough problem that it can be solved trivially.
- Usually recursion involves a function calling itself.
Problems: Combination I, Combinations II, Combination Sum, Letter Combinations of Phone Numbers: recursively process the number sequence, add to the temporary results collection, go to next level until reach certain condition (depth equals to length of number array), return upper level and remove the last element added into the temporary results collection, continue to process next number.
Hardware is different, so need a way to measure program efficiency and then use how many times instructions run and how much space (byte, bit) take to finish the program