Sliding window coding pattern

38 min readAug 25, 2024

The sliding window concept is used to handle problems involving subarrays or substrings of a given data structure. It creates a “window” of a specific size that moves through the data, performs operations on the elements within the window at each step.

On high level, there are two types of sliding window

Fixed Sliding window

A fixed window size is used to scan the input data and slide it to include the new item and remove the old item.

2. Dynamically resizable sliding window

Window size grows based on criteria. It does shrink from left as per problem optimization. It keeps growing/shrinking. Eventually it grows to the point at the end of the array.

Based on different type of problem we either choose fixed size dynamic window or dynamic size sliding window.

In this post, I will go through various problem to understand this technique better and try to solve many related problems.

Coding pattern

To solve both fixed and sliding window, we can take following template.

// Track window left and right boundary
let left=0;
let right =0;
// Track the ans
let ans = 0;
let localAns = 0;
// Use right boundary to scan the each item
for (let right=0; right < n; right++) {
  const item = input[right];
  // Update local ans with the new item blindly
  localAns = update local ans with item;
  // Check for violation
  -- fixed window: violation based on size or other condition
  -- dynamic window: violation based on given problem condition
  // Handle violation
  -- Fixed window: Remove the left item and update the local ans and other state
  -- dynamic window: Keep removing left item until violation is not fixed
// Check for ans eligibility and update ans
}

Fixed length window size problems

346. Moving Average from Data Stream

https://leetcode.com/problems/moving-average-from-data-stream/description/

Given a stream of integers and a window size, calculate the moving average of all integers in the sliding window.

Implement the MovingAverage class:

MovingAverage(int size) Initializes the object with the size of the window size.
double next(int val) Returns the moving average of the last size values of the stream.

Example 1:

Input
["MovingAverage", "next", "next", "next", "next"]
[[3], [1], [10], [3], [5]]
Output
[null, 1.0, 5.5, 4.66667, 6.0]

Approach

Since window size is fixed therefore we can apply fixed sliding window concept here.

Time complexity: O(1)

Space complexity: O(size)

Following is code reference.

/**
 * Initialize your data structure here.
 * @param {number} size
 */
var MovingAverage = function (size) {
    this.size = size;
    this.window = [];
    this.sum = 0;
};

/** 
 * @param {number} val
 * @return {number}
 */
MovingAverage.prototype.next = function (val) {
    // Update local state
    this.window.push(val);
    this.sum += val;


    // Handle violation
    if (this.window.length > this.size) {
        const last = this.window.shift();
        this.sum -= last;
    }
    // calculate ans
    return this.sum / this.window.length;;
};

643. Maximum Average Subarray I

https://leetcode.com/problems/maximum-average-subarray-i/description/

You are given an integer array nums consisting of n elements, and an integer k.

Find a contiguous subarray whose length is equal to k that has the maximum average value and return this value. Any answer with a calculation error less than 10-5 will be accepted.

Example 1:

Input: nums = [1,12,-5,-6,50,3], k = 4
Output: 12.75000
Explanation: Maximum average is (12 - 5 - 6 + 50) / 4 = 51 / 4 = 12.75

Approach

We can apply fixed sliding window and keep track of running max avg to get the answer.

Time complexity: O(n)

Space complexity: O(1)

Following is code for reference.

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findMaxAverage = function (nums, k) {
    const n = nums.length;
    let sum = 0;
    let ans = Number.MIN_SAFE_INTEGER;
    let left = 0;
    for (let right = 0; right < n; right++) {
        // Update state
        sum += nums[right];

        // Check for violation
        if (right - left >= k) {
            sum -= nums[left];
            left++;
        }
        // Ans check only if reach the size
        if (right - left === k - 1) {
            ans = Math.max(ans, sum)
        }
    }
    return ans / k;
};

1343. Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold

https://leetcode.com/problems/number-of-sub-arrays-of-size-k-and-average-greater-than-or-equal-to-threshold/description/

Given an array of integers arr and two integers k and threshold, return the number of sub-arrays of size k and average greater than or equal to threshold.

Example 1:

Input: arr = [2,2,2,2,5,5,5,8], k = 3, threshold = 4
Output: 3
Explanation: Sub-arrays [2,5,5],[5,5,5] and [5,5,8] have averages 4, 5 and 6 respectively. All other sub-arrays of size 3 have averages less than 4 (the threshold).

Approach

We can apply fixed sliding window to solve this problem. Followng is code for reference.

/**
 * @param {number[]} arr
 * @param {number} k
 * @param {number} threshold
 * @return {number}
 */
var numOfSubarrays = function (arr, k, threshold) {
    const n = arr.length;
    let sum = 0;
    let ans = 0;
    let left = 0;
    for (let right = 0; right < n; right++) {
        // Update state
        sum += arr[right];

        // Check for violation
        if (right - left >= k) {
            sum -= arr[left];
            left++;
        }
        // Ans check only if reach the size and satisfy the condition
        if (right - left === k - 1) {
            const avg = sum / k;
            if (avg >= threshold) {
                ans++;
            }
        }
    }
    return ans;
};

1176. Diet Plan Performance

https://leetcode.com/problems/diet-plan-performance/description/

A dieter consumes calories[i] calories on the i-th day.

Given an integer k, for every consecutive sequence of k days (calories[i], calories[i+1], ..., calories[i+k-1] for all 0 <= i <= n-k), they look at T, the total calories consumed during that sequence of k days (calories[i] + calories[i+1] + ... + calories[i+k-1]):

If T < lower, they performed poorly on their diet and lose 1 point;
If T > upper, they performed well on their diet and gain 1 point;
Otherwise, they performed normally and there is no change in points.

Initially, the dieter has zero points. Return the total number of points the dieter has after dieting for calories.length days.

Note that the total points can be negative.

Example 1:

Input: calories = [1,2,3,4,5], k = 1, lower = 3, upper = 3
Output: 0

Approach

We can apply fixed sliding window to solve this problem. Following is code for reference.

/**
 * @param {number[]} calories
 * @param {number} k
 * @param {number} lower
 * @param {number} upper
 * @return {number}
 */
var dietPlanPerformance = function (calories, k, lower, upper) {
    const n = calories.length;
    let total = 0;
    let ans = 0;
    let left = 0;
    for (let right = 0; right < n; right++) {
        // process new cell
        total += calories[right];

        // Handle violation
        if (right - left >= k) {
            total -= calories[left];
            left++;
        }
        // Process ans
        if (right - left === k - 1) {
            if (total < lower) {
                ans--;
            } else if (total > upper) {
                ans++;
            }
        }
    }
    return ans;
};

1052. Grumpy Bookstore Owner

https://leetcode.com/problems/grumpy-bookstore-owner/description/

There is a bookstore owner that has a store open for n minutes. Every minute, some number of customers enter the store. You are given an integer array customers of length n where customers[i] is the number of the customer that enters the store at the start of the ith minute and all those customers leave after the end of that minute.

On some minutes, the bookstore owner is grumpy. You are given a binary array grumpy where grumpy[i] is 1 if the bookstore owner is grumpy during the ith minute, and is 0 otherwise.

When the bookstore owner is grumpy, the customers of that minute are not satisfied, otherwise, they are satisfied.

The bookstore owner knows a secret technique to keep themselves not grumpy for minutes consecutive minutes, but can only use it once.

Return the maximum number of customers that can be satisfied throughout the day.

Example 1:

Input: customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], minutes = 3
Output: 16

Approach

We can first find out the total number of satisfied customers without book owners applying the secret technique. Let’ say it is total .
Since book owner can only apply secret technique once therefore to maximize the total we need to know the max number of not satisfied customer for the given window minute throughout the day.
We can apply fixed window on minute to find out the max number of not satisfied customers.
These max number of not satisfied customers will be additional satisfied customers i.e. total + max will be the answer.

Following is code for reference.

/**
 * @param {number[]} customers
 * @param {number[]} grumpy
 * @param {number} minutes
 * @return {number}
 */
var maxSatisfied = function (customers, grumpy, minutes) {
    const satisfied = customers.reduce((sum, num, i) => {
        return sum + num * (grumpy[i] ^ 1)
    }, 0);

    const n = customers.length;
    let max = 0;
    let local = 0;
    let left = 0;
    // Apply minutes length fixed sliding window
    for (let right = 0; right < n; right++) {
        // Count not satisfied customer
        if (grumpy[right] === 1) {
            local += customers[right];
        }

        // handle violation
        if (right - left >= minutes) {
            // Slide window
            if (grumpy[left] === 1) {
                local -= customers[left];
            }
            left++;
        }

        // Check for answer
        if (right - left + 1 === minutes) {
            max = Math.max(max, local);
        }
    }
    return satisfied + max;
};

1456. Maximum Number of Vowels in a Substring of Given Length

https://leetcode.com/problems/maximum-number-of-vowels-in-a-substring-of-given-length/description/

Given a string s and an integer k, return the maximum number of vowel letters in any substring of s with length k.

Vowel letters in English are 'a', 'e', 'i', 'o', and 'u'.

Example 1:

Input: s = "abciiidef", k = 3
Output: 3

Approach

We can apply fixed sliding window. Following is code for reference.

/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 */
var maxVowels = function (s, k) {
    const vowels = new Set(['a', 'e', 'i', 'o', 'u']);
    let ans = 0;
    let total = 0;
    let left = 0;
    const n = s.length;
    for (let right = 0; right < n; right++) {
        const chr = s[right];

        // Record vowels
        if (vowels.has(chr)) {
            total++;
        }
        // Check for voilation
        if (right - left >= k) {
            // slide window
            if (vowels.has(s[left])) {
                total--
            }
            left++;
        }
        // Check for answer
        if (right - left === k - 1) {
            ans = Math.max(ans, total);
        }
    }
    return ans;
};

1100. Find K-Length Substrings With No Repeated Characters

https://leetcode.com/problems/find-k-length-substrings-with-no-repeated-characters/description/

Given a string s and an integer k, return the number of substrings in s of length k with no repeated characters.

Example 1:

Input: s = "havefunonleetcode", k = 5
Output: 6
Explanation: There are 6 substrings they are: 'havef','avefu','vefun','efuno','etcod','tcode'.

Approach

We can apply fixed sliding window
To maintain the no repeated chars, we can map variable to track the frequency of char.
If k === map.size then this would be the case when there is no repeating chars. This will be included as answer.
On violation, shrink window from left. We will remove char from map.

Following is code for the reference.

/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 */
var numKLenSubstrNoRepeats = function (s, k) {
    const n = s.length;
    let ans = 0;
    const map = new Map();
    let left = 0;
    for (let right = 0; right < n; right++) {
        // process new cell
        const chr = s[right];
        map.set(chr, map.has(chr) ? map.get(chr) + 1 : 1);

        // Handle violation
        if (right - left >= k) {
            // Slide window
            const chr = s[left];
            map.set(chr, map.get(chr) - 1);
            if (map.get(chr) === 0) {
                map.delete(chr);
            }
            left++;
        }
        // Calcualte ans
        if (right - left === k - 1) {
            if (map.size === k) {
                ans++;
            }
        }
    }
    return ans;

};

239. Sliding Window Maximum

https://leetcode.com/problems/sliding-window-maximum/description/

You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

Return the max sliding window.

Example 1:

Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]
Explanation: 
Window position                Max
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

Approach

This is a problem of fixed sliding window.
Finding max num efficiently in the given window is a critical task.
Goal is to find out max num in O(1) . We can scan the window but that would be O(k) so not efficient.
One standard way to find out max is using monotonic decreasing stack/queue.
Since on shrinking window, we will need to remove left most therefore we need to use double ended queue for monotonic decreasing queue.
Instead of tracking separate left variable, we can use first item of queue as left pointer.
It means, instead of value, we will have to keep track of index in the queue.
Following is details to show case how we can use monotonic decreasing stack to find out the max number in constant time.

Following is code for referece.

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> q; // monotonic decreasing q
        vector<int> ans;
        int n = nums.size();
        for (int right = 0; right < n; right++) {
            // insert new element to q
            while (!q.empty() && nums[q.back()] < nums[right]) {
                q.pop_back(); // remove last elememt
            }
            q.push_back(right);
            // Handle violation
            if (right - q.front() + 1 == k + 1) {
                q.pop_front();
            }
            // ans zone
            if (right >= k - 1) {
                ans.push_back(nums[q.front()]);
            }
        }
        return ans;
    }
};

1151. Minimum Swaps to Group All 1’s Together

https://leetcode.com/problems/minimum-swaps-to-group-all-1s-together/description/

Given a binary array data, return the minimum number of swaps required to group all 1’s present in the array together in any place in the array.

Example 1:

Input: data = [1,0,1,0,1,0,0,1,1,0,1]
Output: 3

Approach

Only 0 insdie the 1 needs to be swap. It means, we need to find a pattern of 1xxxxxxx1 .
It means we need to fist count number of 1 in the array. That will give us the window size.
We can run the fix sliding window to find out the minimum number of zeros present in the window, that will gives the minimum number of swap needed to keep all the ones together.

Following is code for reference.

/**
 * @param {number[]} data
 * @return {number}
 */
var minSwaps = function (data) {
    // Count number of ones i.e. k will be the size of fixed sliding window
    const k = data.reduce((sum, num) => sum + num, 0)
    const n = data.length;
    let left = 0;
    let zeros = 0;
    // Let's calcualte ans i.e. min number of zeros in the sliding window
    let ans = n - k; // Initialize with 
    for (let right = 0; right < n; right++) {
        if (data[right] === 0) {
            zeros++;
        }
        // handle violation
        if (right - left >= k) {
            if (data[left] === 0) {
                zeros--;
            }
            left++;
        }
        // Calculate ans for k size fixed window only
        if (right - left === k - 1) {
            ans = Math.min(ans, zeros);
        }
    }
    return ans;
};

1703. Minimum Adjacent Swaps for K Consecutive Ones

https://leetcode.com/problems/minimum-adjacent-swaps-for-k-consecutive-ones/description/

You are given an integer array, nums, and an integer k. nums comprises of only 0's and 1's. In one move, you can choose two adjacent indices and swap their values.

Return the minimum number of moves required so that nums has k consecutive 1's.

Example 1:

Input: nums = [1,0,0,1,0,1], k = 2
Output: 1
Explanation: In 1 move, nums could be [1,0,0,0,1,1] and have 2 consecutive 1's.

Approach

For example [1,0,0,1,0,1] , we can either move 1 at 0th index to right to keep it close with 1 at 3rd index in two moves or 1 at 5th index to left to keep it close with 1 at 3rd index in one move.
It is clear that we just need to keep track of index of 1 , we don’t need to track the position of 0 .
First 1 at index i if needs to move to second 1 at index j then it needs to make |i-j-1| moves.
Once 1 is moved then it’s position is also updated.
We can prepare the index array for 1 , in this example we can work on array as [0,3,5] .
Now we can apply fixed sliding window of size k to calculate the number of moves to make all 1 together. We can keep sliding window and keep track of minimum number of moves which makes all ones in that window together as answer.
Now our main problem is to find out number of moves in the window of k size to make all one together.
One approach is to choose median element in the window and moves everything from left and right to the median element.
In case of odd length, we can choose middle element as center point. In case of even length, we can pick first element from center (we can also choose second).

Let’s try to understand how we can calcualte the number of moves with following example.

nums = [0 0 0 1 0 1 0 1 0 1  0  1]
        0 1 2 3 4 5 6 7 8 9 10 11 
index of one = [3,5,7,9,11]
median = 7
Goal: Move everything towards 7
cost = [3(5-3),5(7-5),7,9(9-7),11(11-9)]
     = sum(median, right) -  sum(left,...median)
     = (prefix[right] - prefix[median+1]) - (prefix[median] - prefix[left+1])    
Radius  = (k-1)/2;
Extra save  = (radious+1) * radious
Note: For even k size, we will have to do extra for following 
cost = cost - index[median];
radious = (k-2)/2
save = (radious+1) * radious - (radious+1)

Note: Instead of prefix sum, we can also use bruteforce to get the sum of moves.

Based on above approach, we can write code as below.

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var minMoves = function (nums, k) {
    const index = [];
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] === 1) {
            index.push(i);
        }
    }

    const n = index.length;
    const prefix = new Array(n + 1).fill(0);
    for (let i = 1; i < n + 1; i++) {
        prefix[i] = prefix[i - 1] + index[i - 1];
    }

    let res = Infinity;

    // Odd case
    if (k % 2 === 1) {
        const radius = (k - 1) / 2;
        for (let median = radius; median < n - radius; median++) {
            const left = median - radius;
            const right = median + radius;
            const rightCost = prefix[right + 1] - prefix[median + 1];
            const leftCost = prefix[median] - prefix[left];
            res = Math.min(res, rightCost - leftCost);
        }
        return res - radius * (radius + 1);
    } else {
        // Even case
        const radius = (k - 2) / 2;
        for (let median = radius; median < n - radius - 1; median++) {
            const left = median - radius;
            const right = median + radius + 1;
            const rightCost = prefix[right + 1] - prefix[median + 1];
            const leftCost = prefix[median] - prefix[left];
            res = Math.min(res, rightCost - leftCost - index[median]);
        }
        return res - radius * (radius + 1) - (radius + 1);
    }
};

683. K Empty Slots

https://leetcode.com/problems/k-empty-slots/description/

You have n bulbs in a row numbered from 1 to n. Initially, all the bulbs are turned off. We turn on exactly one bulb every day until all bulbs are on after n days.

You are given an array bulbs of length n where bulbs[i] = x means that on the (i+1)th day, we will turn on the bulb at position x where i is 0-indexed and x is 1-indexed.

Given an integer k, return the minimum day number such that there exists two turned on bulbs that have exactly k bulbs between them that are all turned off. If there isn't such day, return -1.

Example 1:

Input: bulbs = [1,3,2], k = 1
Output: 2
Explanation:
On the first day: bulbs[0] = 1, first bulb is turned on: [1,0,0]
On the second day: bulbs[1] = 3, third bulb is turned on: [1,0,1]
On the third day: bulbs[2] = 2, second bulb is turned on: [1,1,1]
We return 2 because on the second day, there were two on bulbs with one off bulb between them.

Approach

We have bulbs which tells us that on ith day, we need to turn on bulbs[i] th bulb.
We can also maintain days[] to tells us that ith bulb was turned on days[i] day.

It means we will have following for days[]

bulbs = [1,3,2]
days  = [1,3,2]

We wanted to find candidate intervals [left, right] where days[left], days[right] are the two smallest values in [days[left], days[left+1], ..., days[right]], and right - left = k + 1.

Following is code for reference.

const slidingWindow = (bulbs, k) => {
    const n = bulbs.length;
    const days = new Array(n).fill(0); // ith bulb which was turned on x days
    
    // Turn on bulbs and store the day when bulb was turned on
    for (let i=0; i < n; i++) {
        const pos = bulbs[i] - 1;
        days[pos] = i + 1;
    }
    let ans = Number.MAX_SAFE_INTEGER;
    let left = 0;
    let right = k + 1;
    while ( right < n) {
        let valid = true;
        // check if all bulbs were not turned on between left and right days
        for (let current = left + 1; current < right; current++) {

            // in case if violation break
            if( days[current] < days[left] || days[current] < days[right]) {
                left = current;
                right = current + k + 1;
                valid = false;
                break;
            } 
        }
        if(!valid) {
            continue;
        }
        // update ans
        ans = Math.min(ans, Math.max(days[left], days[right]));                                   
        // slide window
        left = right;
        right = right + k  + 1;        

    }
    return ans < Number.MAX_SAFE_INTEGER ? ans : -1;
}

567. Permutation in String

https://leetcode.com/problems/permutation-in-string/

Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise.

In other words, return true if one of s1's permutations is the substring of s2.

Example 1:

Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: s2 contains one permutation of s1 ("ba").

Approach

We can apply fixed sliding window of size(s1) on s2 to find out substring contains all the chars from s1 . We can take following approach.

Build a frequency map of char ins1 .
While running sliding window of size k (k=len(s1)), on every new char, remove char from map . if key frequency become zero then update the zeroCounter
On sliding window, add left char if it is in s1. Update zeroCounter if there is change.

Following is code for reference.

/**
 * @param {string} s1
 * @param {string} s2
 * @return {boolean}
 */
var checkInclusion = function (s1, s2) {
    const map = new Map();
    for (const chr of s1) {
        map.set(chr, map.has(chr) ? map.get(chr) + 1 : 1);
    }
    let left = 0;
    const k = s1.length;
    const n = s2.length;
    let zeroCount = 0;
    for (let right = 0; right < n; right++) {
        const chr = s2[right];
        // process chr
        if (map.has(chr)) {
            map.set(chr, map.get(chr) - 1);
            if (map.get(chr) === 0) {
                zeroCount++;
            }
        }
        // Check for violation
        if (right - left >= k) {
            const chr = s2[left];
            if (map.has(chr)) {
                if (map.get(chr) === 0) {
                    zeroCount--;
                }
                map.set(chr, map.get(chr) + 1);
            }
            left++;
        }
        // Ans area
        if (right - left == k - 1 && map.size === zeroCount) {
            return true;
        }
    }
    return false;
};

1297. Maximum Number of Occurrences of a Substring

https://leetcode.com/problems/maximum-number-of-occurrences-of-a-substring/description/

Given a string s, return the maximum number of occurrences of any substring under the following rules:

The number of unique characters in the substring must be less than or equal to maxLetters.
The substring size must be between minSize and maxSize inclusive.

Example 1:

Input: s = "aababcaab", maxLetters = 2, minSize = 3, maxSize = 4
Output: 2
Explanation: Substring "aab" has 2 occurrences in the original string.
It satisfies the conditions, 2 unique letters and size 3 (between minSize and maxSize).

Approach

Goal here is to find out max occurrence of substring which satisfies the rules.
We can fixed sliding window for size in the range of minSize and maxSize
Track the global ans

Following is code for reference.

const runFixedSlidingWindow = (s, k, maxLetters) => {
    const n = s.length;
    const map = new Map();
    const ansMap = new Map();
    let ans = 0;
    let left = 0;
    for (let right = 0; right < n; right++) {
        const chr = s[right];
        map.set(chr, map.has(chr) ? map.get(chr) + 1 : 1);

        // Handle violation
        if (right - left >= k) {
            const chr = s[left];
            map.set(chr, map.get(chr) - 1);
            if (map.get(chr) === 0) {
                map.delete(chr);
            }
            left++;
        }

        // Ans zone
        if (right - left === k - 1 && map.size <= maxLetters) {
            const sub = s.substring(left, right + 1);
            ansMap.set(sub, ansMap.has(sub) ? ansMap.get(sub) + 1 : 1);
            ans = Math.max(ans, ansMap.get(sub));
        }
    }
    return ans;
}
/**
 * @param {string} s
 * @param {number} maxLetters
 * @param {number} minSize
 * @param {number} maxSize
 * @return {number}
 */
var maxFreq = function (s, maxLetters, minSize, maxSize) {
    let ans = 0;
    // Try all possible fixed sliding window i.e. possible substring size
    for (let k = minSize; k <= maxSize; k++) {
        const local = runFixedSlidingWindow(s, k, maxLetters);
        ans = Math.max(ans, local);
    }
    return ans;
};

Dynamic sliding window size problems

209. Minimum Size Subarray Sum

https://leetcode.com/problems/minimum-size-subarray-sum/

Given an array of positive integers nums and a positive integer target, return the minimal length of a subarray whose sum is greater than or equal to target. If there is no such subarray, return 0 instead.

Example 1:

Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: The subarray [4,3] has the minimal length under the problem constraint.

Approach

Goal here is to find out the minimum size of window which gives sum greater than or equal to target.
As per problem, since nums is array of positive integer therefore sum of window will be a growing number.
If global sum exceeds target then no need to add more number to check answer as adding more positive number will keep making sum larger than target
It means, at this time we can shrink window and reduce the sum .
Every time sum stisfies the answer, we will update the global answer.

Following is code for reference.

/**
 * @param {number} target
 * @param {number[]} nums
 * @return {number}
 */
var minSubArrayLen = function (target, nums) {
    const n = nums.length;
    let left = 0;
    let ans = n + 1; // To handle no such subarray use case
    let sum = 0;
    for (let right = 0; right < n; right++) {
        // Process new num
        sum += nums[right];

        // Handle violation as well as ans area
        while (sum >= target) {
            // Calcualte ans
            const size = right - left + 1;
            ans = Math.min(ans, size);

            // shrink window
            sum -= nums[left];
            left++;
        }
    }
    return ans === n + 1 ? 0 : ans;

};

485. Max Consecutive Ones

https://leetcode.com/problems/max-consecutive-ones/description/

Given a binary array nums, return the maximum number of consecutive 1's in the array.

Example 1:

Input: nums = [1,1,0,1,1,1]
Output: 3
Explanation: The first two digits or the last three digits are consecutive 1s. The maximum number of consecutive 1s is 3.

Approach

Binary array means value can be either 0 or 1
Goal here is to find out the max window of consecutive 1
We can keep expanding window on seeing 1 and keep track of window size.
Moment we see 0 , we can shrink entire window.
Every time we see 1 , we can update the answer

Following is code for reference.

/**
 * @param {number[]} nums
 * @return {number}
 */
var findMaxConsecutiveOnes = function (nums) {
    const n = nums.length;
    let ans = 0;
    let left = 0;
    for (let right = 0; right < n; right++) {
        // Handle violation,  shrinking till current pointer to right
        if (nums[right] === 0) {
            left = right + 1;
        }
        // Ans zone
        else {
            ans = Math.max(ans, right - left + 1);
        }
    }
    return ans;
};

We can also write code in following pattern which helps to solve followup problems.

Keep track of total zeros seen so far.
If zeros>0 it means we have a violation therefore keep shrinking window from left until violation resolved.
If no violation means, we have an ans area

/**
 * @param {number[]} nums
 * @return {number}
 */
var findMaxConsecutiveOnes = function (nums) {
    const n = nums.length;
    let ans = 0;
    let left = 0;
    let zeros = 0;
    for (let right = 0; right < n; right++) {
        if (nums[right] === 0) {
            zeros++;
        }
        // Handle violation
        while (zeros > 0) {
            if (nums[left] === 0) {
                zeros--;
            }
            left++;
        }
        // Ans zone
        ans = Math.max(ans, right - left + 1);
    }
    return ans;
};

487. Max Consecutive Ones II

https://leetcode.com/problems/max-consecutive-ones-ii/description/

Given a binary array nums, return the maximum number of consecutive 1's in the array if you can flip at most one 0.

Example 1:

Input: nums = [1,0,1,1,0]
Output: 4

Approach

In above approach, we can now tolerate violation on zeros > 1 instead of zeros >0

Following is updated code for reference.

/**
 * @param {number[]} nums
 * @return {number}
 */
var findMaxConsecutiveOnes = function (nums) {
    const n = nums.length;
    let ans = 0;
    let left = 0;
    let zeros = 0;
    for (let right = 0; right < n; right++) {
        if (nums[right] === 0) {
            zeros++;
        }
        // Handle violation (at least one zero is tolerated)
        while (zeros > 1) {
            if (nums[left] === 0) {
                zeros--;
            }
            left++;
        }
        // Ans zone
        ans = Math.max(ans, right - left + 1);
    }
    return ans;
};

1004. Max Consecutive Ones III

https://leetcode.com/problems/max-consecutive-ones-iii/description/

Given a binary array nums and an integer k, return the maximum number of consecutive 1's in the array if you can flip at most k 0's.

Example 1:

Input: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2
Output: 6

Approach

In previous problem approach to use the dynamic sliding window, we can simply update the violation condition to zeros > k to solve this problem.

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var longestOnes = function(nums, k) {
    const n = nums.length;
    let ans = 0;
    let left = 0;
    let zeros = 0;
    for (let right = 0; right < n; right++) {
        if (nums[right] === 0) {
            zeros++;
        }
        // Handle violation (at least k zeros are tolerated)
        while (zeros > k) {
            if (nums[left] === 0) {
                zeros--;
            }
            left++;
        }
        // Ans zone
        ans = Math.max(ans, right - left + 1);
    }
    return ans;    
};

Dynamic window size with auxiliary data structure

159. Longest Substring with At Most Two Distinct Characters

https://leetcode.com/problems/longest-substring-with-at-most-two-distinct-characters/description/

Given a string s, return the length of the longest substring that contains at most two distinct characters.

Example 1:

Input: s = "eceba"
Output: 3
Explanation: The substring is "ece" which its length is 3.

Approach

Since we need to scan every possible substring therefore we can apply dynamic sliding window.
Goal is to keep track of distinct chars in the substring, we can use frequency map to track each chars.
Problem is asking for at most two distinct chars.
It means, if map has more than two distinct chars then we can treat this as a violation and shrink the window.
On shrining window, we can remove the left most from the map.

Following is code for reference.

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstringTwoDistinct = function (s) {
    const n = s.length;
    let ans = 0;
    let left = 0;
    const map = new Map();
    for (let right = 0; right < n; right++) {
        // process chr
        const chr = s[right];
        map.set(chr, map.has(chr) ? map.get(chr) + 1 : 1);

        // Handle violation
        while (map.size > 2) {
            const chr = s[left];
            map.set(chr, map.get(chr) - 1);
            if (map.get(chr) === 0) {
                map.delete(chr);
            }
            left++;
        }
        // Ans zone
        ans = Math.max(ans, right - left + 1);
    }
    return ans;
};

340. Longest Substring with At Most K Distinct Characters

https://leetcode.com/problems/longest-substring-with-at-most-k-distinct-characters/description/

Given a string s and an integer k, return the length of the longest substring of s that contains at most k distinct characters.

Example 1:

Input: s = "eceba", k = 2
Output: 3
Explanation: The substring is "ece" with length 3.

Approach

We can apply approach same as previous problem with modified condition on at most k chars. Following is code for reference with only change as map.size > k.

/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 */
var lengthOfLongestSubstringKDistinct = function (s, k) {
    const n = s.length;
    let ans = 0;
    let left = 0;
    const map = new Map();
    for (let right = 0; right < n; right++) {
        // process chr
        const chr = s[right];
        map.set(chr, map.has(chr) ? map.get(chr) + 1 : 1);

        // Handle violation
        while (map.size > k) {
            const chr = s[left];
            map.set(chr, map.get(chr) - 1);
            if (map.get(chr) === 0) {
                map.delete(chr);
            }
            left++;
        }
        // Ans zone
        ans = Math.max(ans, right - left + 1);
    }
    return ans;
};

1446. Consecutive Characters

https://leetcode.com/problems/consecutive-characters/

The power of the string is the maximum length of a non-empty substring that contains only one unique character.

Given a string s, return the power of s.

Example 1:

Input: s = "leetcode"
Output: 2
Explanation: The substring "ee" is of length 2 with the character 'e' only.

Appraoch

This is again same as previous approach, we can simply change to map.size > 1 as below.

/**
 * @param {string} s
 * @return {number}
 */
var maxPower = function (s) {
    const n = s.length;
    let ans = 0;
    const map = new Map();
    let left = 0;
    for (let right = 0; right < n; right++) {
        // process chr
        const chr = s[right];
        map.set(chr, map.has(chr) ? map.get(chr) + 1 : 1);

        // Handle violation
        while (map.size > 1) {
            const chr = s[left];
            map.set(chr, map.get(chr) - 1);
            if (map.get(chr) === 0) {
                map.delete(chr);
            }
            left++;
        }

        // Ans zone
        ans = Math.max(ans, right - left + 1);
    }
    return ans;
};

424. Longest Repeating Character Replacement

https://leetcode.com/problems/longest-repeating-character-replacement/description/

You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times.

Return the length of the longest substring containing the same letter you can get after performing the above operations.

Example 1:

Input: s = "ABAB", k = 2
Output: 4

Approach

Goal here is to find out the longest substring of same letters.
We have options to replace any of k chars to other chars.
If k=0 then we just need to find out substring with max duplicate chars size.
It means in a given sliding window, we can tolerate of k-maxOccurance chars only. If more then need to shrink window.
[AAABCAAA] with k=2 and maxOccurance=6 means size = right(7) — left(0) + 1 to tolerate should be size <=2 , if not then it is a violation.

Following is code for reference.

/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 */
var characterReplacement = function (s, k) {
    let ans = 0;
    let maxOccurance = 0;
    const map = new Map();
    let left = 0;
    const n = s.length;
    for (let right = 0; right < n; right++) {
        const chr = s[right];
        map.set(chr, map.has(chr) ? map.get(chr) + 1 : 1);
        maxOccurance = Math.max(maxOccurance, map.get(chr));

        // Check for voilation
        while (right - left + 1 - maxOccurance > k) {
            const chr = s[left];
            map.set(chr, map.get(chr) - 1);
            left++;
        }
        ans = Math.max(ans, right - left + 1);
    }
    return ans;
};

76. Minimum Window Substring

https://leetcode.com/problems/minimum-window-substring/description/

Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "".

The testcases will be generated such that the answer is unique.

Example 1:

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"

Approach

Goal here is to make sure every chars of t is included in the substring of s .
It means, a window in s may have other chars as well that doesn’t exist in t .
Therefore to get the min window, it is ok to consider different char inside the window.
We can build a frequency map of chars based on t
We can track the unique chars count unique=map.size
Every time we process the char of s we reduce char if found in map .
If unique==0 then it means we have answer zone. We can keep track of minimum answer.
On finding unique==0 , we should shrink window until unique!==0 so that we can discover other possible ans.
Since we are not deleting any char from map therefore on shrinking we can add the char back to map if exist.
During shrink, if a char count was zero before then increment the unique

Following is code for reference.

/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
var minWindow = function (s, t) {
    const n = s.length;
    const map = new Map();
    for (const chr of t) {
        map.set(chr, map.has(chr) ? map.get(chr) + 1 : 1);
    }
    let unique = map.size;
    let left = 0;
    let ans = [-1, -1, n + 1];
    for (let right = 0; right < n; right++) {
        const chr = s[right];
        if (map.has(chr)) {
            map.set(chr, map.get(chr) - 1);
            // If frequency become zero then reduce unique
            if (map.get(chr) === 0) {
                unique--;
            }
        }
        // violation & ans
        while (unique === 0) {
            // update ans
            const size = right - left + 1;
            if (size < ans[2]) {
                ans = [left, right, size];
            }
            // Shrink window
            const chr = s[left];
            if (map.has(chr)) {
                if (map.get(chr) === 0) {
                    unique++;
                }
                map.set(chr, map.get(chr) + 1);
            }
            left++;
        }
    }
    if(ans[0] === -1) {
        return '';
    }
    return s.substring(ans[0], ans[1] + 1);
};

3. Longest Substring Without Repeating Characters

https://leetcode.com/problems/longest-substring-without-repeating-characters/description/

Given a string s, find the length of the longest substring without repeating characters.

Example 1:

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Approach

We can keep map to track the frequency of each chars.
We can also keep counter to track the total chars seen in the window.
If counter===map.size it means we found a window with unique chars therefore this is an ans zone.
If map.size !== counter then it means a violation therefore we need to shrink window until violation is resolved.

Following is the code for reference.

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function (s) {
    const n = s.length;
    const map = new Map();
    let left = 0;
    let counter = 0;
    let ans = 0;
    for (let right = 0; right < n; right++) {
        counter++;
        const chr = s[right];
        map.set(chr, map.has(chr) ? map.get(chr) + 1 : 1);
        // voilation
        while (map.size !== counter) {
            const chr = s[left];
            map.set(chr, map.get(chr) - 1);
            if (map.get(chr) === 0) {
                map.delete(chr);
            }
            // move left
            left++;
            counter--;
        }
        // Ans zone
        const local = right - left + 1;
        ans = Math.max(ans, local);
    }
    return ans;
};

992. Subarrays with K Different Integers

https://leetcode.com/problems/subarrays-with-k-different-integers/description/

Given an integer array nums and an integer k, return the number of good subarrays of nums.

A good array is an array where the number of different integers in that array is exactly k.

For example, [1,2,3,1,2] has 3 different integers: 1, 2, and 3.

A subarray is a contiguous part of an array.

Example 1:

Input: nums = [1,2,1,2,3], k = 2
Output: 7
Explanation: Subarrays formed with exactly 2 different integers: [1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2]

Approach

As we have seen with other problem, using sliding window we can find out sub array with at most k distinct chars.
To find out exact k, we can subtract it f(k) — f(k-1)

Following is code for reference.

const subarraysWithAmostKDistinct = (A, K) => {
    const n = A.length;
    const map = new Map(); 
    let startWindow = 0;
    let total = 0;
    for (let endWindow =0; endWindow < n; endWindow++) {
        const num = A[endWindow];
        if(!map.has(num)) {
            map.set(num, 0);
        }
        map.set(num, map.get(num) + 1);
        
        // if voilates
        while(startWindow < n && map.size > K) {
            const lastNum = A[startWindow];
            map.set(lastNum, map.get(lastNum) -1 );
            if(map.get(lastNum) === 0) {
                map.delete(lastNum);
            }
            startWindow++;
        }
        total += endWindow - startWindow + 1;        
    }
    return total;
}
/**
 * @param {number[]} A
 * @param {number} K
 * @return {number}
 */
var subarraysWithKDistinct = function(A, K) {
    return subarraysWithAmostKDistinct(A, K) - subarraysWithAmostKDistinct(A, K-1);
};

30. Substring with Concatenation of All Words

https://leetcode.com/problems/substring-with-concatenation-of-all-words/description/

You are given a string s and an array of strings words. All the strings of words are of the same length.

A concatenated string is a string that exactly contains all the strings of any permutation of words concatenated.

For example, if words = ["ab","cd","ef"], then "abcdef", "abefcd", "cdabef", "cdefab", "efabcd", and "efcdab" are all concatenated strings. "acdbef" is not a concatenated string because it is not the concatenation of any permutation of words.

Return an array of the starting indices of all the concatenated substrings in s. You can return the answer in any order.

Example 1:

Input: s = “barfoothefoobarman”, words = [“foo”,”bar”]

Output: [0,9]

Explanation:

The substring starting at 0 is "barfoo". It is the concatenation of ["bar","foo"] which is a permutation of words.
The substring starting at 9 is "foobar". It is the concatenation of ["foo","bar"] which is a permutation of words.

Approach

438. Find All Anagrams in a String

https://leetcode.com/problems/find-all-anagrams-in-a-string/description/

Given two strings s and p, return an array of all the start indices of p's anagrams in s. You may return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1:

Input: s = "cbaebabacd", p = "abc"
Output: [0,6]
Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".

Approach

We need to build frequency map of chars from p
map will be used to track the number of chars seen so far. Tracking will be based on reducing the value on match.
Since we do want to keep the map list of keys therefore we need a separate total= map.size and reduce it once a key become zero.
Once total==0 then this would be an ans zone.

Following is code for reference.

/**
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 */
var findAnagrams = function (s, p) {
    const n = s.length;
    const k = p.length;
    const map = new Map();
    for (const chr of p) {
        map.set(chr, map.has(chr) ? map.get(chr) + 1 : 1);
    }
    let total = map.size;
    const ans = [];
    let left = 0;
    for (let right = 0; right < n; right++) {
        const chr = s[right];
        if (map.has(chr)) {
            map.set(chr, map.get(chr) - 1);
            if (map.get(chr) === 0) {
                total--;
            }
        }
        // violation zone
        if (right - left >= k) {
            const chr = s[left];
            if (map.has(chr)) {
                if (map.get(chr) === 0) {
                    total++;
                }
                map.set(chr, map.get(chr) + 1);
            }
            left++;
        }
        // ans zone
        if (total === 0) {
            ans.push(left);
        }
    }
    return ans;
};

395. Longest Substring with At Least K Repeating Characters

https://leetcode.com/problems/longest-substring-with-at-least-k-repeating-characters/description/

Given a string s and an integer k, return the length of the longest substring of s such that the frequency of each character in this substring is greater than or equal to k.

if no such substring exists, return 0.

Example 1:

Input: s = "aaabb", k = 3
Output: 3
Explanation: The longest substring is "aaa", as 'a' is repeated 3 times.

Example 2:

Input: s = "ababbc", k = 2
Output: 5
Explanation: The longest substring is "ababb", as 'a' is repeated 2 times and 'b' is repeated 3 times.

Approach

A substring is valid if each character has at least k frequency.
The main idea is to find all the valid substrings with a different number of unique characters and track the maximum length.
Find the number of unique characters in the string s and store the count in variable maxUnique. For s = aabcbacad, the unique characters are a,b,c,d and maxUnique = 4.
Iterate over the string s with the value of currUnique ranging from 1 to maxUnique. In each iteration, currUnique is the maximum number of unique characters that must be present in the sliding window.
We can write separate sliding window function to return max substring size with given currUnique as the maximum number of unique characters.
Use countAtLeastK to track the presence of at least k frequent chars for O(1) check.

Following is the code for reference.

const runSlidingWindow = (s, unique, k) => {
    const n = s.length;
    let ans = 0;
    let left = 0;
    const map = new Map();
    let countAtLeastK = 0;
    for (let right = 0; right < n; right++) {
        const chr = s[right];
        map.set(chr, map.has(chr) ? map.get(chr) + 1 : 1);
        if (map.get(chr) === k) {
            countAtLeastK++;
        }
        // Handle violation
        while (map.size > unique) {
            const chr = s[left];
            if (map.get(chr) === k) {
                countAtLeastK--;
            }
            map.set(chr, map.get(chr) - 1);
            if (map.get(chr) === 0) {
                map.delete(chr);
            }
            left++;
        }
        // Ans zone
        if (map.size === unique && unique === countAtLeastK) {
            ans = Math.max(ans, right - left + 1);
        }
    }
    return ans;
}
/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 */
var longestSubstring = function (s, k) {
    // Get uniq char count
    const maxUnique = new Set(s.split('')).size;
    let ans = 0;

    // Run sliding window on all possible uniq char counts
    for (let unique = 1; unique <= maxUnique; unique++) {
        const local = runSlidingWindow(s, unique, k);
        ans = Math.max(ans, local);
    }
    return ans;

};

1180. Count Substrings with Only One Distinct Letter

https://leetcode.com/problems/count-substrings-with-only-one-distinct-letter/description/

Given a string s, return the number of substrings that have only one distinct letter.

Example 1:

Input: s = "aaaba"
Output: 8
Explanation: The substrings with one distinct letter are "aaa", "aa", "a", "b".
"aaa" occurs 1 time.
"aa" occurs 2 times.
"a" occurs 4 times.
"b" occurs 1 time.
So the answer is 1 + 2 + 4 + 1 = 8.

Approach

We can run sliding window and keep track of char frequency.


/**
 * @param {string} S
 * @return {number}
 */
var countLetters = function (S) {
    let ans = 0;
    const map = new Map();
    let left = 0;
    const n = S.length;
    for (let right = 0; right < n; right++) {
        const chr = S[right];
        map.set(chr, map.has(chr) ? map.get(chr) + 1 : 1);

        // handle violation
        while (map.size > 1) {
            const chr = S[left];
            map.set(chr, map.get(chr) - 1);
            if (map.get(chr) === 0) {
                map.delete(chr);
            }
            left++;
        }
        // update answer
        ans += map.get(chr);
    }
    return ans;
};

219. Contains Duplicate II

https://leetcode.com/problems/contains-duplicate-ii/description

Given an integer array nums and an integer k, return true if there are two distinct indices i and j in the array such that nums[i] == nums[j] and abs(i - j) <= k.

Example 1:

Input: nums = [1,2,3,1], k = 3
Output: true

Example 2:

Input: nums = [1,0,1,1], k = 1
Output: true

Approach 1: Try every pair of duplicate indices for the same number

We can use a HashMap to group each number and it’s list of indices.
Then iterate each <key, [indices]> in map.
Try all pairs of indices and see if it satisfies condition.

Following is code for reference.

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {boolean}
 */
var containsNearbyDuplicate = function (nums, k) {
    const map = new Map();
    for (let i = 0; i < nums.length; i++) {
        const num = nums[i];
        if (!map.has(num)) {
            map.set(num, []);
        }
        map.get(num).push(i);
    }
    for (const [num, indices] of map) {
        const n = indices.length;
        for (let i = 0; i < n; i++) {
            for (let j = i + 1; j < n; j++) {
                if (Math.abs(indices[i] - indices[j]) <= k) {
                    return true;
                }
            }
        }
    }
    return false;
};

Approach 2: Native linear search

Look for duplicate element in the previous k elements. Following is code for reference.

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {boolean}
 */
var containsNearbyDuplicate = function (nums, k) {
    const n = nums.length;
    for (let i = 0; i < n; i++) {
        for (let j = Math.max(0, i - k); j < i; j++) {
            if (nums[i] === nums[j] && i - j <= k) {
                return true;
            }
        }
    }
    return false;
};

Approach 3: Sliding window using Binary Search Tree

Keep a sliding window of k elements using self-balancing Binary Search Tree (BST).
The key to improve upon Approach #2 above is to reduce the search time of the previous k elements.
We can use auxilary data structure like aself-balancing BST. A BST supports search, delete and insert operations all in O(logk) time, where k is the number of elements in the BST.
Loop through the array, for each element
Search current element in the BST, return true if found
Put current element in the BST
If the size of the BST is larger than k, remove the oldest item.
Return false otherwise

Note: Most programming languages provide implementations of BST data structure in its standard library. In Java, you may use a TreeSet or a TreeMap. In C++ STL, you may use a std::set or a std::map. There is no such implementation in javascript so we will have to implement it.

Following is code for reference in java.

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Set<Integer> set = new TreeSet<>();
        int n = nums.length;
        int left = 0;
        for (int right=0; right < n; right++) {
            int num = nums[right];
            // Ans zone i.e. check before adding into BST
            if(set.contains(num)) {
                return true;
            }
            set.add(num);
            // Handle violation
            if(set.size() > k) {
                set.remove(nums[left]);
                left++;
            }
        }
        return false;
    }
}

Approach 4: Sliding window using hashmap

We can use HashMap for constant time search/delete operation. Following is code for reference.

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {boolean}
 */
var containsNearbyDuplicate = function (nums, k) {
    const n = nums.length;
    const set = new Set();
    let left = 0;
    for (let right = 0; right < n; right++) {
        const num = nums[right];
        if(set.has(num)) {
            return true;
        }
        set.add(num);
        // Handle violation
        if(set.size > k) {
            set.delete(nums[left]);
            left++;
        }
    }
    return false;
};

220. Contains Duplicate III

https://leetcode.com/problems/contains-duplicate-iii/description/

You are given an integer array nums and two integers indexDiff and valueDiff.

Find a pair of indices (i, j) such that:

i != j,
abs(i - j) <= indexDiff.
abs(nums[i] - nums[j]) <= valueDiff, and

Return true if such pair exists or false otherwise.

Example 1:

Input: nums = [1,2,3,1], indexDiff = 3, valueDiff = 0
Output: true
Explanation: We can choose (i, j) = (0, 3).
We satisfy the three conditions:
i != j --> 0 != 3
abs(i - j) <= indexDiff --> abs(0 - 3) <= 3
abs(nums[i] - nums[j]) <= valueDiff --> abs(1 - 1) <= 0

Approach# Linear search (TLE)

class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        for (int i = 0; i < nums.length; ++i) {
            for (int j = Math.max(i - k, 0); j < i; ++j) {
                if (Math.abs((long) nums[i] - nums[j]) <= t) return true;
            }
        }
        return false;
    }
}

Approach #2: Balance Binary search tree

To gain an actual speedup, we need a dynamic data structure that supports faster insert, search and delete. Self-balancing Binary Search Tree (BST) is the right data structure.

Initialize an empty BST set
Loop through the array, for each element x
Find the smallest element s in set that is greater than or equal to x, return true if s−x≤t
Find the greatest element g in set that is smaller than or equal to x, return true if x−g≤t
Put x in set
If the size of the set is larger than k, remove the oldest item.
Otherwise return false

Following is code for reference in java.

class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        TreeSet<Integer> set = new TreeSet<>();
        for (int i = 0; i < nums.length; ++i) {
            // Find the successor of current element
            Integer s = set.ceiling(nums[i]);
            if (s != null && (long) s <= nums[i] + t) return true;

            // Find the predecessor of current element
            Integer g = set.floor(nums[i]);
            if (g != null && nums[i] <= (long) g + t) return true;

            set.add(nums[i]);
            if (set.size() > k) {
                set.remove(nums[i - k]);
            }
        }
        return false;
    }
}

995. Minimum Number of K Consecutive Bit Flips

https://leetcode.com/problems/minimum-number-of-k-consecutive-bit-flips/description

You are given a binary array nums and an integer k.

A k-bit flip is choosing a subarray of length k from nums and simultaneously changing every 0 in the subarray to 1, and every 1 in the subarray to 0.

Return the minimum number of k-bit flips required so that there is no 0 in the array. If it is not possible, return -1.

A subarray is a contiguous part of an array.

Example 1:

Input: nums = [0,1,0], k = 1
Output: 2
Explanation: Flip nums[0], then flip nums[2].

Approach 1: BFS tree (TLE)

const getKey = nums => nums.join('#');
const getNeighbors = (nums, k) => {
    const n = nums.length;
    const ans = [];
    let left = 0;
    const copy = [...nums];
    for (let right = 0; right < n; right++) {
        copy[right] = copy[right] ^ 1;
        // in case of violation
        if (right - left >= k) {
            // shift to right
            copy[left] = nums[left];
            left++;
        }
        // Ans areas
        if (right - left === k - 1) {
            ans.push([...copy]);
        }
    }
    return ans;
}
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var minKBitFlips = function (nums, k) {
    const n = nums.length;
    const target = getKey(new Array(n).fill(1));
    const queue = [nums];
    const map = new Map();
    map.set(getKey(nums), 0);
    while (queue.length > 0) {
        const node = queue.shift();
        const u = getKey(node);
        if (u === target) {
            return map.get(target);
        }
        for (const neighbor of getNeighbors(node, k)) {
            const v = getKey(neighbor);
            if (!map.has(v)) {
                map.set(v, map.get(u) + 1);
                queue.push(neighbor);
            }
        }

    }
    return -1;
};

Approach 2: Sliding window

The order in which the flips are applied does not affect the final outcome.
This means that the solution can be approached by determining the correct indices to flip, regardless of the sequence.
The number of times an index is flipped determines its final value.
If an index is flipped an odd number of times, its value will be inverted; if flipped an even number of times, it will remain unchanged.
The problem boils down to finding the minimum flip sequence needed to convert all elements of nums to 1.

We can take following approach

Manage queue to track the window of flipped bits.
If after applying flips, nums[left] is still 0 then only do the flips.
If we don’t have enough remaining k elements then return -1

Following is code for reference.

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var minKBitFlips = function (nums, k) {
    const n = nums.length;
    let ans = 0;
    const queue = [];
    for (let left = 0; left < n; left++) {
        // All the flips tracked in the queue should be relavent to current sliding window
        while(queue.length > 0 && left > queue[0] + k - 1) {
            // remove these from queue
            queue.shift();
        }
        // Check the number of flips applied, if it is still 0 then only flips
        if ((nums[left] + queue.length) % 2 === 0) {
            // If we don't have enough elements remaining to perform k flips then return -1
            if (left + k > n) {
                return -1;
            }
            ans++; // flip happened so track it
            queue.push(left);
        }
    }
    return ans;
};

1156. Swap For Longest Repeated Character Substring

https://leetcode.com/problems/swap-for-longest-repeated-character-substring

You are given a string text. You can swap two of the characters in the text.

Return the length of the longest substring with repeated characters.

Example 1:

Input: text = "ababa"
Output: 3
Explanation: We can swap the first 'b' with the last 'a', or the last 'b' with the first 'a'. Then, the longest repeated character substring is "aaa" with length 3.

Approach# Use dynamic sliding window with custom implementation

Track the frequency of each character in the entire string.
Use a sliding window to find the longest substring where all characters are the same, except for at most one character that can be swapped.
Ensure that the character being swapped is available outside the current window.

Following is code for reference.

class Solution {
public:
    int maxRepOpt1(string s) {
        int n = s.length();
        // Frequency of each character in the entire string
        vector<int> freq(26, 0);
        for (char c : s) {
            freq[c - 'a']++;
        }

        int ans = 0;
        // Iterate through each character in the string
        int left = 0;
        while (left < n) {
            char chr = s[left];
            int right = left;

            // Find the length of the current segment of the same character
            while (right < n && s[right] == chr) {
                right++;
            }

            int segmentLen = right - left; // Length of the current segment

            // Check if we can extend the segment by swapping one character
            int k = right + 1;
            while (k < n && s[k] == chr) {
                k++;
            }

            int extendedLen = k - left; // Length after extending

            // The maximum possible length is the minimum of the extended length
            // and the total frequency of the character
            ans = max(ans, min(extendedLen, freq[chr - 'a']));

            left = right; // Move to the next segment
        }

        return ans;
    }
};

1687. Delivering Boxes from Storage to Ports

https://leetcode.com/problems/delivering-boxes-from-storage-to-ports

TBD

Enjoy coding :-)

Sliding window coding pattern

Coding pattern

Fixed length window size problems

346. Moving Average from Data Stream

643. Maximum Average Subarray I

1343. Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold

1176. Diet Plan Performance

1052. Grumpy Bookstore Owner

1456. Maximum Number of Vowels in a Substring of Given Length

1100. Find K-Length Substrings With No Repeated Characters

239. Sliding Window Maximum

1151. Minimum Swaps to Group All 1’s Together

1703. Minimum Adjacent Swaps for K Consecutive Ones

683. K Empty Slots

567. Permutation in String

1297. Maximum Number of Occurrences of a Substring

Dynamic sliding window size problems

209. Minimum Size Subarray Sum

485. Max Consecutive Ones

487. Max Consecutive Ones II

1004. Max Consecutive Ones III

Dynamic window size with auxiliary data structure

159. Longest Substring with At Most Two Distinct Characters

340. Longest Substring with At Most K Distinct Characters

1446. Consecutive Characters

424. Longest Repeating Character Replacement

76. Minimum Window Substring

3. Longest Substring Without Repeating Characters

992. Subarrays with K Different Integers

30. Substring with Concatenation of All Words

438. Find All Anagrams in a String

395. Longest Substring with At Least K Repeating Characters

1180. Count Substrings with Only One Distinct Letter

219. Contains Duplicate II

220. Contains Duplicate III

995. Minimum Number of K Consecutive Bit Flips

1156. Swap For Longest Repeated Character Substring

1687. Delivering Boxes from Storage to Ports

Written by Dilip Kumar

No responses yet