Explaining Sliding Window Technique

Have you ever encountered a question, maybe on leetcode, or some other source, that required you to either get the minimum or maximum subarray size whose sum is equivalent to a target? If so, you might find this article useful.

In this piece, I’ll explain the sliding window technique and give an example of it implementation in a coding interview question from leetcode. In addition, I’ll explain it’s time complexity.

What is the sliding window technique?

This technique is an algorithm used to find the smallest or the largest subarray with a given property. It has a time complexity of O(n), to be specific, O(2n).

How does it really work?

It involves using a window to look at a bunch of elements in an array and performing various computations on each element in that window.

Two pointers are used, one points to the first element, and the other to the last element in the subarray. Changing the position of these pointers is equivalent to moving the window.

The algorithm behind

Let us assume you’ve been tasked to find the smallest subarray whose elements sum up to a given value, we call it target. To solve this using the sliding window technique, you have two options; using a fixed-size window or a dynamically sized window. I’ll explain each method below:

1. Using a fixed-size window

If the size of the window is stated, for example as size, follow the following steps:

  1. Set the initial subarray’s size (subArraySize) to 0.
  2. Initialize a variable minSize.
  3. Calculate the summation of all elements in the subarray and set minsize to equal the subarray size.
  4. Loop the array from the second element (index == 1) until the point where size plus the increment variable is less than the length of the array. Use an increment variable i.
  5. Decrement subArraySize by the element before it (index == i – 1) and increment it by the element immediately after (index == size + i – 1)
  6. Take minSize to be the greatest value between minSize and subArraysize.
  7. Return minSize.

Example Code in Java:

public int minSubArray(int[] array, int size){         int minSize;         int subArrSize = 0;         for (int i = 0; i < size; i++) {             subArrSize += array[i];         }         minSize = subArrSize;         for (int i = 1; (size + i) < array.length; i++) {             subArrSize = subArrSize - array[i - 1];             subArrSize = subArrSize + array[size + i - 1];             minSize = Math.min(minSize, subArrSize);         }         return minSize;     }
Code language: PHP (php)

2. Using a dynamically sized window

If the size of the window to be used is not specified, following the steps will do:

  1. Initialize two variables, first ‘minCount’ to be the maximum possible integer value (infinity) and ‘len’ to be the length of the input array
  2. Loop from the first element in the array to the last element of the array using an increment variable i.
  3. Set the sum as well as the count of elements in the subarray as zero (0).
  4. Loop from the element in the increment index to the last element.
  5. Increment sum and count as you loop through.
  6. If the sum is greater than or equal to target, Compute the smallest between minCount and count and set it as minCount and break from the inner loop.
  7. Return the minCount value.

Example code in Java:

public int smallestSubArrayCount(int [] arr, int target){         int minCount = Integer.MAX_VALUE;         int len = arr.length;         for (int i = 0; i < len; i++) {             int sum = 0;             int count = 0;             for (int j = i; j < len; j++) {                 sum += arr[j];                 count += 1;                 if (sum >= target)                 {                     minCount = Math.min(minCount, count);                     break;                 }             }         }         return minCount;     }
Code language: JavaScript (javascript)

Why O(n) and not O(n²)

This is because each pointer for the window is moved a maximum of n times, n being the size of the input array.

Despite the nested loops in the second procedure, the inner loop does not restart from the beginning for each value of the outer loop. Instead, the inner loop starts where the outer loop left off, effectively ensuring that each array element is only processed once.

Conclusion

In this article, we learned one of the most useful technique used in solving DSA problems “Sliding Window”. We explored how we can use this technique to optimize the time complexity of a solution where the Sliding Window technique can be used and how it brings down the time complexity of the solution from polynomial to linear. This technique is very much asked in the technical interviews. So, It’s worth your time preparing this algorithm. Thank You.


Posted

in

by

Recent Post

  • Mastering Software Testing Strategies: Your Guide

    Implementing best software testing strategies is a crucial part of software development, ensuring that digital products meet industry standards. Defined by the International Software Testing Qualification Board, it encompasses a range of activities, both static and dynamic, throughout the software’s lifecycle. As an essential component of the Software Development Life Cycle (SDLC), the Software Testing […]

  • Your Complete Guide to Securing Your Kubernetes Cluster: Essential Tips for Beginners

    In today’s digital landscape, Kubernetes has emerged as the go-to solution for managing applications at scale. However, amidst its power lies a crucial concern: security. Ensuring the safety of your Kubernetes cluster is paramount to protecting your applications, data, and infrastructure. This comprehensive guide will walk you through essential practices and tips to help you […]

  • How to use Cloudinary in Node.js to upload images?

    It’s simple to use Cloudinary to upload images in a Nodе.js application, which can improve your app’s imagе management capabilities. Wе’ll go over how to sеt up and incorporate Cloudinary in your Nodе.js application for imagе uploads and how to use Cloudinary nodejs in this blog article. What is Cloudinary? Cloudinary is a cloud-based media […]

  • Mobile App User Experience- 10 Biggest Mistakes First-Time Founders Make 

    With the mobile app industry hitting a whopping 206 Billion in value (as per Grand View Research), it is no wonder more entrepreneurs are jumping into the mobile app market with their innovative ideas and life-changing solutions. But for those taking their first plunge, it is crucial to understand that creating an app isn’t just […]

  • Building Draggable Components in React

    As user interaction becomes more prevalent in today’s applications, sometimes it’s nice to use draggable elements in your apps. Consider website builders like Trello or Wix. They have drag-and-drop features that make it easy and convenient for users. Hello everyone! In this article, I will show some simple ways to create draggable components in React […]

  • How to Fetch Data from an API with JavaScript?

    In web development, integrating data from external sources is a common task. Application Programming Interfaces (APIs) play an important function in changing data amongst systems. In this blog, we’ll explore the way to Get information from an API with the use of JavaScript, supplying step-by-step the resource of-step commands with complete code examples of how […]