# [Problems] Algorithm & Data Structure

## Patterns

### Sliding window

* 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 a desired value.
* Either we have given a "window size i.e. k" or we have to "manually find out window size".

// template for variable window size
while(j < size()){

    // Calculation's happen's here
-----------------------------------------------
    if(condition < k){
        j++;
    }
-----------------------------------------------

-----------------------------------------------
    else if(condition == k){
        // ans <-- calculation
        j++;
    }
----------------------------------------------

----------------------------------------------
    else if(condition > k){
        while(condition > k){
            // remove calculation for i
            i++;
        }
        j++;
    }
----------------------------------------------
}
return ans;

#### Problems
* Maximum sum subarray of size ‘K’ (easy)
* [Longest substring with ‘K’ distinct characters (medium)](https://leetcode.com/problems/longest-substring-without-repeating-characters/solutions/2133524/java-c-a-reall-detailed-explanation/)
* String anagrams (hard)

### Two pointers or iterators

* 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++.

#### Problems

* Squaring a sorted array (easy)
* Triplets that sum to zero (medium)
* Comparing strings that contain backspaces (medium)

### Hare & tortoise algorithm

node *slow = head, *fast = head;
while (fast != nullptr && fast->next != nullptr){
    slow = slow->next;
    fast = fast->next->next;
}
// slow is the MIDDLE NODE if total number of nodes is ODD
// slow is the node AFTER the MIDDLE NODE if total number of nodes is EVEN

* 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++.

#### Problems

* Linked List Cycle (easy)
* [Palindrome Linked List (medium)](https://leetcode.com/problems/palindrome-linked-list/submissions/)
* Cycle in a Circular Array (hard)

### Merge intervals

* If you’re asked to produce a list with only ++mutually exclusive intervals++.
* If you hear the term ==“overlapping intervals”==.

#### Problems
* Intervals Intersection (medium)
* Maximum CPU Load (hard)

### Cyclic sort
If the current number you are iterating is not at the correct index, you swap it with the number at its correct index.

* They will be problems involving a sorted array with numbers in a given range.
* If the problem asks you to find the missing/duplicate/smallest number in an sorted/rotated array.

#### Problems

* Find the Missing Number (easy)
* Find the Smallest Missing Positive Number (medium)

### Tree BFS
Pushing the root node to the ==queue== and then continually iterating until the queue is empty.

#### Problems
* Binary Tree Level Order Traversal (easy)
* Zigzag Traversal (medium)

### Tree DFS

If the node is ++not a leaf++(next is not `nullptr`):
1. Decide whether to process the ++current node now (pre-order)++, or ++between processing two children (in-order)++ or ++after processing both children (post-order)++.
2. Make two recursive calls for both the children of the current node to process them.

#### Problems

* Sum of Path Numbers (medium)
* All Paths for a Sum (medium)

### Two heaps
This pattern uses two heaps; A Min Heap to find the smallest element and a Max Heap to find the biggest element. The pattern works by storing the first half of numbers in a Max Heap, this is because you want to find the largest number in the first half. You then store the second half of numbers in a Min Heap, as you want to find the smallest number in the second half. At any time, the median of the current list of numbers can be calculated from the top element of the two heaps.

* Useful in situations like Priority Queue, Scheduling.
* If the problem states that you need to find the smallest/largest/median elements of a set.
* Sometimes, useful in problems featuring a binary tree data structure.

#### Problems
* Find the Median of a Number Stream (medium)

### Subsets
++Permutations and Combinations++ of a given set of elements.

#### Problems

* Subsets With Duplicates (easy)
* String Permutations by changing case (medium)

### Modified binary search

Whenever you are given a ++sorted array, linked list, or matrix++, and are asked to ++find a certain element++, the best algorithm you can use is the Binary Search.

Use ``middle = start + (end — start) / 2`` to avoid overflow.

#### Problems
* Order-agnostic Binary Search (easy)
* Search in a Sorted Infinite Array (medium)

### Top K elements

Insert ‘K’ elements into the ++min-heap or max-heap++ based on the problem.

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.

* 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.

#### Problems
* Top ‘K’ Numbers (easy)
* [Top ‘K’ Frequent Numbers (medium)](https://leetcode.com/problems/top-k-frequent-elements/description/)

### K-way Merge

1. Insert the first element of each array in a Min Heap.
2. Take out the smallest (top) element from the heap and add it to the merged list.
3. After removing the smallest element from the heap, insert the next element of the same list into the heap.
4. Repeat steps 2 and 3 to populate the merged list in sorted order.

* The problem will feature ++sorted arrays, lists, or a matrix++.
* If the problem asks you to ==merge sorted lists==, find the smallest element in a sorted list.

#### Problems
* Merge K Sorted Lists (medium)
* K Pairs with Largest Sums (Hard)

### BInary search
Given a ==sorted array== `vec` of `n` elements, write a function to search a given element `target` in `vec` and return its index.

int left = 0, right = vec.size()-1;
// use left <= right if the retult is return inside the loop
while(left < right){
  int mid = left + (right-left)/2; // avoid overflow
    // case 1: vec[mid] == target
    if (vec[mid] == target)
        return mid;
    // case 2: target is at the right side of mid
    if (vec[mid] < target)
        left = mid + 1;
    // case 3: target is at left side of mid
    else
        right = mid - 1;
}
// left == right
return left;

* If there is no `vec[mid] == target`, then be careful about `right = mid - 1` because `mid` might be 0.
* Keep in mind that `mid` might be equal to `left` but not to `right`. So I think it's better to first check if the target is at the right side of `mid`.

#### [Problems](https://leetcode.com/tag/binary-search/)

* [Find Minimum in Rotated Sorted Array (medium)](https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/)
* [Search in Rotated Sorted Array (medium)](https://leetcode.com/problems/search-in-rotated-sorted-array/)
* [Find First and Last Position of Element in Sorted Array (medium)](https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/)

### Dynamic programming

#### Problem
* [Coin change (medium)](https://leetcode.com/problems/coin-change/solutions/778548/c-dp-solution-explained-100-time-100-space/)
* [Longest Common String (medium)](https://leetcode.com/problems/longest-common-subsequence/description/)

### Graph
#### [Topological sort](https://www.geeksforgeeks.org/topological-sorting/)

* [Directed Acyclic Graph (DAG)](https://web.ntnu.edu.tw/~algo/DirectedAcyclicGraph.html): 不斷前進、不會後退、沒有環，有時分化、有時聚合
* In-degree: The number of incoming edges
Ex from the image above:
1 has in-degree 0, 2 has in-degree 2, 3 has in-degree 1.

Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge (u, v), vertex u comes before v in the ordering.

#### Approach: [Kahn’s algorithm](https://www.geeksforgeeks.org/topological-sorting-indegree-based-solution/) (BFS)

1. ++Compute in-degree++ for each of the vertex present in the DAG and initialize the count of visited nodes as 0.
2. Pick all the ++vertices with in-degree as 0++ and add them into a ==queue==.
3. Remove a vertex from the queue and then
1. Increment the count of visited nodes by 1.
2. ++Decrease in-degree by 1 for all its neighbouring nodes++.
3. ++If the in-degree of neighbouring nodes is reduced to zero, then add it to the queue++.
4. Repeat Step 3 until the queue is empty.
5. ++If the count of visited nodes is not equal to the number of nodes in the graph then the topological sort is not possible for the given graph++.

#### Problems

* [Course Schedule (medium)](https://leetcode.com/problems/course-schedule/)

## Sort

### Bubble sort

void bubbleSort(vector<int>& v){
    for (int l = v.size()-1; l > 1; --l){
        for (int i = 0; i < l; ++i){
            if (v[i] > v[i+1])
                swap(v[i], v[i+1]);
        }
    }
}

### Insertion sort

void insertSort(vector<int>& v){
    for (int l = 2; l < v.size(); ++l){
        for (int i = l; i > 0; --i){
            if (v[i] < v[i-1])
                swap(v[i], v[i-1]);
            else
                break;
        }
    }
}

### Selection sort

void selectSort(vector<int>& v){
    for (int i = 0; i < v.size()-1; ++i){
        int minVal = v[i];
        int minIdx = i;
        for (int j = i+1; j < v.size(); ++j){
            if (v[j] < minVal){
                minVal = v[j];
                minIdx = j;
            }
        }
        swap(v[i], v[minIdx]);
    }
}

### Quick sort

void quickSort(vector<int>& v, int front, int back){
    if (front >= back)
        return;
    
    const int pivot = v[front];
    int i = front;
    for (int j = front+1; j <= back; ++j){
        if (v[j] < pivot)
            swap(v[j], v[++i]);
    }
    swap(v[front], v[i]);
    
    quickSort(v, front, i-1);
    quickSort(v, i+1, back);
}

### Merge sort

void merge(vector<int> &v, int front, int mid, int back){
    int idxL = 0, idxR = 0, idxV = front;
    vector<int> left(v.begin()+front, v.begin()+mid+1);
    vector<int> right(v.begin()+mid+1, v.begin()+back+1);
    
    while(idxL != left.size() && idxR != right.size()){
        if (left[idxL] < right[idxR])
            v[idxV] = left[idxL++];
        else
            v[idxV] = right[idxR++];
        
        idxV++;
    }
    
    while (idxL != left.size())
        v[idxV++] = left[idxL++];
    while (idxR != right.size())
        v[idxV++] = right[idxR++];
    
    return;
}

void mergeSort(vector<int> &v, int front, int back){
    if (front >= back) return;
    
    const int mid = (front+back)/2;
    mergeSort(v, front, mid);
    mergeSort(v, mid+1, back);
    merge(v, front, mid, back);
    
    return;
}

## [Binary Search Tree](https://pjchender.dev/dsa/dsa-bst/)


### Depth First Traversal

* In-Order(left, root, right)
smallest element to biggest element
* Pre-Order(root, left, right)
copy Tree
* Post-Order(left, right, root)
delete node

### Breadth First Traversal
Use ==queue== to store nodes.

## Bit manipulation
* Set union: A | B
* Set intersection: A & B
* Set subtraction: A & ~B
* Set bit: A |= 1 << bit
* Clear bit: A &= ~(1 << bit)
* Test bit: (A & 1 << bit) != 0
* Extract last bit A&-A
* Remove last bit A&(A-1)
* Get all 1-bits ~0

#### Count the number of ones in the binary representation

int count_one(int n) {
    int count = 0;
    while(n) {
        n = n&(n-1);
        ++count;
    }
    return count;
}

#### Is power of 4

bool isPowerOfFour(int n) {
    return !(n&(n-1)) && (n&0x55555555);
    //check the 1-bit location;
}

#### Sum of Two Integers

int getSum(int a, int b) {
    return b==0? a:getSum(a^b, (a&b)<<1); 
    //be careful about the terminating condition;
}

#### Reverse bits
##### Loop

uint32_t reverseBits(uint32_t n) {
    unsigned int mask = 1<<31, res = 0;
    for(int i = 0; i < 32; ++i) {
        if(n & 1) res |= mask;
        mask >>= 1;
        n >>= 1;
    }
    return res;
}

##### Divide and conquer

x = ((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555) << 1);
x = ((x & 0xcccccccc) >> 2) | ((x & 0x33333333) << 2);
x = ((x & 0xf0f0f0f0) >> 4) | ((x & 0x0f0f0f0f) << 4);
x = ((x & 0xff00ff00) >> 8) | ((x & 0x00ff00ff) << 8);
x = ((x & 0xffff0000) >> 16) | ((x & 0x0000ffff) << 16);