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

  • Mastering Merge Sort: A Comprehensive Guide to Efficient Sorting

    Are you eager to enhance your coding skills by mastering one of the most efficient sorting algorithms? If so, delve into the world of merge sort in Python. Known for its powerful divide-and-conquer strategy, merge sort is indispensable for efficiently handling large datasets with precision. In this detailed guide, we’ll walk you through the complete […]

  • Optimizing Chatbot Performance: KPIs to Track Chatbot Accuracy

    In today’s digital age, chatbots have become integral to customer service, sales, and user engagement strategies. They offer quick responses, round-the-clock availability, and the ability to handle multiple users simultaneously. However, the effectiveness of a chatbot hinges on its accuracy and conversational abilities. Therefore, it is necessary to ensure your chatbot performs optimally, tracking and […]

  • Reinforcement Learning: From Q-Learning to Deep Q-Networks

    In the ever-evolving field of artificial intelligence (AI), Reinforcement Learning (RL) stands as a pioneering technique enabling agents (entities or software algorithms) to learn from interactions with an environment. Unlike traditional machine learning methods reliant on labeled datasets, RL focuses on an agent’s ability to make decisions through trial and error, aiming to optimize its […]

  • Understanding AI Predictions with LIME and SHAP- Explainable AI Techniques

    As artificial intelligence (AI) systems become increasingly complex and pervasive in decision-making processes, the need for explainability and interpretability in AI models has grown significantly. This blog provides a comprehensive review of two prominent techniques for explainable AI: Local Interpretable Model-agnostic Explanations (LIME) and Shapley Additive Explanations (SHAP). These techniques enhance transparency and accountability by […]

  • Building and Deploying a Custom Machine Learning Model: A Comprehensive Guide

    Machine Learning models are algorithms or computational models that act as powerful tools. Simply put, a Machine Learning model is used to automate repetitive tasks, identify patterns, and derive actionable insights from large datasets. Due to these hyper-advanced capabilities of Machine Learning models, it has been widely adopted by industries such as finance and healthcare.  […]

  • Mastering Conversational UX: Best Practices for AI-Driven Chatbots

    In today’s digital landscape, where customer engagement reigns supreme, traditional marketing strategies are giving way to more interactive and personalized approaches. The rise of conversational interfaces, often powered by Artificial Intelligence (AI) and Natural Language Processing (NLP), has transformed how businesses interact with their audiences. Whether through AI-driven chatbots on websites, virtual assistants on mobile […]

Click to Copy