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.