Explaining Sliding Window Technique

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

  • 12 Essential SaaS Metrics to Track Business Growth

    In the dynamic landscape of Software as a Service (SaaS), the ability to leverage data effectively is paramount for long-term success. As SaaS businesses grow, tracking the right SaaS metrics becomes essential for understanding performance, optimizing strategies, and fostering sustainable growth. This comprehensive guide explores 12 essential SaaS metrics that every SaaS business should track […]

  • Bagging vs Boosting: Understanding the Key Differences in Ensemble Learning

    In modern machine learning, achieving accurate predictions is critical for various applications. Two powerful ensemble learning techniques that help enhance model performance are Bagging and Boosting. These methods aim to combine multiple weak learners to build a stronger, more accurate model. However, they differ significantly in their approaches. In this comprehensive guide, we will dive […]

  • What Is Synthetic Data? Benefits, Techniques & Applications in AI & ML

    In today’s data-driven era, information is the cornerstone of technological advancement and business innovation. However, real-world data often presents challenges—such as scarcity, sensitivity, and high costs—especially when it comes to specific or restricted datasets. Synthetic data offers a transformative solution, providing businesses and researchers with a way to generate realistic and usable data without the […]

  • Federated vs Centralized Learning: The Battle for Privacy, Efficiency, and Scalability in AI

    The ever-expanding field of Artificial Intelligence (AI) and Machine Learning (ML) relies heavily on data to train models. Traditionally, this data is centralized, aggregated, and processed in one location. However, with the emergence of privacy concerns, the need for decentralized systems has grown significantly. This is where Federated Learning (FL) steps in as a compelling […]

  • Federated Learning’s Growing Role in Natural Language Processing (NLP)

    Federated learning is gaining traction in one of the most exciting areas: Natural Language Processing (NLP). Predictive text models on your phone and virtual assistants like Google Assistant and Siri constantly learn from how you interact with them. Traditionally, your interactions (i.e., your text messages or voice commands) would need to be sent back to […]

  • What is Knowledge Distillation? Simplifying Complex Models for Faster Inference

    As AI models grow increasingly complex, deploying them in real-time applications becomes challenging due to their computational demands. Knowledge Distillation (KD) offers a solution by transferring knowledge from a large, complex model (the “teacher”) to a smaller, more efficient model (the “student”). This technique allows for significant reductions in model size and computational load without […]

Click to Copy