Data Structures and Algorithms — Sliding Window Technique

The Sliding Window is another technique to solve array and string algorithm questions. Actually, we use the two-pointers technique to implement the sliding window.

If you are not familiar with Two-Pointers Technique, please check it first before moving forward

Two Pointers Technique

Once you see shorter lengths, the larger length with constraints, you should understand you can solve the question more efficiently using the sliding window technique.

You can solve those kinds of questions using nested for loops but there will be at least a time complexity of O(n ²)

It is so easy to implement a sliding window

1. Define two pointers which are left and right
2. Iterate the right pointer over the input of the array
3. Whenever constraints are broken, remove elements from the window by iterating the left pointer.

int left=0;
int right=0;

while(right < input of array.Length)
{
  // do some logic here
  //whenever constranints are broken
  while(condition)
  {
      // do logic here
      left++;
  }
  right++;
  
  // do some logic here to show the result
}

If you want to find a subarray of an array

There are n subarrays of length one, there are n-1 subarrays of length two

when we check the above approach, we will find the formula below

n(n+1)/2 where n is the length of the array.

Let’s say we have an array of length two [0,1]

There are 3 subarrays which are [0] — [1] — [0,1]

When we use the formula instead of checking each one we will have the same result.

2 ( 2 + 1 ) / 2 = 3

When we use the formula and check the subarrays, it will have a time complexity of at least O(n ²) but the sliding window guarantees that your time complexity will be a maximum of O(2n) which means O(n).

Because the right pointer will be iterated n times and the left pointer will be iterated n times(when the constraint is broken).

Let’s check some examples

Max Consecutive Ones II (Medium Level)

Max Consecutive Ones II - LeetCode

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

We will use the sliding window technique and the question says we can only have one zero in our window.

First, we need to create variables that will be stored our values.

int left=0; // we will use it once the constraint is broken and get rid of more zeros
//int right=0; if you want to use while loop, you have to create another variable to keep your index
int ans=0; // result value
int zeros=0; // zeros variable will keep amount of zero in our window

We need to create a loop to iterate over the array and create our window. I prefer to use the for loop to iterate over the array and create a window.

for(int right=0;right<nums.Length;right++)
//while(right<nums.Length)

Then, time to implement our logic

for(int right=0;right<nums.Length;right++)
//while(right<nums.Length)
{
    if(nums[right]==0) zeros++;// if we run into zero, we increase the zeros by 1
    
    while(left < right && zeros > 1)// if the constraint is broken, we need to get rid of zero that we do not need
    {
        if(nums[left] == 0) zeros--;// if the left pointer represents zero, we remove it and decrease the zeros variable by 1
        left++;//increase left variable by 1
    }

    ans=Math.Max(ans,(right-left+1));// check to see if result is bigger or not

    //right++; if you use while, you have to increase the right variable by 1 for each iteration
}

Lastly, we need to return the result.

return ans;

All code should be like the one below

if(nums.Length==0) return 0;

int left=0;
//int right=0;
int ans=0;
int zeros=0;

for(int right=0;right<nums.Length;right++)
//while(right<nums.Length)
{
    if(nums[right]==0) zeros++;
    
    while(left < right && zeros > 1)
    {
        if(nums[left] == 0) zeros--;
        left++;
    }

    ans=Math.Max(ans,(right-left+1));

    //right++;
}

return ans;

Time complexity is O(n) — Space complexity is O(n).

Let’s check the other question and you will see the below question is almost the same as the previous one. The only difference is that the previous one allowed us to have at most one zero, the below question will only allow us to have at most k zeros.

Max Consecutive Ones III (Medium Level)

Max Consecutive Ones III - LeetCode

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.

  if(nums.Length==0) return 0;

  int left=0;
  int ans=0;
  int zeros=0;

  for(int right=0;right<nums.Length;right++)
  {
      if(nums[right] == 0) zeros++;

      //only difference here, we check the amount of zero and it has to be less and equal to k, not greater
      while(zeros > k && left <= right) 
      {
          if(nums[left] == 0) zeros--;
          left++;
      } 

      ans = Math.Max(ans, (right - left + 1));
  }

  return ans;

Time complexity is O(n) — Space complexity is O(n).

As you can see, if you are familiar with the sliding window technique, you can solve the related algorithm questions easily no matter what level they are. The point is that you should understand how to use and implement the sliding window instead of memorizing it.