Solving Coding Questions by 15 Patterns

• This article demonstrates how to solve typical coding questions by patterns.
• Thanks for this great article.

Table of Contents

1. Sliding Window
2. 2 Pointers or Iterators
3. Fast and Slow Pointers or Iterators
4. Merge Intervals
5. Cyclic sort
6. In-place reversal of linked list
7. Tree BFS
8. Tree DFS
9. Two heaps
10. Subsets
11. Modified binary search
12. Top K elements
13. K-way merge
14. 0/1 Knapsack (Dynamic Programming)
15. Topological sort

General Tips

String

1. Char to string, leetcode.

string str;
res += n % 26 + 'A'; // is equal to below
res = res + char(n % 26 + 'A'); // char is quired

Math

• Sum of 0, 1, 2, 3 … n-1 is n(n-1)/2 , the sum of 1, 2, 3…n is n + n(n-1)/2 = n(n+1)/2.
• Reverse a number (123 ->321 ) or combine single digits to a number (1,2,3 => 123). Init result with 0, updates result by multiplying 10 + x % 10. Need to check overflow. If x >= 0, both x/10 and x % 10 will be >=0. If x < 0, both of them will be <= 0.

-1 / 10 : 0
-1 % 10 : -1
-10 / 10 : -1
-10 % 10 : 0
-11 / 10 : -1
-11 % 10 : -1

• Prime numbers. For a number n, to check if n is prime (2,3,5…) or not, we can use the following condition [2, sqrt(n)] instead of using [2, n-1].

for (int i = 2; i <= sqrt(n); i++){
    if (n % i) return false; //non-prime
}
e.g. 36, co-factors are:
{1,36}, {2,18}, {3,12}, {4,9}, {6,6}
{9,4}, {12,3}, {18,2}, {36,1}
we can only check the first part where the first element of the co-factors are <= sqrt(n)

• %

4 % 2 : quotient 2, carry 0
2 % 4 : quotient 0, carry 2, not 0!
0 % 2 : quotient 0, carry 0

Hashmap

• When dealing with the frequency of a character, use hashmap (vector v(128) for standard ASCII, vector v(256) for extended ASCII, vector v(26) for alphabet, unordered_map for all cases) to record the frequency.
• Create and check one-to-one mapping. LeetCode.

if (m1[s[i]] != m2[t[i]]) return false;
m1[s[i]] = i + 1;
m2[t[i]] = i + 1;

LinkedList

• when the questions ask to return a linked list (e.g. https://leetcode.com/problems/add-two-numbers/), it’s essential to assign the correct value to the head of the linked list and return it. We can either define a dummy node with a dummy value and return dummy->next (it’s ok even if we need to return nullptr), or we can assign value to head when we find the exact head. e.g.

// method 1, use dummy
ListNode* somefunc(){
    ListNode *dummy = new ListNode(-1), *node = dummy;
    node->next = <sum value>;
    node = node->next;
    return dummy->next;
}
// method 2, update head
ListNode* somefunc(){
    ListNode *head = nullptr;
    ListNode *node = nullptr;
    while( some condition ){
        ListNode *tmp = new ListNode(some value);
        if(head == nullptr) {
            head = tmp;
            node = head;
        }else{
            node->next = tmp;
            node = node->next;
        }
    }
    return res;
}
// the following doesn't work, we need to allocate node and assign it to node->next, like method 2, (node->next = new ListNode(1), node = node->next, otherwise the nodes are not connected.
ListNode *head = nullptr;
ListNode *node = head;
while( some condition ){
    node = new ListNode(some value);
    if(head == nullptr) head = node;
    node = node->next;
}
return head; //it only contains a single node

• Use of dummy

Node *dummy = new Node(0, nullptr);
Node *node1 = new Node(1, nullptr);
Node *cur = dummy;
cout << cur << endl;         //0x371640
cout << dummy << endl;       //0x371640
cout << dummy->next << endl; //0
cur->next = node1;
cout << cur->next << endl;   //0x371660
cout << dummy->next << endl; //0x371660 changing cur->next will change dummy->next
Node *node2 = new Node(2, nullptr);
cur = node2;
cout << cur << endl;   //0x3712d0
cout << dummy << endl; //0x371640, changing cur won't change dummy!

• Find the center of a linked list. It is better to use the condition below instead of while (fast && fast->next). When we need to manipulate the second half of the linked list. Leetcode

ListNode *slow = head, *fast = head;
while (fast->next && fast->next->next) {
    slow = slow->next;
    fast = fast->next->next;
}

1 2 2 1
  s f
1 2 3 2 1
    s   f
The slow pointer will stop at the center position no matter the number of nodes is odd or even.

Tree

• Two ways of traversal: BFS and DFS. e.g. leetcode 102.
• BFS

1. iteration with the help of queue , for loop starting with q.size().

queue<TreeNode*>q{{root}};
while(!q.empty()){
    for(int i = q.size(); i > 0; i--){
        TreeNode* t = q.front(); q.pop();
        if(t->left) q.push(t->left);
        if(t->right) q.push(t->right);
    }
}

2. recursion with the help of variable level , start with level 0.

void helper(TreeNode* root, int level, vector<vector<int>>&res){
    if(!root) return;
    if(level == res.size())
        res.push_back({}); //apply for new layer
    res[level].push_back(root->val);
    helper(root->left, level+1, res);
    helper(root->right, level+1, res);
}

• DFS (preorder, inorder, postorder)

1. recursion (preorder)

void dfs(root){
    if (!root) return;
    <do something for currenct node>
    dfs(root->left);
    dfs(root->right);
}

2. Iteration with the help of stack. The preorder traversal of a BST will generate a list with ascending order.

vector<int> preorderTraversal(TreeNode* root) {
    vector<int>res;
    stack<TreeNode*>s;
    TreeNode* cur = root;
    while (!s.empty() || cur){
        while (cur){ //go to the left most node's next (nullptr)
            s.push(cur);
            res.push_back(cur->val);            
            cur = cur->left;
        }
        cur = s.top(); s.pop();
        cur = cur->right; //no if
    }
    return res;
}
vector<int> inorderTraversal(TreeNode* root) {
    vector<int> res;
    stack<TreeNode*>s;
    TreeNode *cur = root;
    while(!s.empty() || cur){
        while(cur){ //go the left most node's next (nullptr)
            s.push(cur);
            cur = cur->left;
        }
        cur = s.top(); s.pop();
        res.push_back(cur->val);
        cur = cur->right; //no if
    }
    return res;
}
vector<int> postorderTraversal(TreeNode* root) {
    vector<int> res;
    stack<TreeNode*> s;
    TreeNode *cur = root;
    while (!s.empty() || cur) {
        while (cur) {
            s.push(cur);
            res.insert(res.begin(), cur->val);
            cur = cur->right; 
        }
        cur = s.top(); s.pop();
        cur = cur->left; //no if
    }
    return res;
}

• For a full binary tree, the leaf level has an upper bound of n/2, which is O(n). The time complexity to calculate the height of a tree is O(n) as we will need to visit all the nodes once, space is O(h) == O(n).
• Find the height/max depth of a tree

int height(TreeNode* root) {  
    if (!root) return 0;  
    return 1 + max(height(root->left), height(root->right));
}

• Count nodes of a tree

int count(TreeNode* root) {
    if (!root) return 0;  
    return 1 + count(root->left) + count(root->right);
}

• To find the Lowest Common Ancestor, we could discuss all possible cases.
  1. Two nodes are in the left tree
  2. Two nodes are in the right tree
  3. One is in the left and the other one is in the right tree
  If it is a BST, it is to find the node whose value is in between the two nodes, if it is not a BST, we may write code with the 3 cases.

Matrix

• Convert index in 1D array (size k) to index in 2D array(row:m, col: n) where k = mn If i is index in 1D array, the index in 2D array is [i/n][i%n], where n is column of 2D array.

0 1 2 3
4 5 6 7
8 9 1 0
5 => [5/4][5%4] = [1][1]

• swap the numbers around symmetry \ and / . Leetcode

7 8 9     7 4 1
4 5 6  => 8 5 2
1 2 3     9 6 3
// symmetry \
for (int i = 0; i < matrix.size(); ++i) {
    for (int j = i + 1; j < matrix[i].size(); ++j)
        swap(matrix[i][j], matrix[j][i]);
}
// symmetry /
1  2  3    9  6  3
4  5  6 => 8  5  2
7  8  9    7  4  1
int n = matrix.size();
for (int i = 0; i < n - 1; ++i) {
    for (int j = 0; j < n - i; ++j) {
        swap(matrix[i][j], matrix[n - 1- j][n - 1 - i]);
    }
}

Binary Search

• Use int m = l + (r - l) / 2; or int m = r — (r - l) / 2; instead of int m = (l + r) / 2 to avoid overflow.
• Upper bound: if we initialize right = arr.size()-1, close boundary, [0, size()-1], then:

while(left <= right){
    ... left = mid + 1;
    ... right = mid - 1;
}

• Upper bound: if we initialize right = arr.size(), which means it is an open boundary, [0, size()), then:

while(left < right){
    ... left = mid + 1;
    ... right = mid; //open boundary, doesn't include mid
}

• Find first greater or equal (upper bound). If target could not be found, then left — right = 1; right is the lower bound, right + 1 is the lower bound.

int firstGreaterEqual(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) left = mid + 1;
        else right = mid - 1; // if nums[mid] >= target
    }
    return right + 1;
}

Subsets, substring

• Sum of 1…n is n * (n+1)/2.
• Ref, Subset, Palindrome Partitioning, Substring

Subset: 2^n (Order doesn't matter in sets, each charactor can exist or nont exist, so 2^n)
Subsequence: 2^n (Since we keep the original ordering but may not be consecutive, this is the same as subset), 3 letters: => C(3, 0) + C(3, 1) + C(3, 2) + C(3, 3) = 1 + 3 + 3 + 1 = 8 (2^3), may not be consecutive)
Substring: n(n+1)/2 (Elements must be consecutive), n + (n-1) + (n-2) + (n-3) + … 2 + 1)
Number of ways to partition a string: 2^(n-1). (we can either put or don't put the pipe in n-1 slots, different ways may have same substring: aab: {a,ab}, {a,a,b}, {aa,b}

vector

• Remove duplicates, it works for set even if the element of vector is vector. but not for unordered_set. ref

1. Just using vector, sort + unique

sort( vec.begin(), vec.end() );
vec.erase( unique( vec.begin(), vec.end() ), vec.end() );

2. Convert to set (manually)

set<int> s;
unsigned size = vec.size();
for( unsigned i = 0; i < size; ++i ) s.insert( vec[i] );
vec.assign( s.begin(), s.end() );

3. Convert to set (using a constructor)

set<int> s( vec.begin(), vec.end() );
vec.assign( s.begin(), s.end() );

• Use of resize and assign, assign a value to all the elements.

vector<int>res(5);
res.resize(i+1, 1); //value of new elements are 1
res.assign(10, 1); //assign 1 to all elements

Bit

1. To check bit at position i from right, there are two solutions. We can use this technique to extract k-bit from an integer (32-bit) while using a mask with k 1s. i.e (num & mask) LeetCode, LeetCode 169

1. Don't change the number
for (int i = 0; i < 32; ++i) {
    if (num & (1 << i)) // the value will be 0, 1, 2, 4, 8... as 1 << i) can be greater than 1.
}
2. Change the number itself
for (int i = 0; i < n; i++){
    if (num & 1) { // it can only be 0 or 1
         // do something
    };
    num >>= 1; // change num, drop the right most bit
}

2. Operators

if (n & (1 << i)) { // same as n & 1 << i
     res += (1 << (31 - i)); // same as res += 1 << 31 - i;
}

1. Sliding Window

Concepts: ref

• The problem input is a linear data structure such as a linked list, array, or string
• You’re asked to find the longest/shortest substring, subarray, or the desired value
• The window size remains constant or grows or shrinks

Tips

• The key is to figure out how to update the start position of the window: if the size is fixed, we use k, otherwise, we check the condition (e.g. sum of the element so far)

Questions

• Longest Substring with (no more than) K Distinct Characters (medium)

Solution: O(n), O(k)

1. use hashmap to track the frequency of each char
2. if there are more than k different char in the hashmap, we need to decrease the frequency by 1 from the start position, and delete this char from the hashmap if the frequency turns to 0, after each decrement, increase start postion by 1
Input: String=”araaci”, K=2
Output: 4
Explanation: The longest substring with no more than ‘2’ distinct characters is “araa”.
um[a]:1, size:1, start:0, res:1
um[r]:1, size:2, start:0, res:2
um[a]:2, size:2, start:0, res:3
um[a]:3, size:2, start:0, res:4
um[c]:1, size:3
   um[a]:2, size:3, start:1, res:4
   um[r]:0, size:2, start:2, res:4
um[i]:1, size:3
   um[a]:1, size:3, start:3, res:4
   um[a]:1, size:2, start:4, res:4

Question list for practice

1. Longest Substring Without Repeating Characters (medium), solution
2. Permutation in String (medium), solution, solution, use the size of one string as window size
3. Longest Repeating Character Replacement (medium)

2. Two Pointers or Iterators

Concepts: ref

• It will feature problems where you deal with sorted arrays (or Linked Lists) and need to find a set of elements that fulfill certain constraints
• The set of elements in the array is a pair, a triplet, or even a subarray

Questions

• Squaring a sorted array (easy)

Solution O(n), O(n)

Input: [-4,-1,0,3,10]
Output: [0,1,9,16,100]
1. Find the find the first non-negative (if all are negative, the right most element) and initiate right pointer with its index, not the left pointer!! e.g. -1, 2, 2
2. Square the elements of the left part from the right to left, square the elements of the right part from left to right, merge those two parts
rightIdx: 2
leftIdx: right-1 = 1
left: 1, 0 => 1,16
right: 2, 3, 4 => 0,9,100 
merge: 0,1,9,16,100

• Triplets that sum to zero (medium)

Solution O(n²), O(number of results)

1. Sort the array so we can use two pointers
2. We need to find the unique triplets, so we need to skip same values of first, second and third value to avoid duplicate
3. The continue is to skip the duplicate for the first element, and the two while loops is to skip the duplicates for the second and the third elements
Given array nums = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]
-4 -1 -1 0 1 2
i  l         r
i     l      r
i        l   r
i          l r
   i  l      r =>-1,-1,2
   i     l r   =>-1,0,1
      i        =>nums[i] == nums[i-1],continue to avoid dup: -1,0,1
         i l r

Question list for practice: leetcode

1. Remove Element (easy) but tricky
2. Implement strStr() (easy)
3. Container With Most Water (medium) typical problem to calculate maximum area, solution
4. 3Sum Closest (medium) similar to Triplets that sum to zero
5. Sort Colors (medium) tricky, two + 1 pointers

3. Fast and Slow pointers

Concepts: ref

• The problem will deal with a loop in a linked list or array
• When you need to know the position of a certain element or the overall length of the linked list
• Fast and slow pointer usually start from the same direction, may or may not start at the same position
• It is important to understand why it works if there is a loop as explained in the above link. Think about it this way: fast enters the cycle first, after the slow enters, if you think of slow is ahead of fast, the distance between slow and fast will minus 1 after each forwarding, so they will meet
• There are some cases where you shouldn’t use the Two Pointer approach such as in a singly linked list where you can’t move in a backward direction

Tips

• There is no need to check the boundary of the slow pointer, as checking the fast pointer is enough. e.g.

while(fast && fast->next){...} //fast
while(slow && fast && fast->next){...} //slow

Questions

• Linked List Cycle (easy)

Solution O(n), O(1)

1. If there is a cycle, the slow and fast will eventually meet

Question list for practice

1. Linked List Cycle II (medium) explanation
2. Happy number (easy/medium), note:

int i = 19;
cout << (i%10 * i%10) << endl; //1: (9 * 19)%10 == 1
cout << (i%10) * (i%10) << endl; //81: 9*9

3. Palindrome Linked List (easy/medium), stack, recursion, reversal

4. Merge Intervals

Concepts

• In a lot of problems involving intervals, you either need to find overlapping intervals or merge intervals if they overlap.
• Given two intervals (‘a’ and ‘b’), there will be six different ways the two intervals can relate to each other.

Questions

• Merge Intervals (medium)

Solution O(nlogn), O(n)

1. Sort intervals (by start time, no additional compare function)
2. Push first interval to lists
3. Iterate over each interval, check:
a. If it overlaps with last interval in the list, update the end time
b. If it doesn't overlap with the last interval in the list, push current interval to list

• Insert Interval (medium/hard), the key is to 1. find possible overlap patterns, 2. update the newInterval (pattern 1,2) and insert it at the proper position by using a pos variable to track the position (only increment position by 1 when it is pattern 3), 3. for pattern 4, we just insert current interval to result.

  1.|_|   2.|_|  3.|_|     4.   |_|
new: |_|   |_|        |_|    |_|

5. Cyclic sort

Questions

• Find the Smallest Missing Positive Number (medium/hard)

Solution O(n), O(1)

1. Change original array to put nums[i] on nums[nums[i] - 1], i.e. 1:nums[0], 2:nums[1]
2. Only care about the numbers >=1 and <=n, i.e. if n = 4 => 1,2,3,4
3 4 -1 1
n = 4
i = 0, nums[3-1] != nums[0] => -1 4 3 1 (put 3 at correct position)
i = 1, nums[4-1] != nums[1] => -1 1 3 4 (put 4 at correct position)
       nums[1-1] != nums[1] => 1 -1 3 4 (put 1 at correct position)
i = 2, nums[3-1] == nums[2] => do nothing
i = 3, nums[4-1] == nums[3] => do nothing
-1 != 1+1, return 2
if n == 0, return 1

Question list for practice

• Find the Missing Number (easy), solution (use XOR to remove elements)

6. In-place reversal of linked list

Concepts

• To reverse a linked list without using extra memory

Questions

• Reverse a Linked list (easy)

Solution O(n), O(1), article, video

The key is to return the last element as new head, and keep returning this new head in each recursive call, so we will eventually get the new head after all recursive are called.
1->2->3->4->null
reverse(1)
  reverse(2)
    reverse(3)
      reverse(4), 4->next is null, return 4 as head, list: 4
    node=4
    3->next->next = 3 (4->next=3), list: 4->3
    3->next = nullptr, list:4->3->null
    return node (4)
  node=4
  2->next->next = 2(3->next=2), list:4->3->2
  2->next = nullptr, list: 4->3->2->null
  return node (4)
node=4
1->next->next = 1(2->next=1), list: 4->3->2->1
1->next = nullptr, list:4->3->2->1->null
return node (4)

• Reverse Linked List II (medium)

Solution O(n), O(1)

Method 1: use dummy node, its next points to head, then reverse one node in one loop:
Original: 1 -> 2 -> 3 -> 4 -> 5 -> NULL, m = 2, n = 4
1st loop: 1 -> 3 -> 2 -> 4 -> 5 -> NULL
2nd loop: 1 -> 4 -> 3 -> 2 -> 5 -> NULL
Method 2: Reverse the sub linked list using regular reversal, e.g.
Original: 1 -> 2 -> 3 -> 4 -> 5 -> NULL, m = 2, n = 4, we need to reverse 2->3->4 to 4->3->2, then let node 1’s next points to start of reversed sub linked list (beforeStart->next = prev), let the last node's next points to first node behind the sub linked list (start->next = cur), e.g.
beforeStart: 1
start: 2
After reversal:
Reversed part: 4->3->2
prev: 4
cur: 5
start->next=cur => 2->5,thus: 4->3->2->5->NULL
beforeStart->next = prev => 1->4, thus: 1->4->3->2->5->NULL

Question list for practice (linked-list, not limited to reversal)

• Rotate List
• Reorder List

7. Tree BFS

Concepts

• Traverse a tree and uses a queue to keep track of all the nodes of a level before jumping onto the next level.
• The Tree BFS pattern works by pushing the root node to the queue and then continually iterating until the queue is empty. For each iteration, we remove the node at the head of the queue and “visit” that node. After removing each node from the queue, we also insert all of its children into the queue.
• Any problem involving the traversal of a tree in a level-by-level order (or level order traversal) can be efficiently solved using this approach.

Questions

• Binary Tree Level Order Traversal (easy), solution

Solution O(n), O(n)

// Iteration
1. all children pushed in the iteration of nodes of current level will be the elements of next level
2. inserting element at beginning of vector will give us the traversal with bottom to up order
// Recursion
1. Due to the recursive nature, we will always have depth-first processing of the left child node, so it will cross different layers, when we want to insert a node, we must know the current depth, so we use a variable level marking the current depth, it is initialized with 0, indicating the depth of the root node. 
2. Since we need to return a two-dimensional array res, we don't know the depth of the binary tree at first, so we can't realize the size of the two-dimensional array. It only increases continuously during the traversal process.
3. When level is equal to the size of a two-dimensional array, we need to to apply for a new layer and continue to add numbers to it.
Another way to return reversed vector is:
reverse(res.begin(), res.end());
return res;

Question list for practice (LeetCode)

• Symmetric Tree (easy), can also be solved by DFS
• Zigzag Traversal (medium), similar to above, the only difference is we have to determine whether or not we insert the element in reverse order. We use a variable to mark the current level, if it is odd, reverse current line (in iterative method) or insert the element at the beginning of the current line (in recursive method).

8. Tree DFS

Concepts

• Use recursion (or a stack for the iterative approach) to keep track of all the previous (parent) nodes while traversing.
• Decide whether to process the current node now (pre-order) or between processing two children (in-order) or after processing both children (post-order).
• It can be used if the problem requires searching for something where the node is closer to a leaf.

Tips

• Time complexity to calculate the height of a binary tree is O(n), as we need to traverse each node once.
• To calculate the max/min depth/height of a binary tree, we basically use DFS, we can also use BFS along with a variable to track the level.

Questions

• Binary Tree Path Sum (easy)

Solution O(n), O(h)

// Iteration
1. We can easily get stuck if we change the value of sum itself in the loop, e.g. sum -= tmp->val, this is different from the recursion below, as the the changed sum value is not independent in each stack pop, we will need to recover the value to go to another path if we changed the sum value.
2. Instead of change sum in loop, We can add value of parent to its children and when it reaches leaf, we simply check if the value is equal to sum or not.
// Recursion
1. The termination is when we find a leaf and its value is equal to the target value.
2. The subproblem is to check left tree and right tree with the target value (sum - root->val).
3. The sum-root->val is independent in each call for left and right tree, thus we don't need to recover its value if we don't find a path in left tree then go to right tree.

• All Paths for a Sum (medium)

Solution O(n), O(h * num_of_solution)

  1
 / \
2   3
sum: 4
helper(1), vec: 1
  helper(2), vec: 1,2
    helper(null), 2’s left
    helper(null), 2’s right
  pop_back(), vec: 1zx
  helper(3), vec: 1,3 res: {{1,3}}
    helper(null), 3’s left
    helper(null), 3’s right
  pop_back(), vec: 1

Question list for practice (LeetCode)

• Same Tree (easy)
  1. Recursion: Check current values and left and right subtrees
  2. Iteration: Inorder
  3. Iteration: BFS (must add nullptr node to queue as well)
• Symmetric Tree (easy)
• Invert Binary Tree (easy)
• Maximum Depth of Binary Tree (easy) (DFS, BFS)
• Balanced Binary Tree (easy) (Tricky Time/Space Complexity)
• Convert Sorted Array to Binary Search Tree (easy)
• Validate Binary Search Tree (medium)
  1. Recursion: limit the range for the sub-tree
  2. Inorder using array
  3. Inorder using previous node
  4. Iteration (stack): inorder using the previous node
• Kth Smallest Element in a BST (medium), use the property that inorder traversal returns elements with ascending order.

9. Two heaps

Concepts

• A Min Heap to find the smallest element and a Max Heap to find the biggest element.

Questions

• Find the Median of a Number Stream (medium/hard)

Solution O(log n), O(n)

1. A max-heap to store the smaller half of the input numbers
2. A min-heap to store the larger half of the input numbers
3. Both the heaps are balanced (or nearly balanced), The max-heap contains all the smaller numbers while the min-heap contains all the larger numbers
4. The max-heap is allowed to store, at worst, one more element more than the min-heap.
5. The median can be found with O(1) time complexity using top().
6. As the heaps are sorted, adding element to it takes O(log n).
e.g.
1,2,4
lomax: 2,1
himin: 4
m = lomax.top() = 2
1,2,3,5
lomax: 2,1
himin: 3,5
m = (lomax.top() + himin.top()) * 0.5 = (2+3) * 0.5 = 2.5

Question list for practice (heap, not limited to two heaps)

10. Subsets

Concepts

• The pattern Subsets describes an efficient Breadth-First Search (BFS) approach to handling all problems of finding Permutations and Combinations of a set of elements.
• Subsets problem is one type of the problems in backtracking
  1. Decision Problem — we search for a feasible solution.
  2. Optimization Problem —we search for the best solution.
  3. Enumeration Problem (permutations and combinations) — we find all feasible solutions.

Tips

• When calculating subsets using recursion, we use a variable level in each function call.
• When calculating combinations, (e.g. [], [1], [1,3]…), we start with the last position of the array, i.e. level = array.size-1, and the base condition is when the level is -1, indicating we need to add an empty set in the result.
• When calculating permutations, (e.g. [1,3,5],[1,5,3],[5,1,3]…), we start with the first position of the array, i.e. level = 0, and the base condition is when the level is equal to the size, i.e level = array.size, indicating we need to add the current result to the result list.

Questions

• Subsets (easy/medium)

Solution O(2^n), O(2^n), Iteration

Given set: [1, 5, 3]
Iteration
1. Start with an empty set: [[]]
2. Add the first number (1) to all the existing subsets to create new subsets: [[], [1]];
3. Add the second number (5) to all the existing subsets: [[], [1], [5], [1,5]];
4. Add the third number (3) to all the existing subsets: [[], [1], [5], [1,5], [3], [1,3], [5,3], [1,5,3]].
Recursion
1. Start from the last element, decrease the index by 1 each time until the index becomes -1 which means it is empty now.
2. Assign the result with the returned value of last recursion, add current element to each vector and push those new vector to result.
e.g. [1,5,3]
rec(nums, 2)
  rec(nums, 1)
    rec(nums, 0)
      rec(nums, -1)
      vv = [[]], return vv
    size = 1
    v = [1]
    vv = [[],[1]], return vv
  size = 2
  v = [5], [1,5]
  vv = [[],[1],[5],[1,5]], return vv
size = 4
v = [3], [1,3], [5,3],[1,5,3]
vv = [[],[1],[5],[1,5],[3],[1,3],[5,3],[1,5,3]], return vv
Time and Space:
In each step, the number of subsets doubles as we add each element to all the existing subsets, the time complexity of the above algorithm is O(2^N)
Since we will have a total of O(2^N) subsets, the space complexity of our algorithm is also O(2^N)
Note: we can also use below in the for loop
vv.push_back(res[j]);
vv.back().push_back(nums[i]);

• Subsets With Duplicates (easy/medium)

Solution O(2^n), O(2^n), Iteration

1. Sort all numbers of the given set. This will ensure that all duplicate numbers are next to each other.
2. Follow the same BFS approach but whenever we are about to process a duplicate (i.e., when the current and the previous numbers are same), instead of adding the current number (which is a duplicate) to all the existing subsets, only add it to the subsets which were created in the previous step.
3. The key is how to update the index of start and end. If it is not duplicate, [0, size-1], if duplicates, [end_before_adding_previous_ele + 1, size-1]
[1,2,2]
0. [], start:0, end:0
1. (1), start:0, end:0 => [][1]
2. (2), start:0, end:1 => [][1][2][1,2]
3. (2), start:end+1=2, end:3 => [][1][2][1,2][2,2][1,2,2]

• Letter case Permutation (easy/medium)

Solution O(n*2^l), O(n)+O(n*2^l):stack+solutions, n is the length of string, l is the number of letters. the number of solutions is 2^l, each solution has length of n.

1. Use recursion to solve the problem, the base condition is when the level is equal to the size, not size-1, as we need to check if the element s[size-1] is alpha or not
e.g. a1b2
helper(a1b2,0)
  helper(a1b2,1)
    helper(a1b2,2)
      helper(a1b2,3)
        helper(a1b2,4), 4==size
          v.push(a1b2)
        s[3] != alpha, do nothing
      s[2] == alpha
      s[2] = B
      helper(a1B2,3)
        helper(a1B2,4), 4==size
          v.push(a1B2)
    s[1] != alpha, do nothing
  s[0] == alpha
  s[0] = A
  helper(A1b2,1)
    ...
result: a1b2, a1B2, A1b2, A1B2

• Permutations (medium)

Solution, more solutions, O(n*n!), O(n*n!), as there are n! solutions we will operate n times for each, which means line 17 (insert) takes O(n). Each result contains n elements, thus time is O(n*n!).

This problem follows the Subsets pattern and we can follow a similar Breadth First Search (BFS) approach. However, unlike Subsets, every permutation must contain all the number.
1. If the given set is empty then we have only an empty permutation set: []
2. Let’s add the first element (1), the permutations will be: [1]
3. Let’s add the second element (3), the permutations will be: [3,1], [1,3]
4. Let’s add the third element (5), the permutations will be: [5,3,1], [3,5,1], [3,1,5], [5,1,3], [1,5,3], [1,3,5]

Question list for practice (backtracking, not limited to subsets)

• Combination Sum
• Combinations
• Generate Parentheses

11. Modified Binary Search

Concepts

• The best way to search an element in a sorted array, linked list or matrix is binary search.
• To find the middle, init left with 0, right with size()-1, mid = left + (right — left) / 2 can avoid overflow.
• Search smaller side if the key is less than the middle (right = mid -1)
• Search greater side if the key is greater than the middle. (left = mid +1)
• If the key is equal to the element with index middle, return mid.

Tips

• If we init left with 0, right with size()-1, then the while condition is left ≤ right, and the change of left and right are : left = mid + 1, right = mid — 1; It’s better to stick to this initialization.
• There are several patterns that can be solved with binary search:

1. Find the number that is exactly equal to the target. e.g. [2, 4, 5, 6, 9]，target = 6, return idx == 3. Use straightforward Binary Search

int findTarget(vector<int>& nums, int target) {
    int left = 0, right = nums.size()-1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) return mid;
        else if (nums[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

2. Find the first number that is not less than the target (ceiling), this can also be used to find the last number that is less than the target (floor). e.g. [2, 4, 5, 6, 9], target: 3, ceiling: idx = 1, floor: idx = 0

// find the first number that is not less than the target
int findFirstNotLessThan(vector<int>& nums, int target) {
    int left = 0, right = nums.size()-1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) left = mid + 1;
        else right = mid - 1; //nums[mid]>=target, answer is within [left, mid]
    }
    return right+1; //last mid
}
[2,4,5,6,9], target=3
2 4 5 6 9
l       r => m = 2, 5 > 3, right = mid-1 = 1
l r       => m = 0, 0 < 3, left = 1
 lr       => m = 1, 4 > 3, right = 0
r l       => exit loop
return 0+1 -> 1, which is number 4
// to find the last number that is less than the target, as we already found the one which is equal or greater than target, the last element of that element is the last element that is less than the target, so, we can return right instead of right+1, which is 0 (number 2) in this case.

3. Similar to 2, find the first number that is greater than the target, this can also be used to find the last one that is not greater than the target

// find the first number greater than target
int findFirstGreaterThan(vector<int>& nums, int target) {
    int left = 0, right = nums.size()-1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] <= target) left = mid + 1;
        else right = mid - 1; //nums[mid]>target, answer is within [left, mid]
    }
    return right+1; //last mid
}
// to find the last one that is not greater than the target, similar to pattern 2, we can return right instead of right + 1

4. Use sub-function as determining condition

5. Others

Questions

• Search in a Sorted Infinite Array (medium)

Solution, O(log n), O(1)

1. As the array is sorted and we are asked to search a target, the best way to do is using binary search
2. To do binary search, we need left, right and target, however, we don't know right here.
3. As mentioned in the description, if we access the array out of bounds, ArrayReader.get will return 2147483647 which means it is safe to access the array out of bounds.
4. We can try to find the right bound by doubling the right each time until we find the index at which the value is greater than target. (We don't need to find the right most element actually as we only care about finding a number that is greater than target, and as smallest as possible)

• Ceiling of a Number (medium)

Solution O(log n), O(1), binary search

[1,3,4,6,8]
x = 5
1. low = 0, high = 4, mid = 2
arr[mid] < 5, then either arr[2+1] (6) is ceiling or ceiling lies in arr[3, 4] (6, 8)
mid+1 <= high && 5 <= arr[mid+1], return mid+1 (3)
x = 2
1. low = 0, high = 4, mid = 2
arr[mid] > 2, then either arr[mid] (4) is ceiling or ceiling lies in arr[0, 1] (1,3).
mid - 1 >= low, but x < arr[mid-1] (1 >= 0, 2 < 3)
2. ceilSearch(arr, 0, 1, 2)
mid = 0
arr[mid] < x, then either arr[0+1] (3) is ceiling or ceiling lies in arr[1] (3)
mid+1 <= high, x <= arr[mid+1], return mid+1 (1)

Question list for practice

• Intersection of Two Arrays (easy), pattern 1. several solutions including binary search
• Sqrt(x) (easy). pattern 3, find the last one that is not greater than the target
• First Bad Version (easy), pattern 3, find the first that is greater than the target
• Search in Rotated Sorted Array (medium), solution, pattern 5, typical, when getting stuck, try drawing out every possible rotated sorted array to see if there is any rule
• Find First and Last Position of Element in Sorted Array (medium), pattern 2, first is calculated by right, while last is calculated by left.

12. Top K elements

Concepts

• If you’re asked to find the top/smallest/frequent ‘K’ elements of a given set
• If you’re asked to sort an array to find an exact element
• The best data structure to keep track of ‘K’ elements is Heap

1. Insert ‘K’ elements into the min-heap or max-heap based on the problem.
2. Iterate through the remaining numbers and if you find one that is larger than what you have in the heap, then remove that number and insert the larger one.

Tips

• To find top k / kth largest elements, use min-heap to store the large elements, and keep its size k, then the top() is the k-th largest element and all elements in min heap are the top k elements.
• To find top k / kth smallest elements, use max-heap to store the small elements, keep size k, all the k elements are the k / kth smallest elements.

Questions

• Top ‘K’ Numbers (another version)(easy/medium)

Solution (another link)

1) Build a Min Heap MH of the first k elements (arr[0] to arr[k-1]) of the given array. O(k)
2) For each element, after the kth element (arr[k] to arr[n-1]), compare it with root of MH.
a) If the element is greater than the root then make it root and call heapify for MH
b) Else ignore it.
// The step 2 is O((n-k)*logk)
3) Finally, MH has k largest elements and root of the MH is the kth largest element.
Time Complexity: O(k + (n-k)Logk) without sorted output. If sorted output is needed then O(k + (n-k)Logk + kLogk)
The method can also be used to find the kth largest (or smallest) element.

priority_queue<int, vector<int>, greater<int>> pq; is to create a min heap where the root has the smallest value. Code of finding the kth largest element:

• Top ‘K’ Frequent Numbers (medium)

Solution O(nlogn), O(n), max heap

1. Build a hash map element -> its frequency
2. Use priority_queue (pq) to store the pair of element and frequency, use frequency as the first element so that the priority_queue sorts the element by frequency, by default, decreasing order (max heap).
3. When there are less than k elements in the map that hasn't been added to the pq, start to pop the largest (although the current largest isn't the actual largest, it still is the one of k largest)
Note: Instead of popping out in the for loop (which is not intuitive), we can also first add all pairs in max heap, then write a loop to get the top and pop out the elements:
for (auto it : um) pq.push({it.second, it.first});
for (int i = 0; i < k; ++i) {
    res.push_back(pq.top().second); 
    pq.pop();
}

Question list for practice

• Kth Largest Element in a Stream (easy). When adding new element to min-heap, we don’t need to compare its value with top(), as we will pop out an element if the size exceeds k which ensures the min-heap only holds the k largest elements we have so far. We can also use multiset as min-heap.
• K Closest Points to Origin (medium), use max-heap not min-heap!. As we will pop out the elements, using max-heap will leave k smallest (closest) in the heap while min-heap will leave k largest elements.

13. K-way Merge

Concepts

• K-way Merge helps you solve problems that involve a set of sorted arrays.
• Whenever you’re given ‘K’ sorted arrays, you can use a Heap to efficiently perform a sorted traversal of all the elements of all arrays. You can push the smallest element of each array in a Min Heap to get the overall minimum. After getting the overall minimum, push the next element from the same array to the heap. Then, repeat this process to make a sorted traversal of all elements.
• The problem will feature sorted arrays, lists, or a matrix.
• Use this method if the problem asks you to merge sorted lists, find the smallest element in a sorted list.

Questions

• Merge K Sorted Lists (medium)

Solution O(n log k), O(k) (min-heap), O(n log k), O(1) (divide and conquer)

Solution 1: using min-heap
1. Use min-heap (priority_queue) to store the pointer of the linked list.
2. The size of priority_queue is always k, thus Space is O(k)
3. For each push operation, the time is logk and we will do it for total n elements, so time is O(n log k)
4. Also notice how we use our own comparison function
Note: if the problem is Kth Smallest Number in M Sorted Lists (Medium), just use a counter variable and return the value if counter is equal to k in while loop.
Solution 2: devide and conquer
1. Pick k/2 pairs and merge each pair
2. Set k = (k+1)/2, (not k/2), as we need to ensure the last list will be included in one of the pairs, 01234 => 0,3; 1,4
3. Repeat this procedure until we get the final sorted linked list.
we'll traverse almost n nodes per pairing and merging, and repeat this procedure about logk times.
e.g. n = 6, [0][1][2][3][4][5], n, k are the variable below
1st loop: n = 6, k = (n+1)/2 = 3, pairs (n/2 = 3): [0][3]->[0], [1][4]->[1], [2][5]->[2], then: n = k = 3
2nd loop: n = 3, k = (n+1)/2 = 2, pairs (n/2 = 1): [0][2]->[0], then n = k = 2
3rd loop: n = 2, k = (n+1)/2 = 1, pairs (n/2 = 1): [0][1]->[0], then n = k = 1
return [0] if lists is not empty

• Kth Smallest Element in a Sorted Matrix and G4G (Medium/hard)

Solution, min-heap: O(k log n), O(n), max-heap: O(n log k), O(k)

Solution 1: min-heap O(k log n), O(n)
1. Similar to previous one, the difference is the element in the min-heap is not the pointer, thus we need to define a type to store the value and the index (i,j) of the element, and store this type of variable in min-heap
2. The size of priority_queue is always n (n arrays), thus Space is O(n)
3. For each push operation, the time is logn and we will do it for total k times (terminate when we find the kth smallest), so time is O(k log n)
4. We don't need to define our own comparison function
e.g. n = 3, k = 3
[
[1,5,9]
[2,4,6]
]
init: q: 1, 2
1st loop: pop 1 => q: 2, k:2, i:0, j:0, q: 2,5
2nd loop: pop 2 => q: 5, k:1, i:1, j:0, q: 4,5
3nd loop: pop 4 => q: 5, k:0, i:1, j:1, q: 5,6
return matrix[1][1] which is 4
Solution 2: max-heap O(n log k), O(k)
1. Use max-heap which contains k elements
2. If current size of max-heap is larger than k, pop out element, which will always pop out the largest element, so eventually we will have k smallest elements and the top is the result

Question list for practice

• Ugly Number II (medium)

14. 0/1 Knapsack (Dynamic Programming)

Concepts: guru99

• Given weights and values of n items, put these items in a knapsack of capacity W to get the maximum total value in the knapsack. In other words, given two integer arrays val[0..n-1] and wt[0..n-1] which represents values and weights associated with n items respectively. Also given an integer W which represents knapsack capacity, find out the maximum value subset of val[] such that the sum of the weights of this subset is smaller than or equal to W. You cannot break an item, either pick the complete item or don’t pick it (0–1 property).
• 0–1 Knapsack problem has both properties (see this and this) of a dynamic programming problem:
  1. Optimal Substructure — find best/max
  2. Overlapping Subproblems — use Memoization (Top Down) or Tabulation (Bottom Up)

Questions

• 0/1 Knapsack (medium)

Solution and Solution, Video, O(nW), O(nW), where n is the number of items and W is the capacity of knapsack.

1. To consider all subsets of items, there can be two cases for every item: 
(1) the item is included in the optimal subset
(2) not included in the optimal set
2. Therefore, the maximum value that can be obtained from n items is max of following two values.
(1) Maximum value obtained by n-1 items and W weight (excluding nth item).
(2) Value of nth item plus maximum value obtained by n-1 items and W minus weight of the nth item (including nth item).
3. If weight of nth item is greater than W, then the nth item cannot be included and case 1 is the only possibility.
4. As this problem has Overlapping Subproblems property, we can use tabulation to improve.

0–1 Knapsack Problem

• Equal Subset Sum Partition (medium)

Solution O(n*sum), O(sum), video, link

1. As two same sums add to even, return false if the sum is odd
2. Use bool array dp[j] to check if we can get the sum j
3. To check if we can partition, we will need to check if we can find elements whose sum are sum/2
e.g.
1,5,11,5
sum = 22, dp[23]
dp[0..22] = false
dp[0] = true, it is true to get sum 0
1
if(dp[0]),dp[0+1]: true
5
if(dp[0]),dp[5]: true
if(dp[1]),dp[6]: true
11
if(dp[0]),dp[11]: true
if(dp[1]),dp[12]:true
if(dp[5]),dp[16]:true
if(dp[6]),dp[17]:true
as dp[11] (dp[sum/2]) is true, return true

Question list for practice

• House Robber (easy)
• Subset Sum (medium), each number can be chosen or not chosen, the recursion method is exponential (2^n ), but we can use the same method of 0/1 Knapsack problem above by building a 2-D array with bottom-up technique.

15. Topological Sort

Concepts

• Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge uv, vertex u comes before v in the ordering. Topological Sorting for a graph is not possible if the graph is not a DAG.
• For example, a topological sorting of the following graph is “5 4 2 3 1 0”. There can be more than one topological sorting for a graph. For example, another topological sorting of the following graph is “4 5 2 3 1 0”. The first vertex in topological sorting is always a vertex with in-degree as 0 (a vertex with no incoming edges).

• In DFS, we start from a vertex, we first print it and then recursively call DFS for its adjacent vertices.
• In topological sorting, we use a temporary stack. We don’t print the vertex immediately, we first recursively call topological sorting for all its adjacent vertices, then push it to a stack. Finally, print the contents of the stack. Note that a vertex is pushed to stack only when all of its adjacent vertices (and their adjacent vertices and so on) are already in stack.

Questions

• Topological Sorting (medium)

Solution, O(v+e), O(v+e)

adj:
0->
1->
2->3
3->1
4->0,1
5->2,0
ts(0): visited[0]:true, s:0
ts(1): visited[1]:true, s:0,1
ts(2): visited[2]:true => ts(3): visited[3]:true, s:0,1,3,2
ts(4): visited[4]:true, s:0,1,3,2,4
ts(5): visited[5]:true, s:0,1,3,2,4,5
print all elements of stack from top to bottom: 5,4,2,3,1,0

• Course Schedule (medium)

Solution O(v+e), O(v+e)

// BFS
1. create an array to track in-degree of each vertex
2. Start with vertices whose in-degree are 0, put them in queue
3. Iterate through their adjacent vertices, reduce in-degree by 1, if the degree is 0, push to queue
4. If there are vertices whose in-degree are not 0, then cycle exists, return false
[[0,1],[0,2],[1,3],[3,2]]
0->1,2
1->3
2->
3->2
in[0]:0
in[1]:1
in[2]:2
in[3]:1
as in[0]==0, q:0 
1st loop: pop, in[1]:0, q:1, in[2]:1, q:1
2nd loop: pop, in[3]:0, q:3
3rd loop: pop, in[2]:0, q:2
4th loop: pop, q:
in[0], in[1], in[2], in[3] == 0, return true
// DFS
-1: circle, 1: visited, 0: unvisited
[[0,1],[0,2],[1,3],[3,0]]
0->1,2
1->3
2->
3->0
canFinishDFS(0)
  v[0] = -1
    canFinishDFS(1)
      v[1] = -1
        canFinishDFS(3)
          v[3] = -1
            canFinishDFS(0)
              as v[0] == -1, return false
          return false
      return false
  return false