SLIDING WINDOW

1. FIXED WINDOW

f(arr, k)
{
    n, res, curr = 0;
    // step 1: first window
    for (int i = 0; i <= k - 1; i++)
    {
        // add arr[i] into window
    }
    res = curr;
    int firstInd = 0;
    // step 2: slide the window
    for (int i = k; i <= n - 1; i++)
    {
        // add arr[i] into window
        // remove arr[firstInd] from window
        // firstInd++

        // compare with curr and update res
    }
    return res;
}

https://www.geeksforgeeks.org/problems/max-sum-subarray-of-size-k5313/1
643. https://leetcode.com/problems/maximum-average-subarray-i/description/
567. https://leetcode.com/problems/permutation-in-string/description/
438. https://leetcode.com/problems/find-all-anagrams-in-a-string/description/
1423. https://leetcode.com/problems/maximum-points-you-can-obtain-from-cards/description/
1456. https://leetcode.com/problems/maximum-number-of-vowels-in-a-substring-of-given-length/description/
239. https://leetcode.com/problems/sliding-window-maximum/description/

2. VARIABLE SIZE WINDOW — LONGEST

f(arr)
{
    n, i = 0, j = 0, maxLen = 0;
    while (j <= n - 1)
    {
        // 1. Expand: include arr[j]
        add(arr[j]);

        // 2. Shrink until window is valid
        while (/* invalid condition */)
        {
            remove(arr[i]);
            i++;
        }

        // 3. Update result
        maxLen = max(maxLen, j - i + 1);

        j++;
    }
}

3. https://leetcode.com/problems/longest-substring-without-repeating-characters/description/
https://www.naukri.com/code360/problems/distinct-characters_2221410
904. https://leetcode.com/problems/fruit-into-baskets/description/
1493. https://leetcode.com/problems/longest-subarray-of-1s-after-deleting-one-element/description/
1004. https://leetcode.com/problems/max-consecutive-ones-iii/description/
424. https://leetcode.com/problems/longest-repeating-character-replacement/description/

3. COUNT NUMBER OF SUBARRAYS

f(arr)
{
    n, i = 0, j = 0, cnt = 0;
    while (j <= n - 1)
    {
        // 1. Expand: include arr[j]
        add(arr[j]);

        // 2. Shrink until window is valid
        while (/* invalid condition */)
        {
            remove(arr[i]);
            i++;
        }

        // 3. Count all subarrays ending at j
        // all subarrays starting from i..j are valid
        cnt += j - i + 1;

        j++;
    }
}

713. https://leetcode.com/problems/subarray-product-less-than-k/description/

Get Girish’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

4. COUNT NUMBER OF SUBARRAYS WITH ATMOST K DISTINCT

countAtMostK(arr, k)
{
    n, i = 0, j = 0, cnt = 0;
    unordered_map<char, int> mp; // ele, freq
    while (j <= n - 1)
    {
        // 1. Expand: include arr[j]
        add(arr[j]); // mp[arr[j]]++;

        // 2. Shrink until window is valid
        while (/* invalid condition */) // mp.size() > k
        {
            remove(arr[i]);
            // mp[arr[i]]--;
            // if (mp[arr[i]] == 0)
            // {
            //     mp.erase(arr[i]);
            // }
            i++;
        }

        // 3. Count all subarrays ending at j
        // all subarrays starting from i..j are valid
        cnt += j - i + 1;

        j++;
    }
}

5. COUNT NUMBER OF SUBARRAYS WITH EXACT K DISTINCT

f(arr, k)
{
    // AtMostK(k)     : {1 - distinct} + {2 - distinct} + ... + {k - 1 - distinct} + {k - distinct}
    // AtMostK(k - 1) : {1 - distinct} + {2 - distinct} + ... + {k - 1 - distinct}
    // -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --
    // ExactlyK(k)    : { k - distinct only }

    return countAtMostK(arr, k) - countAtMostK(arr, k - 1);
}

992. https://leetcode.com/problems/subarrays-with-k-different-integers/description/
930. https://leetcode.com/problems/binary-subarrays-with-sum/description/
1248. https://leetcode.com/problems/count-number-of-nice-subarrays/description/

6. COUNT NUMBER OF SUBARRAYS WITH AT LEAST K DISTINCT

f(arr, k)
{
    // Total substrings : {1 - distinct} + {2 - distinct} + ... + {k - 1 distinct} + {k distinct} + { > k distinct}
    // AtMostK(k - 1)   : {1 - distinct} + {2 - distinct} + ... + {k - 1 distinct}
    // -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --
    // AtLeastK(k)      : {k distinct} + { > k distinct}

    return totalSubStrings - countAtMostK(arr, k - 1);
}

1358. https://leetcode.com/problems/number-of-substrings-containing-all-three-characters/description/

7. VARIABLE SIZE WINDOW — SMALLEST

f(arr)
{
    n, i = 0, j = 0, minLen = n + 1;
    while (j <= n - 1)
    {
        // 1. Expand: include arr[j]
        add(arr[j]);

        // 2. Shrink while valid, till it becomes invalid
        while (/* valid condition */)
        {
            // 3. Update result
            minLen = min(minLen, j - i + 1);

            remove(arr[i]);
            i++;
        }

        j++;
    }

    return minLen == n + 1 ? 0 : minLen;
}

209. https://leetcode.com/problems/minimum-size-subarray-sum/description/
76. https://leetcode.com/problems/minimum-window-substring/description/