Skip to content

03. Sliding-Window

Theory

Description

The Sliding Window is a popular algorithmic technique used to efficiently solve problems involving sequences (arrays or lists) or strings. It is commonly applied in problems where a contiguous block of elements in an array or a string needs to be examined, especially when the window size is either fixed or dynamic.

1. Fixed Size Sliding Window

In a Fixed Size Sliding Window, the window size is predetermined and does not change during the traversal of the sequence. The window moves step-by-step across the sequence, adjusting its position by adding the next element into the window and removing the element that is no longer in the window's range.

Key Idea

  • The window size remains constant throughout the process.
  • The window moves from the beginning of the sequence to the end, sliding one element at a time.
  • At each step, the next element is added, and the element that is no longer within the window is removed.

Example

Maximum Sum Subarray of Size k
Given an array of integers and a number k, find the maximum sum of a subarray of size k.
Input

Array: [2, 1, 5, 1, 3, 2], k = 3
Process
1. Start with the first window of size k. The window is [2, 1, 5] with sum 8.
2. Slide the window one element to the right: remove 2, add 1. The window is now [1, 5, 1] with sum 7.
3. Slide the window one more time: remove 1, add 3. The window is now [5, 1, 3] with sum 9.
4. Slide the window again: remove 5, add 2. The window is now [1, 3, 2] with sum 6. 5. The maximum sum of any subarray of size 3 is 9.

Time Complexity
O(n), because you only need to traverse the array once and perform constant-time operations for each slide (removing one element and adding another).

2. Dynamic Size Sliding Window

In a Dynamic Size Sliding Window, the size of the window can change based on some condition. The window grows or shrinks dynamically as you traverse the sequence, making it ideal for problems where the window needs to adjust based on constraints or conditions.

Key Idea

  • The window expands or contracts depending on certain conditions.
  • The size of the window is not fixed and can change during traversal.
  • You may expand the window when you meet a certain condition or contract it when a constraint is violated.

Example

Longest Substring Without Repeating Characters
Given a string, find the length of the longest substring without repeating characters.
Input

String: "abcabcbb"
Process
1. Start with an empty set and begin with the first character 'a'. The window is now "a".
2. Move to the next character 'b'. The window is now "ab".
3. Move to the next character 'c'. The window is now "abc".
4. Move to the next character 'a'. Since 'a' is a duplicate, shrink the window from the left by removing 'a'. The window is now "bc".
5. Continue this process. The longest substring without repeating characters in this case is "abc", and its length is 3.

Time Complexity
O(n), because each character is added and removed from the window at most once.

Key Differences Between Fixed and Dynamic Sliding Windows

  1. Window Size:

    • Fixed Size: The window size is constant throughout the problem.
    • Dynamic Size: The window size can change dynamically as per the problem’s requirements.

  2. Problem Types:

    • Fixed Size: Problems often involve fixed-size subarrays or subsegments.
    • Dynamic Size: Problems often involve adjusting the window to satisfy certain constraints or conditions.

  3. Movement of Window:

    • Fixed Size: The window moves one step at a time, adding a new element and removing the old one.
    • Dynamic Size: The window can both grow and shrink, depending on whether the window satisfies certain conditions.

  4. Applications:

    • Fixed Size: Often used for problems involving sums, averages, or statistics on fixed-length subarrays.
    • Dynamic Size: Often used for problems involving string patterns, constraints like sum or distinct elements, or longest subsequences.

Summary

  • Fixed Size Sliding Window is used when you need to consider subarrays of a fixed size as you traverse the array or string.
  • Dynamic Size Sliding Window is used when the size of the window is flexible and changes depending on some condition, often involving optimization or constraint satisfaction.

Both techniques provide an efficient way to solve problems in linear time, as they avoid recomputing sums or other calculations from scratch every time the window moves. Instead, they update values incrementally as the window slides, making them highly effective for problems involving sequences.

Problems

1. Maximum Average Subarray I (Leetcode:643)

Problem Statement

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

Example 2:

Input: nums = [5], k = 1
Output: 5.00000

Constraints:

n == nums.length
1 <= k <= n <= 10^5
-10^4 <= nums[i] <= 10^4

Code and Explaination 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def findMaxAverage(self, nums: List[int], k: int) -> float:

        max_sum = curr_sum = sum(nums[:k])

        for i in range(k,len(nums)):

            curr_sum+= nums[i] - nums[i-k]
            max_sum = max(max_sum, curr_sum)

        return max_sum/k
Explaination:
This is first approach

1
Explaination:
This is second approach

2. Substrings of Size Three with Distinct Characters (Leetcode:1876)

Problem Statement

A string is good if there are no repeated characters.

Given a string s​​​​​, return the number of good substrings of length three in s​​​​​​.

Note that if there are multiple occurrences of the same substring, every occurrence should be counted.

A substring is a contiguous sequence of characters in a string.

Example 1:

Input: s = "xyzzaz"
Output: 1
Explanation: There are 4 substrings of size 3: "xyz", "yzz", "zza", and "zaz".
The only good substring of length 3 is "xyz".

Example 2:

Input: s = "aababcabc"
Output: 4
Explanation: There are 7 substrings of size 3: "aab", "aba", "bab", "abc", "bca", "cab", and "abc".
The good substrings are "abc", "bca", "cab", and "abc".

Constraints:

1 <= s.length <= 100
s​​​​​​ consists of lowercase English letters.

Code and Explaination 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def countGoodSubstrings(self, s: str) -> int:
        l = 0
        st = set()
        ans = 0
        for r in range(len(s)):
            st.add(s[r])
            while r-l+1 > 3:
                if s[l] != s[r] and s[l] != s[r-1] and s[l] != s[r-2]:
                    st.remove(s[l])
                l += 1
            if len(st) == 3: 
                ans += 1
        return ans
Explaination:
This is first approach

1
2
3
4
5
6
7
class Solution:
    def countGoodSubstrings(self, s: str) -> int:
        count = 0
        for i in range(len(s) - 2):
            if s[i] != s[i+1] and s[i] != s[i+2] and s[i+1] != s[i+2]:
                count += 1
        return count
Explaination:
This is second approach

1
2
3
4
5
6
7
8
class Solution:
    def countGoodSubstrings(self, s: str) -> int:
        count = 0

        for x, y, z in zip(s, s[1:], s[2:]):
            if x != y and y != z and x != z:
                count += 1
        return count
Explaination:
This is third approach

3. Maximum Number of Occurrences of a Substring (Leetcode:1297)

Problem Statement

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).

Example 2:

Input: s = "aaaa", maxLetters = 1, minSize = 3, maxSize = 3
Output: 2
Explanation: Substring "aaa" occur 2 times in the string. It can overlap.

Constraints:

1 <= s.length <= 105
1 <= maxLetters <= 26
1 <= minSize <= maxSize <= min(26, s.length)
s consists of only lowercase English letters.

Code and Explaination 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        map = {}
        for i in range(len(s)-minSize+1):
            substr = s[i:i+minSize]
            if len(set(substr))<=maxLetters:
                if substr in map: 
                    map[substr] +=1
                else: 
                    map[substr]=1

        return max(map.values(), default=0)
Explaination:
This is first approach

1
Explaination:
This is second approach

4. K Radius Subarray Averages (Leetcode:2090)

Problem Statement

You are given a 0-indexed array nums of n integers, and an integer k.

The k-radius average for a subarray of nums centered at some index i with the radius k is the average of all elements in nums between the indices i - k and i + k (inclusive). If there are less than k elements before or after the index i, then the k-radius average is -1.

Build and return an array avgs of length n where avgs[i] is the k-radius average for the subarray centered at index i.

The average of x elements is the sum of the x elements divided by x, using integer division. The integer division truncates toward zero, which means losing its fractional part.

For example, the average of four elements 2, 3, 1, and 5 is (2 + 3 + 1 + 5) / 4 = 11 / 4 = 2.75, which truncates to 2.

Example 1:

Input: nums = [7,4,3,9,1,8,5,2,6], k = 3
Output: [-1,-1,-1,5,4,4,-1,-1,-1]
Explanation:
- avg[0], avg[1], and avg[2] are -1 because there are less than k elements before each index.
- The sum of the subarray centered at index 3 with radius 3 is: 7 + 4 + 3 + 9 + 1 + 8 + 5 = 37.
Using integer division, avg[3] = 37 / 7 = 5.
- For the subarray centered at index 4, avg[4] = (4 + 3 + 9 + 1 + 8 + 5 + 2) / 7 = 4.
- For the subarray centered at index 5, avg[5] = (3 + 9 + 1 + 8 + 5 + 2 + 6) / 7 = 4.
- avg[6], avg[7], and avg[8] are -1 because there are less than k elements after each index.

Example 2:

Input: nums = [100000], k = 0
Output: [100000]
Explanation:
- The sum of the subarray centered at index 0 with radius 0 is: 100000.
avg[0] = 100000 / 1 = 100000.

Example 3:

Input: nums = [8], k = 100000
Output: [-1]
Explanation:
- avg[0] is -1 because there are less than k elements before and after index 0.

Constraints:

n == nums.length 1 <= n <= 10^5 0 <= nums[i], k <= 10^5

Code and Explaination 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def getAverages(self, nums: List[int], k: int) -> List[int]:

        window_size = 2 * k + 1
        n = len(nums)

        if n < window_size: return [-1]* n

        curr_sum = sum(nums[:window_size])
        avgs= [-1]*k
        avgs.append(curr_sum//window_size)

        for i in range(k+1, n-k):
            curr_sum += nums[i+k] - nums[i-k-1]
            avgs.append(curr_sum//window_size)

        for i in range(k): avgs.append(-1)

        return avgs
Explaination:
This is first approach

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def getAverages(self, nums: List[int], k: int) -> List[int]:

        if k == 0: return nums

        window_size = 2 * k + 1
        n = len(nums)
        avgs = [-1] * n

        if n < window_size: return avgs

        window_sum = sum(nums[:window_size])
        avgs[k] = window_sum // window_size

        for i in range(window_size, n):
            window_sum+= nums[i] - nums[i - window_size]
            avgs[i - k] = window_sum // window_size

        return avgs
Explaination:
This is second approach

5. Maximum Erasure Value (Leetcode:1695)

Problem Statement

You are given an array of positive integers nums and want to erase a subarray containing unique elements. The score you get by erasing the subarray is equal to the sum of its elements.

Return the maximum score you can get by erasing exactly one subarray.

An array b is called to be a subarray of a if it forms a contiguous subsequence of a, that is, if it is equal to a[l],a[l+1],...,a[r] for some (l,r).

Example 1:

Input: nums = [4,2,4,5,6]
Output: 17
Explanation: The optimal subarray here is [2,4,5,6].

Example 2:

Input: nums = [5,2,1,2,5,2,1,2,5]
Output: 8
Explanation: The optimal subarray here is [5,2,1] or [1,2,5].

Constraints:

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^4

Code and Explaination 

1
Explaination:
This is first approach

1
Explaination:
This is second approach

6. Arithmetic Slices (Leetcode:413)

Problem Statement

An integer array is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same.

For example, [1,3,5,7,9], [7,7,7,7], and [3,-1,-5,-9] are arithmetic sequences. Given an integer array nums, return the number of arithmetic subarrays of nums.

A subarray is a contiguous subsequence of the array.

Example 1:

Input: nums = [1,2,3,4]
Output: 3
Explanation: We have 3 arithmetic slices in nums: [1, 2, 3], [2, 3, 4] and [1,2,3,4] itself.

Example 2:

Input: nums = [1]
Output: 0

Constraints:

1 <= nums.length <= 5000
-1000 <= nums[i] <= 1000

Code and Explaination 

1
Explaination:
This is first approach

1
Explaination:
This is second approach

7. Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold (Leetcode:1343)

Problem Statement

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).

Example 2:

Input: arr = [11,13,17,23,29,31,7,5,2,3], k = 3, threshold = 5
Output: 6
Explanation: The first 6 sub-arrays of size 3 have averages greater than 5. Note that averages are not integers

Constraints:

1 <= arr.length <= 10^5
1 <= arr[i] <= 10^4
1 <= k <= arr.length
0 <= threshold <= 10^4

Code and Explaination 

1
Explaination:
This is first approach

1
Explaination:
This is second approach

8. Permutation in String (Leetcode:567)

Problem Statement

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").

Example 2:

Input: s1 = "ab", s2 = "eidboaoo"
Output: false

Constraints:

1 <= s1.length, s2.length <= 10^4
s1 and s2 consist of lowercase English letters.

Code and Explaination 

1
Explaination:
This is first approach

1
Explaination:
This is second approach

9. Maximum Points You Can Obtain from Cards (Leetcode:1423)

Problem Statement

There are several cards arranged in a row, and each card has an associated number of points. The points are given in the integer array cardPoints.

In one step, you can take one card from the beginning or from the end of the row. You have to take exactly k cards.

Your score is the sum of the points of the cards you have taken.

Given the integer array cardPoints and the integer k, return the maximum score you can obtain.

Example 1:

Input: cardPoints = [1,2,3,4,5,6,1], k = 3
Output: 12
Explanation: After the first step, your score will always be 1. However, choosing the rightmost card first will maximize your total score. The optimal strategy is to take the three cards on the right, giving a final score of 1 + 6 + 5 = 12.

Example 2:

Input: cardPoints = [2,2,2], k = 2
Output: 4
Explanation: Regardless of which two cards you take, your score will always be 4.

Example 3:

Input: cardPoints = [9,7,7,9,7,7,9], k = 7
Output: 55
Explanation: You have to take all the cards. Your score is the sum of points of all cards.

Constraints:

1 <= cardPoints.length <= 10^5
1 <= cardPoints[i] <= 10^4
1 <= k <= cardPoints.length

Code and Explaination 

1
Explaination:
This is first approach

1
Explaination:
This is second approach

10. Sliding Window Maximum (Leetcode:239)

Problem Statement

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

Example 2:
Input: nums = [1], k = 1
Output: [1]

Constraints:

1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
1 <= k <= nums.length

Code and Explaination 

1
Explaination:
This is first approach

1
Explaination:
This is second approach

11. Sliding Window Median (Leetcode:480)

Problem Statement

The median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle values.

For examples, if arr = [2,3,4], the median is 3.
For examples, if arr = [1,2,3,4], the median is (2 + 3) / 2 = 2.5.

You are given an integer array nums and an integer k. 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 median array for each window in the original array. Answers within 10-5 of the actual value will be accepted.

Example 1:

Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [1.00000,-1.00000,-1.00000,3.00000,5.00000,6.00000]
Explanation:

Window position Median
[1 3 -1] -3 5 3 6 7 1
1 [3 -1 -3] 5 3 6 7 -1
1 3 [-1 -3 5] 3 6 7 -1
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] 6

Example 2:

Input: nums = [1,2,3,4,2,3,1,4,2], k = 3
Output: [2.00000,3.00000,3.00000,3.00000,2.00000,3.00000,2.00000]

Constraints:

1 <= k <= nums.length <= 10^5 -2^31 <= nums[i] <= 2^31 - 1

Code and Explaination 

1
Explaination:
This is first approach

1
Explaination:
This is second approach

12. Subarrays with K Different Integers (Leetcode:992)

Problem Statement

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]

Example 2:

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

Constraints:

1 <= nums.length <= 2 * 10^4
1 <= nums[i], k <= nums.length

Code and Explaination 

1
Explaination:
This is first approach

1
Explaination:
This is second approach

13. Minimum Window Substring (Leetcode:76)

Problem Statement

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"
Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.

Example 2:

Input: s = "a", t = "a"
Output: "a"
Explanation: The entire string s is the minimum window.

Example 3:

nput: s = "a", t = "aa"
Output: ""
Explanation: Both 'a's from t must be included in the window.
Since the largest window of s only has one 'a', return empty string.

Constraints:

m == s.length
n == t.length
1 <= m, n <= 105
s and t consist of uppercase and lowercase English letters.

Follow up:

Could you find an algorithm that runs in O(m + n) time?

Code and Explaination 

1
Explaination:
This is first approach

1
Explaination:
This is second approach

Problem 14: Find All Anagrams in a String (Leetcode:438)

Problem Statement

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.

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".
Example 2: Input: s = "abab", p = "ab"
Output: [0,1,2]
Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".

Constraints:

  • 1 <= s.length, p.length <= 3 * 104
  • s and p consist of lowercase English letters.
Code and Explaination 

1
Explaination:
This is first approach

1
Explaination:
This is second approach

Problem 15: Maximum Sum of Distinct Subarrays With Length K (Leetcode:2461)

Problem Statement

You are given an integer array nums and an integer k. Find the maximum subarray sum of all the subarrays of nums that meet the following conditions:

  • The length of the subarray is k, and
  • All the elements of the subarray are distinct.

Return the maximum subarray sum of all the subarrays that meet the conditions. If no subarray meets the conditions, return 0.

A subarray is a contiguous non-empty sequence of elements within an array.

Example 1:

Input: nums = [1,5,4,2,9,9,9], k = 3
Output: 15
Explanation: The subarrays of nums with length 3 are:
- [1,5,4] which meets the requirements and has a sum of 10.
- [5,4,2] which meets the requirements and has a sum of 11.
- [4,2,9] which meets the requirements and has a sum of 15.
- [2,9,9] which does not meet the requirements because the element 9 is repeated.
- [9,9,9] which does not meet the requirements because the element 9 is repeated.
We return 15 because it is the maximum subarray sum of all the subarrays that meet the conditions

Example 2:

Input: nums = [4,4,4], k = 3
Output: 0
Explanation: The subarrays of nums with length 3 are:
- [4,4,4] which does not meet the requirements because the element 4 is repeated.
We return 0 because no subarrays meet the conditions.

Constraints:

  • 1 <= k <= nums.length <= 105
  • 1 <= nums[i] <= 105
Code and Explaination 

1
Explaination:
This is first approach

1
Explaination:
This is second approach

Problem 16: Substring with Concatenation of All Words (Leetcode:30)

Problem Statement

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.

Example 2:

Input: s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
Output: []
Explanation:
There is no concatenated substring.

Example 3:

Input: s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
Output: [6,9,12]
Explanation:
The substring starting at 6 is "foobarthe". It is the concatenation of ["foo","bar","the"].
The substring starting at 9 is "barthefoo". It is the concatenation of ["bar","the","foo"].
The substring starting at 12 is "thefoobar". It is the concatenation of ["the","foo","bar"].

Constraints:

  • 1 <= s.length <= 104
  • 1 <= words.length <= 5000
  • 1 <= words[i].length <= 30
  • s and words[i] consist of lowercase English letters.
Code and Explaination 

1
Explaination:
This is first approach

1
Explaination:
This is second approach