Shubham Shah

Patterns in algorithms

Patterns

Sliding window

When you want to maintain a characteristic while looping through an array.

eg. For index and for an array , keep track of the maximum number from to (both included). Here maximum number is the characteristic. We can move and and calculate values for all the subarrays.

Sliding window maximum number

Problems

Prefix sum

If you can solve a problem using a prefix sum array then it is likely that you can optimize for space and use a single integer variable prefix to solve the problem

Top K elements

We can find the top k elements by using a heap or by using quickselect algorithm

Proving algorithms

Invariants are really useful whether you are iterating or recursing. A good place to read is mathematics for computer science

Loop invariant

To prove a loop invariant we need to prove two properties

Variables

Bit manipulation

If we want the leftmost bit of a number n unset then just do n-1.

eg.

uint32_t n = 0b0010010; //Number in binary C++
cout << n - 1; //Would print 0010000

By showing you the subtraction

Using Abstraction

It is inevitable to solve complex problems without abstracting away things.

Eg. consider this question.

Let me give you a backstory. I wasn’t able to solve this problems in days if not months until the idea of abstraction hit me. I tried to solve it using weird logic which was given by people who did competitive coding and you know how they solve problems. One of the solution explained the logic well but it was hard for me to understand simply because I didn’t make it and even though I understood the solution it was hard for me to remember. Instead I needed a way where I could remember the solution very easily and I think abstraction helped me in that as well.

Iteration

Do while loop

When we want to execute an algorithm just once regardless of the condition then we make use of do while.

Eg. In below algorithm we need to find a cycle in a linked list. Although the condition is true for the first iteration we still want to execute it. The algorithm is that the fast pointer moves at twice the speed of the slow pointer. They start at the same place and if they meet again at a valid node then the linked list contains a cycle.

class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode* slow{head};
        ListNode* fast{head};

        do{
            if(fast)
                fast = fast->next;
            if(fast)
                fast = fast->next;
            if(slow)
                slow = slow->next;
        }
        while(fast != slow);

        if(fast && fast == slow){
            return true;
        }else{
            return false;
        }
    }
};

Nested while loops

Nesting while loops is hardly required. Think again when nesting them.

eg. Consider the problem of searching in a 2d matrix.

Bad:

bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int rows = matrix.size();
        int cols = matrix[0].size();
        int i = 0;
        int j = cols - 1;
        bool found{false};

        while(i < rows && j >= 0 && !found){
            while((i < rows && j >= 0) && (matrix[i][j] < target)){
                i++;
            }
            while((i < rows && j >= 0) && (matrix[i][j] > target)){
                j--;
            }
            if((i < rows && j >= 0) && (matrix[i][j] == target))
                found = true;
        }

        return found;
}

Good:

bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int rows = matrix.size();
        int cols = matrix[0].size();
        int i = 0;
        int j = cols - 1;
        bool found{false};

        while(i < rows && j >= 0 && !found){
            if(matrix[i][j] < target){
                i++;
            }
            else if(matrix[i][j] > target){
                j--;
            }
            else if(matrix[i][j] == target){
                found = true;
						}
        }

        return found;
}

Recursion

Global state

Sometimes while doing recursion we want to share some variables across the recursive calls. Instead of passing them as parameters we might make them global.

Example

While solving Leetcode: decode string we encounter that we want to share some data across recursive calls. For this we make class properties str and i which we call global variables as these are shared across all the recursive calls.

Some variables such as str doesn’t change(static). Static globals can alternatively be passed inside of the recursive call backs eg. decode(string s) but we don’t do this instead we make it a global variable.

Other type of global variables is dynamic such as i. That changes as the recursive functions. This can be seen as a global state and cannot be remedied by passing as parameters. You must define the recursive function in harmony to this global state.

Array

Dynamic programming

Definitions

memo:

A memo can be a dictionary/map or an array or a matrix which stores result of previously computed values which can be utilized.

Tips for dynamic programming algorithms:

Untitled

Steps for solving with dynamic programming.

The ideas here are derived from MIT 6.006 lectures

Backtracking

Tips

Tree

Questions

Fruits into baskets

Question

This problem is available on leetcode.

You are visiting a farm that has a single row of fruit trees arranged from left to right. The trees are represented by an integer array fruits where fruits[i] is the type of fruit the ith tree produces.

You want to collect as much fruit as possible. However, the owner has some strict rules that you must follow:

You only have two baskets, and each basket can only hold a single type of fruit. There is no limit on the amount of fruit each basket can hold. Starting from any tree of your choice, you must pick exactly one fruit from every tree (including the start tree) while moving to the right. The picked fruits must fit in one of your baskets. Once you reach a tree with fruit that cannot fit in your baskets, you must stop. Given the integer array fruits, return the maximum number of fruits you can pick.

Example 1:

Input: fruits = [1,2,1] Output: 3 Explanation: We can pick from all 3 trees. Example 2:

Input: fruits = [0,1,2,2] Output: 3 Explanation: We can pick from trees [1,2,2]. If we had started at the first tree, we would only pick from trees [0,1]. Example 3:

Input: fruits = [1,2,3,2,2] Output: 4 Explanation: We can pick from trees [2,3,2,2]. If we had started at the first tree, we would only pick from trees [1,2].

Constraints:

1 <= fruits.length <= 105

0 <= fruits[i] < fruits.length

Solution

  1. Initialize max_picked = 0 as the maximum fruits we can collect, and use hash map basket to record the types of fruits in the current window.

  2. Start with an empty window having left = 0 and right = 0 as its left and right index.

  3. We iterate over right and add fruits[right] to this window.

    • If there are no more than 2 types of fruits, this subarray is valid.
    • Otherwise, we need to keep removing fruits from the left side until there are only 2 types of fruits in the window.

    Then we update max_picked as max(max_picked, right - left + 1).

  4. Once we finish iterating, return max_picked as the maximum number of fruits we can collect.

class Solution:
    def totalFruit(self, fruits: List[int]) -> int:
        # We use a hash map 'basket' to store the number of each type of fruit.
        basket = {}
        max_picked = 0
        left = 0

        # Add fruit from the right index (right) of the window.
        for right in range(len(fruits)):
            basket[fruits[right]] = basket.get(fruits[right], 0) + 1

            # If the current window has more than 2 types of fruit,
            # we remove fruit from the left index (left) of the window,
            # until the window has only 2 types of fruit.
            while len(basket) > 2:
                basket[fruits[left]] -= 1
                if basket[fruits[left]] == 0:
                    del basket[fruits[left]]
                left += 1

            # Update max_picked.
            max_picked = max(max_picked, right - left + 1)

        # Return max_picked as the maximum number of fruits we can collect.
        return max_picked

Decode String Leetcode

Question

Given an encoded string, return its decoded string.

The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.

You may assume that the input string is always valid; there are no extra white spaces, square brackets are well-formed, etc.

Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there will not be input like 3a or 2[4].

Example 1:

Input: s = "3[a]2[bc]"
Output: "aaabcbc"

Example 2:

Input: s = "3[a2[c]]"
Output: "accaccacc"

Example 3:

Input: s = "2[abc]3[cd]ef"
Output: "abcabccdcdcdef"

Solution

This problem can be solved recursively by defining decode as follows:

class Solution {
public:
    //Global--------
    string str; //Static
    int i{0};   //Dynamic
    //Global---------

    string decodeString(string s) {
        str = s;
        return decode();
    }
    string decode(){
        string ans;
        while(i < str.size() && str[i] != ']'){
            if(isdigit(str[i])){
                string sRep;
                int rep;
                while(str[i] != '['){
                    sRep += str[i];
                    i++;
                }
                //Skip '['
                i++;
                rep = stoi(sRep);
                string inner{decode()};
                for(int j = 0; j < rep; j++){
                    ans += inner;
                }
            }else{
                ans += str[i];
                i++;
            }
        }
        //Skip ']'
        i++;
        return ans;
    }
};

Search in rotated sorted array

There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].

Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

You must write an algorithm with O(log n) runtime complexity.

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

Example 3:

Input: nums = [1], target = 0
Output: -1

Constraints:

Solution: Search in rotated sorted array(Competitive version)

This very nice idea is from rantos22’s solution who sadly only commented “You are not expected to understand that :)”, which I guess is the reason it’s now it’s hidden among the most downvoted solutions. I present an explanation and a more usual implementation.

Explanation

Let’s say nums looks like this: [12, 13, 14, 15, 16, 17, 18, 19, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

Because it’s not fully sorted, we can’t do normal binary search. But here comes the trick:

And then we can simply do ordinary binary search.

Of course we don’t actually adjust the whole array but instead adjust only on the fly only the elements we look at. And the adjustment is done by comparing both the target and the actual element against nums[0].

Code

If nums[mid] and target are “on the same side” of nums[0], we just take nums[mid]. Otherwise we use -infinity or +infinity as needed.

int search(vector<int>& nums, int target) {
    int lo = 0, hi = nums.size();
    while (lo < hi) {
        int mid = (lo + hi) / 2;

        double num = (nums[mid] < nums[0]) == (target < nums[0])
                   ? nums[mid]
                   : target < nums[0] ? -INFINITY : INFINITY;

        if (num < target)
            lo = mid + 1;
        else if (num > target)
            hi = mid;
        else
            return mid;
    }
    return -1;
}

Search in rotated sorted array (Abstracted version)

This version is very easy to understand, implement and remember(so you’ll be able to implement easily again when needed).

The search() method just implements the routine binary search.

It makes use of the inLeft abstraction which is named exactly what it does. It evaluates to true when the target can be found in the range [low, mid] i.e. from low to mid including low and mid.

The implementation of inLeft is fairly complex for this problem so go through the code and understand. I have provided comments at the place where needed.

class Solution {
public:
		//routine binary search
    int search(vector<int>& nums, int target) {
        int n = nums.size();
        long l{0};
        long h{n - 1};

        while(l < h){
            long m{(l+h)/2};
            if(inLeft(nums, target, l, m, h)){
                h = m;
            }else{
                l = m+1;
            }
        }
        //We may not be able to find the target then return -1
        if(nums[l] == target){
            return l;
        }else{
            return -1;
        }
    }
		//n: nums
		//t: target, l: low, m: mid, h: high
    //Returns true if target is in first half including mid(left) else returns false
    bool inLeft(vector<int>& n, int t, int l, int m, int h){
        //m to h would be sorted
        if(n[l] > n[m]){
            if(n[m] < t && t <= n[h]){
                return false;
            }else{
                return true;
            }
        }
        //l to m would be sorted
        else{
            //Target is in between the low and mid
            if(n[l] <= t && t <= n[m]){
                return true;
            }else{
                return false;
            }
        }
    }
};

Search in 2D Matrix

Write an efficient algorithm that searches for a target value in an m x n integer matrix. The matrix has the following properties:

Example 1:

https://assets.leetcode.com/uploads/2020/11/24/searchgrid2.jpg

Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
Output: true