Sliding Window || Python || Data Structures and Algorithms

#webdev #programming #python #career

What is Sliding Window Technique ?

Sliding Window Technique is a method where we define a window or range in the input data (arrays or strings) and then move that window across the data to perform some operation within the window.

This technique is commonly used in algorithms like finding subarrays with a specific sum, finding the longest substring with unique characters, or solving problems that require a fixed-size window to process elements efficiently.

Two Types of Sliding Window-

1. Fixed Size Sliding Window - In this, the size of the window is fixed, and we move the window across the array.

2. Variable Size Sliding Window - In this, we increment the right pointer by one in each iteration, and we move the left pointer only when the condition is not met. We continue moving the left pointer until the condition is met again or it reaches the right pointer.

When should we use sliding window?

Whenever we see a problem where we need to calculate maximum or minimum of a subarray or any operation related to subarray then There is a high chance a sliding window can be used in it.

General template for Sliding Window -

function fn(arr):
    left = 0
    for (int right = 0; right < arr.length; right++):
        Do some logic to "add" element at arr[right] to window

        while WINDOW_IS_INVALID:
            Do some logic to "remove" element at arr[left] from window
            left++

        Do some logic to update the answer

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

Test Case 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.

Test Case 2:

Input: target = 4, nums = [1,4,4]

Output: 1

Test Case 3:

Input: target = 11, nums = [1,1,1,1,1,1,1,1]

Output: 0

Brute Force - The Brute Force Approach to solve this problem is to iterate from left to right for each element. Then calculate the subarray sum for all the elements between our left and right pointer.

So the time complexity will be O(n) * O(n(n+1) /2 ) = O(n3)

Sliding Window Approach -

Code -

Algorithm -

Initialize 2 pointers left and right and Two more variables one for calculating current sum and and one for size of minimum window.
Our window size will always be (right - left + 1) , as arrays starting index starts from 0.
Now increment the right pointer in each iteration.
In each iteration check if the current sum of the window exceeds the target then we have to decrease the size of our window.
Increment the left pointer until the size of the window is correct as per the condition.
During this calculate the size of the minimum window as we want to calculate the minimum size window.
At Last if the min Window variable has changed the return the original value otherwise return 0.

Time Complexity - O(n) as for the worst case we are iterating through the array elements at most twice.

Simplifying O(2n) to O(n)

Space Complexity - O(1)

By using sliding window algorithm we reduced the time complexity from O(n3) to O(n).