Skip to content

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

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

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

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

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

Code and Explaination 

1
Explaination:
This is first approach

1
Explaination:
This is second approach

6. Arithmetic Slices (Leetcode:413)

Problem Statement

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

Code and Explaination 

1
Explaination:
This is first approach

1
Explaination:
This is second approach

8. Permutation in String (Leetcode:567)

Problem Statement

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

Code and Explaination 

1
Explaination:
This is first approach

1
Explaination:
This is second approach

10. Sliding Window Maximum (Leetcode:239)

Problem Statement

Code and Explaination 

1
Explaination:
This is first approach

1
Explaination:
This is second approach

11. Sliding Window Median (Leetcode:480)

Problem Statement

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

Code and Explaination 

1
Explaination:
This is first approach

1
Explaination:
This is second approach

13. Minimum Window Substring (Leetcode:76)

Problem Statement

Code and Explaination 

1
Explaination:
This is first approach

1
Explaination:
This is second approach