đŸ‘©â€đŸ« Courses
đŸ‘©â€đŸ’»About

Data Structure & Algorithm

DSL Pattern: Sliding Window Technique

Sliding window based problems use two pointers. At any point in time only one of these pointers move and the other pointer remains fixed. Always expand the window from the right end and shrink from the left end

  • Right pointer -> to expand the current window
  • Left pointer -> to contract a given window.
  • Benefits:
    • Most of the time sliding window problems can be solved in O(n) time and O(1) space complexity.
    • Helps avoid unnecessary iteration over elements (that is usually an operation with O(n*k) or O(n^2) time complexity.
  • Where to use?
    If you are asked to find a sub-array or a substring with a specific property, use the sliding window pattern.
    • Things we iterate over sequentially i.e. contiguous sequence of elements (Strings, arrays, linked lists)
    • Key words: min, max, longest, shortest, something is contained in a given string/array
  • Question Types:
    There are two main types of windows i.e. Fixed Length Window & Dynamic Length Window
    • Fixed Length Window
      • Maximum sum subarray of size k
      • Given an array of integers, find maximum/minimum sum subarray of the required size.
    • Dynamic length window - can grow & shrink
      • Smallest sum ≄ to some value S
      • Given an array of positive integers, find the subarrays that add up to a given number.
    • Dynamic length window with auxiliary data structure
      • Longest substring with no more than k distinct characters
      • String permutations

1. Maximum sum of any contiguous subarray of size ‘k’

Question: Given an array of positive numbers and a positive number ‘k,’ find the maximum sum of any contiguous subarray of size ‘k’.

Input: [5, 3, 8, 6, 8, 3, 1, 7, 4, 0] , k=3
Output: 22
Reason: Subarray with maximum sum is [8, 6, 8]

function maxSumSubArray(array, k) {
let maxSum = 0;
let currentRunningSum = 0;
for (let idx = 0; idx < array.length; idx++) {
currentRunningSum += array[idx];
if (idx >= k - 1) {
//Determine maxSum when window size becomes k
maxSum = Math.max(maxSum, currentRunningSum);
currentRunningSum -= array[idx - (k - 1)]; //subtract the first element of current window
}
}
return maxSum;
}
console.log(maxSumSubArray([5, 3, 8, 6, 8, 3, 1, 7, 4, 0], 3));

Time Complexity:

The time complexity of the above algorithm will be O(n).

Space Complexity:

The algorithm runs in constant space O(1).

2. Minimum sum of any contiguous subarray of size ‘k’

Question: Given an array of positive numbers and a positive number ‘k,’ find the minimum sum of any contiguous subarray of size ‘k’. Input: [5,3,8,6,8,3,1,7,4,0], k=3
Output: 11
Reason: Subarray with minimum sum is [3, 1, 7] and [7,,4,0]

function minSumSubArray(array, k) {
let minSum = Infinity;
let currentRunningSum = 0;
for (let idx = 0; idx < array.length; idx++) {
currentRunningSum += array[idx];
if (idx >= k - 1) {
//Determine maxSum when window size becomes k
minSum = Math.min(minSum, currentRunningSum);
currentRunningSum -= array[idx - (k - 1)]; //subtract the first element of current window
}
}
return minSum;
}
console.log(minSumSubArray([5, 3, 8, 6, 8, 3, 1, 7, 4, 0], 3));

Time Complexity:

The time complexity of the above algorithm will be O(n).

Space Complexity:

The algorithm runs in constant space O(1).

3. Smallest Subarray with a given sum

Question: Given an array of positive numbers and a positive target number ‘target,’ find the length of the smallest contiguous subarray whose sum is greater than or equal to ‘target’. Return 0 if no such subarray exists.

Input: array = [2, 5, 1, 1, 7], S = 8
Output: 2
Reason: The smallest subarray with a sum greater than or equal to '7' is [5, 2].

function smallestSubarrayWithGivenSum(array, target) {
let smallestWinSize = 0;
let winStartIdx = 0;
let currentWinSum = 0;
for (let winEndIdx = 0; winEndIdx < array.length; winEndIdx++) {
currentWinSum += array[winEndIdx];
while (currentWinSum >= targetSum) {
smallestWinSize = Math.min(smallestWinSize, winEndIdx - winStartIdx + 1);
currentWinSum -= array[winStartIdx];
winStartIdx++;
}
}
return smallestWinSize;
}
console.log(
smallestSubarrayWithGivenSum([4, 2, 2, 7, 8, 1, 2, 8, 1, 2, 8, 10], 5)
);
console.log(smallestSubarrayWithGivenSum([2, 5, 1, 1, 7], 8));

Time Complexity:

The time complexity of the above algorithm will be O(n).

Space Complexity:

The algorithm runs in constant space O(1).

4. Longest Substring with maximum K Distinct Characters

Question: Given a string, find the length of the longest substring in it with no more than K distinct characters.

Input: String= "abbccbdgher", k=3
Output: 6 Reason: The longest substring with no more than '3' distinct characters is "abbccb".

function longestSubstringWithDistinctChar(str, k) {
let maxLength = 0;
let winStartIdx = 0;
const charMap = {};
for (let winEndIdx = 0; winEndIdx < str.length; winEndIdx++) {
const rightChar = str[winEndIdx];
if (!charMap[rightChar]) {
charMap[rightChar] = 0;
}
charMap[rightChar] += 1;
while (Object.keys(charMap).length > k) {
//If keys in map exceeds k, shrink window
const leftChar = str[winStartIdx];
charMap[leftChar] -= 1;
if (charMap[leftChar] === 0) {
delete charMap[leftChar]; //removes character from the map
}
winStartIdx += 1; //Shrink the window;
}
maxLength = Math.max(maxLength, winEndIdx - winStartIdx + 1);
}
return maxLength;
}
console.log(longestSubstringWithDistinctChar("abbccbdgher", 3));

Time Complexity:

Time complexity will be O(n), where n is the number of characters in the input string. Note that the inner while loop processes each character only once; therefore, the time complexity of the algorithm will be O(n+n), which is asymptotically equivalent to O(n).

Space Complexity

Space complexity is O(K), as we store a maximum of K+1 characters in the character map.

5. Minimum Window that contains all characters from a target substring

Question: Given a search string and a string target, find shortest sequence of characters that contains all of the characters from target string. These characters can be in any order. If target string doesn't exist in the search string, return an empty string.

Input: String= "donutsandwafflemakemehungry", target = "flea"
Output: "affle" or "flema" Reason: The minimum window (substring) which contain all the characters that are found in target is "affle" or "flema".

Aapproach: Grow your window until you have a window that contains all the characters you’re looking for. Once you find a valid window using the right pointer, start sliding the left pointer up until you no longer have a valid window (meaning you no longer have all the characters you’re looking for). Again, start moving the right pointer to again reach a valid window. Continue this process until you reach the end of the string. During the process, keep track of minimum window. Note that the smallest window will always be bounded by letters that we are searching for.

function minWindowSubstring(str, target) {
const charMap = {};
let start = 0,
matched = 0,
minLength = Infinity,
substrStart = 0;
// Create a char map to keep a count of all the unique characters in target string
for (let i = 0; i < target.length; i++) {
let char = target[i];
if (!charMap[char]) charMap[char] = 0;
charMap[char] += 1;
}
for (let end = 0; end < str.length; end++) {
let right = str[end];
if (right in charMap) {
charMap[right] -= 1;
if (charMap[right] >= 0) matched++;
}
while (matched === target.length) {
if (minLength > end - start + 1) {
minLength = end - start + 1;
substrStart = start;
}
let left = str[start];
start++;
if (left in charMap) {
if (charMap[left] === 0) matched--;
charMap[left]++;
}
}
}
return minLength > str.length
? ""
: str.substring(substrStart, substrStart + minLength);
}
console.log(minWindowSubstring("ABAACBAB", "ABC"));

Time Complexity:

The time complexity of the above algorithm will be O(n).

Space Complexity:

The algorithm runs in constant space O(1).

Additional Resources:

Dynamic Programming

"Don't repeat yourself" (DRY, or sometimes "do not repeat yourself") is a principle of software development aimed at reducing repetition of software patterns. Same rule is applied when we talk about Dynamic Programming i.e. remembering answers to the sub-problems we’ve already solved, and not solving them again.

Key attributes of DP problems:

  • Optimal substructure
  • Overlapping sub-problems

How it works?

  • Break down a complicated problem into simpler overlapping sub-problems.
  • Solve the overlapping sub-problems in an optimal way
  • Combine the results of those subproblems to find the most optimum solution.
  • Each sub-problem is solved only once (using memoization technique i.e. simply storing the solutions to the sub-problems)

When to apply Dynamic Programming?

  • When a problem can be broken into simpler over-lapping sub-problems

1. Min Number of Coins

Question: You are given an integer array denoms representing coins of different denominations and an integer amount n representing a total amount of money.

Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

Aapproach:

  • Build a dp array to store the fewest number of coins needed to create "i" change (i.e. dp[10] = the fewest number of coins to make 10 cents).
  • Solve all subproblems up to the the nth problem (aka "amount" in this problem) and return the result.

Method 1

function minNumberOfCoinsForChange(n, denoms) {
//Create an array to track coin denominators
const dp = new Array(n + 1).fill(Infinity);
dp[0] = 0;
for (const denom of denoms) {
for (let amount = 0; amount < dp.length; amount++) {
if (denom <= amount) {
dp[amount] = Math.min(dp[amount], dp[amount - denom] + 1);
}
}
}
return dp[n] == Infinity ? -1 : dp[n];
}

Method 2

function minNumberOfCoinsForChange(n, denoms) {
// Create an array to track coin denominators
const dp = new Array(n + 1).fill(n + 1);
dp[0] = 0;
for (let i = 0; i <= n; i++) {
// i denotes how many number of cents we are going to make
for (let j = 0; j < denoms.length; j++) {
if (denoms[j] <= i) {
dp[i] = Math.min(dp[i], 1 + dp[i - denoms[j]]);
}
}
}
return dp[n] > n ? -1 : dp[n];
}

2. Number of ways to make change

Question:
You are given an integer array denoms representing coins of different denominations and an integer amount n representing a total amount of money.

Return the number of combinations that make up that amount. If that amount of money cannot be made up by any combination of the coins, return 0.

You may assume that you have an infinite number of each kind of coin.

// Method 1:
function numberOfWaysToMakeChange(n, denoms) {
//Create an array to track coin denominators
// [1, 0, 0, 0, 0, 0, 0]
const coinTracking = new Array(n + 1).fill(0);
coinTracking[0] = 1;
for (let i = 0; i < denoms.length; i++) {
for (let j = denoms[i]; j < coinTracking.length; j++) {
coinTracking[j] += coinTracking[j - denoms[i]];
console.log(j, coinTracking[j]);
}
}
return coinTracking[n];
}
// Method: 2
function numberOfWaysToMakeChange2(n, denoms) {
const dp = new Array(n + 1).fill(0);
dp[0] = 1;
for (const denom of denoms) {
for (let amount = 0; amount < dp.length; amount++) {
if (denom <= amount) {
dp[amount] += dp[amount - denom];
}
}
}
return dp[n];
}
console.log(numberOfWaysToMakeChange(6, [1, 5]));
console.log(numberOfWaysToMakeChange2(6, [1, 5]));

3. Maximum sum of non adjacent elements

Write a function that takes an unsorted array of positive integers and returns the maximum sum of non-adjacent elements.

Max sum non-adjacent array

function maxSubsetSumNoAdjacent(array) {
if (array.length == 0) return 0;
let incl = array[0];
let excl = 0;
for (let i = 1; i < array.length; i++) {
const current = array[i];
newIncl = current + excl;
newExcl = Math.max(incl, excl);
incl = newIncl;
excl = newExcl;
}
return Math.max(incl, excl);
}
console.log(maxSubsetSumNoAdjacent([9, 8, 10, 100, 5, 6])); //115
console.log(maxSubsetSumNoAdjacent([75, 105, 120, 75, 90, 135])); //330
console.log(maxSubsetSumNoAdjacent([9, 8, 19, 109, 24, 115])); //233
console.log(maxSubsetSumNoAdjacent([6])); //6

4. Levenshtein distance (Minimum Edit Distance)

Question:
Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.

You have the following three operations permitted on a word:

  • Insert a character
  • Delete a character
  • Replace a character

What is Levenshtein distance?

The Levenshtein distance is a string metric for measuring the difference between two sequences. Informally, the Levenshtein distance between two words is the minimum number of single-character edits (insertions, deletions or substitutions) required to change one word into the other. It is named after the Soviet mathematician Vladimir Levenshtein, who considered this distance in 1965. (wikipedia)

For example, the Levenshtein distance between "kitten" and "sitting" is 3, since the following three edits change one into the other, and there is no way to do it with fewer than three edits:

kitten → sitten (substitution of "s" for "k") sitten → sittin (substitution of "i" for "e") sittin → sitting (insertion of "g" at the end).

Application:

  • Spell checkers
  • Finding the closest matching words in a dictionary
  • Search recommendations

Max sum non-adjacent array

Pattern

If characters at column and row positions are different:

For the selected value, check neighbouring boxes i.e box above, box to the left & the box at diagonal position. Take minimum of these 3 values & add 1. We are adding 1 here as only one additional operation is required in addition to previous operation.

`value = min(character Above, character at left, character at diagonal position) + 1`
We can write the logic as below:
`if word1[r-1] !== word2[c-1] then E[r][c] = 1 + min(E[r][c-1], E[r-1][c],E[r-1][c-1])`

If characters are same:

Copy the number that is at the diagonal position. We ignore the boxes above and at the left as the letter is same and doesn't require a change. Only the letter at diagonal position requires an update.

If we have a 2 dimensional array E as a storage to track the edit operation where rows store source word & column stores the target word then logic will be as under:

if word1[r-1] == word2[c-1] then E[r][c] = E[r-1][c-1] (diagonal position)

function levenshteinDistance(str1, str2) {
const dp = [];
for (let i = 0; i < str1.length + 1; i++) {
const row = [];
for (let j = 0; j < str2.length + 1; j++) {
row.push(j);
}
row[0] = i;
dp.push(row);
}
for (let i = 1; i < str1.length + 1; i++) {
for (let j = 1; j < str2.length + 1; j++) {
if (str1[i - 1] === str2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = 1 + Math.min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]);
}
}
}
return dp[str1.length][str2.length];
}
console.log(levenshteinDistance("abc", "yabd")); //2

5. Climbing Stairs

Question:
You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1, 2 or 3 steps. In how many distinct ways can you climb to the top?

Pattern:

Climbing Stairs

  • This question can be solved by solving smaller subproblems & then finding a solution to the bigger or original problem.
  • First determine how many ways are there to reach to the 2nd, 3rd, 4th, 5th ... and the n-1 step. Finally calculate the nth step.
  • We'll define an array named dp to track the steps. Please note that:
    • There is 1 way to climb to 0 steps i.e. don't climb the step.
    • There is 1 way to climb 1 step i.e. we climb 1 step. Here, we can't climb two steps as we only want to reach to step 1
    • Iterate through the remaining subproblems, and solve from 2 to n. The number of ways to reach the ith step is the sum of steps required for reaching the i - 1, i-2 & i-3 step plus the number of ways of reaching the i - 2 step (because we can only climb at most 3 steps).
    • Once the loop is finished, we get the solution to the number of ways to reach the nth step which is stored in dp[n]; therefore, we return dp[n].
const climbingStair = (n) => {
const dp = new Array(n + 1).fill(0);
dp[0] = 1;
for (let i = 1; i < dp.length; i++) {
if (i == 1) {
dp[i] = dp[0];
} else if (i == 2) {
dp[i] = dp[i - 1] + dp[i - 2];
} else {
dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
}
}
return dp[n];
};
console.log(climbingStair(7));

6. Climbing stairs with variable number of jumps

Question:

You are given a number n, representing the number of stairs in a staircase. You are on the 0th step and are required to climb to the top.

You are also provided with an array containing information about possible number of steps, i.e. how far you can jump in a single move at every index (or step). Print the number of different paths via which you can climb to the top.

Pattern:

Climbing Stairs With Variable Jumps

To solve this problem, define an array named dp. The ith position of this array will store number of ways to reach from position i to n.

Here, the small problem is on the left side that is to reach from i=n to i=n. The bigger problem is on the left side that is to reach from i=0 to i=n; therefore we'll solve this problem from right to left.

const climbingStairWithJump = (n, jumps) => {
const dp = new Array(n + 1).fill(0);
dp[n] = 1; //There is only one way to go from n -> n
for (let i = n - 1; i >= 0; i--) {
for (let j = 1; j <= jumps[i] && i + j < dp.length; j++) {
// we need to make sure we don't go outside array length
dp[i] = dp[i] + dp[i + j];
}
}
return dp[0];
};
console.log(climbingStairWithJump(6, [2, 3, 0, 4, 2, 2]));

7. Climb Stairs with Minimum Number of Jumps

Question:

You are given a number n, representing the number of stairs in a staircase. You are on the 0th step and you have to climb to the top with variable jumps (values given as input) and minimum move.

You are provided with an array containing information about possible number of steps, i.e. how far you can jump in a single move at every index (or step). Print the number that shows the minimum number of jumps that will take you to the top. If there is no path to the top, print null.

Pattern:

Climbing Stairs With Minimum Number Of Jumps

const climbingStairWithMinJump = (n, jumps) => {
const dp = new Array(n + 1).fill(null);
dp[n] = 0; //There is no jump required to go from n -> n
for (let i = n - 1; i >= 0; i--) {
if (jumps[i] > 0) {
let min = Infinity;
// we need to make sure we don't go outside array length
for (let j = 1; j <= jumps[i] && i + j < dp.length; j++) {
if (dp[i + j] !== null) {
min = Math.min(min, dp[i + j]);
}
}
if (min !== Infinity) {
dp[i] = min + 1;
} else {
dp[i] = null;
}
}
}
return dp[0];
};
console.log(climbingStairWithMinJump(10, [1, 1, 4, 4, 2, 3, 1, 1, 4, 1]));
console.log(climbingStairWithMinJump(10, [3, 2, 4, 2, 0, 2, 3, 1, 2, 2]));