Patterns in algorithms
Patterns
Sliding window
When you want to maintain a characteristic while looping through an array.
eg. For index
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
- We need to prove if a set of statements are true every time while the loop is running.
- We need to prove that the loop terminates for every possible input.
Variables
- Assign meaning to the variables. Meaning is a statement that describes what the variable keeps track of. The name of a variable should resemble that meaning.
- The more the number of variables the harder to program.
- Make variables out of conditionals
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.
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
- We should make a recursion tree to understand the recursive algorithm. You can also understand recursion as tree traversal of the recursive tree.
- Recursion does take space. Hence while designing a recursive algorithm when you calculate space complexity keep that in mind.
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
- Use counting sort if length of array is bound.
- In arrays check for the following inputs: duplicates, negatives, ascending elements, descending elements, zeroes, empty array, singleton 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:
- Most DP problems are optimization problems where we have to find the min or max of a property. Apart from that, sometimes we encounter problems where we return the total count of some property like in Fibonnaci numbers. Sometimes we counter cases where we want to find if a certain proposition is true or not like in Wildcard matching.
- DP is careful brute force. Try to come up with a brute force solution and then optimize it seeing the substructure.
- When you are building a recursive solution and you find overlapping subproblems then you should use a memo and thus it converts to a dynamic programming problem. eg. Below is a recursive function which has a overlapping substructure. You can see that
recur(0,1)
andrecur(1, 0)
utilize the value ofrecur(1,1)
and thus have an overlapping substructure. If a memo is not used then it needs to compute the problem again.
- Use parent pointers to reconstruct the solution as in MIT 6.006.
Steps for solving with dynamic programming.
The ideas here are derived from MIT 6.006 lectures
- Define subproblem. Eg. For text justification it is dp(i) when recursive approach (or dp[i] when doing bottom up iterative approach) which is defined as the minimum badness for the text starting after word i.In another words it would be least badness from i to n. n is the length of text.
- Guess and break the current subproblem in such a way that it stays in the same structure of original subproblem. Now when we say we break line at j and assume we know the answer for the badness of rest of the text starting from j. Eg. Our guess was to at which word we would begin the next line. This would mean to calculate min(badness(i,j) +dp(j)) where j can range from i+1 to n.
- Build the recurrence relation and also check base cases. The above we have already given a recurrence relation.
- Check for a topological order of which dp(i) would be calculated first. We can clearly see that the value of i in dp(i) becomes 0,1,…n-1. Hence the topo order in which we would have answer is n, n-1, … 0.
- Check if we solve our original problem. Our original problem here is dp(0)
Backtracking
Tips
- We have a set of choices that we can perform, eg. We can fill 1-9 in an unfilled cell in sudoku.
- We have some constraints over the choices. Eg. We need to check if there is no duplicate number in that row, column or sub-matrix.
- We have to undo it if we don’t reach a solution. Eg. If we aren’t able to place a number and we’re stuck then we need to delete values from all the filled cells.
Tree
- Inorder traversal of a binary search tree selects the nodes in sorted increasing order
- Trees can be represented as two forms.
- As a graph whether adjacency list, matrix or edge list.
- As a rooted tree where it is represented as nodes where each node may have children which is represented as an array of Node and a parent Node. We also have a reference to the root of a node. This is the favourite form when performing recursion on trees. If it’s a binary tree then children can be represented with two pointer left and right instead of array.
- When using recursion in trees it might use space of O(n) in the worst case. The worst case being a linear tree.
- Morris traversal is a way to do inorder, pre and post order traversals in O(1) Space. We establish links to the successor and restore them to original as we traverse.
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
-
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. -
Start with an empty window having left = 0 and right = 0 as its left and right index.
-
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)
. -
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:
- Go through the string and copy to the answer until you find a number.
- When you find a number the rest of the string would be of the form
number[subproblem]subproblem
. Therefore find the subproblem in[]
and repeat it a number of times. - Now
i
would be on]
after solving the subproblem so skip it and return.
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:
1 <= nums.length <= 5000
104 <= nums[i] <= 104
- All values of
nums
are unique. nums
is an ascending array that is possibly rotated.104 <= target <= 104
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:
- If target is let’s say 14, then we adjust
nums
to this, where “inf” means infinity:[12, 13, 14, 15, 16, 17, 18, 19, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf] - If target is let’s say 7, then we adjust
nums
to this:[-inf, -inf, -inf, -inf, -inf, -inf, -inf, -inf, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
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:
- Integers in each row are sorted in ascending from left to right.
- Integers in each column are sorted in ascending from top to bottom.
Example 1:
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