Before going through this chapter, please make sure you have very good understanding of Sliding Window technique and how it actually works. I would highly recommend you to go through the following chapters if you haven't already:


There are many problems out there that would look like a perfect fit to be solved by Sliding Window technique, but in reality that may not be the case and once you try hard to solve the problem using Sliding Window that would be like going down the rabbit hole. So whenever you are tempted to solve a problem by Sliding Window technique, it is very important to determine whether the problem could be solved by Sliding Window technique or not.

Once you have identified that a problem could be solve by Sliding Window technique you need to validate if the below two conditions hold true. If any of them do not hold true then the problem could not be solved by Sliding Window technique.
  • If a wider scope of the sliding window is valid, the narrower scope of that wider scope is valid.
  • If a narrower scope of the sliding window is invalid, the wider scope of that narrower scope is invalid.
Let's take a look at the Longest Substring Without Repeating Characters problem, which can be efficiently solved using Sliding Window algorithm, to verify if the above discussed statements hold true for this problem. Let's say an input string "aasdfghjklasdfa". "asdfghjkl" is a window which is valid for "substring without any repeating characters". Now, take a narrower scope of the window and see how it would still be valid: "dfgh". This proves the first statement: If a wider scope of the sliding window is valid, the narrower scope of that wider scope is valid.

Now let's take an example of a substring that is not valid for "a substring with no repeating characters": "asdfa". Now take a broader scope of the window: "klasdfa". Notice that the broader scope of the window is not valid since the narrower scope is invalid. This proves the second statement: If a narrower scope of the sliding window is invalid, the wider scope of that narrower scope is invalid.

Below problem will look like it could be solved using "Sliding Window" at first glance, only to later realize that it cannot be solved by Sliding Window approach.

Problem Statement:
Given an array of integers and an integer k, return the total number of subarrays whose sum equals to k.

Example 1:
Input: input = [2,3,5], k = 5
Output: 2

Example 2:
Input = [2,3,2], k = 5
Output: 2

Example 3:
Input: [-1, -1, 1], k = 0
Output: 1

See how the above discussed statements do not hold for above problem: When input is [-1, -1, 1, -1, -1, 1, 1], k = 0,
[-1, 1] is a valid window but a narrower scope [-1] or [1] is not valid.

Also, [-1, -1] is not a valid window, but a broader scope [-1, -1, 1, 1] is valid.

So now we know Sliding Window cannot be used to solve above problem.

Let's take a look at how this problem could be solved. Say for an example, input = [50, 40, 12, 36, 90], and k = 48. See how 50 + 40 + 12 + 36 = 138, 50 + 40 = 90 and 138 - 90 = 48 = k. So if, sum of all items in input[0...j] = 138, and sum of all items in input[i...j] = k, then input[0...i] = sum - k. So, if we keep all track of all sums starting from index 0 to index j for all j >=0 and j < n, where n = length of input[], then at any point if we get sum = M and we see that (M - k) is stored in memory (which means starting from index 0 to some index j, the sum of all items was M), then we would know that the last few items sum up to k.
So, basically we are iterating over input[] and at every index i we see if we got a subarray ending at index i that sums up to k.


public int subarraySum(int[] input, int k) {
    Map<Integer, Integer> cache = new HashMap<>();
    int count = 0;
    int sum = 0;

    cache.put(0, 1); // initialization
        // this will take care of if there is a
        // subarray starting from index 0 that sums up to k
    for (int i = 0; i < input.length; i++) {
        sum += input[i];
        if (cache.containsKey(sum - k)) {
            count += cache.get(sum - k);
        }
        cache.put(sum, cache.getOrDefault(sum, 0) + 1);
    }
    return count;
}
//Time Complexity= O(n) where n = length of input[]





Instructor:

Abhishek Dey

Abhishek Dey

A Visionary Software Engineer With A Mission To Empower Every Person & Every Organization On The Planet To Achieve More

Microsoft | University of Florida

View LinkedIn profile


If you have any feedback, please use this form: https://thealgorists.com/Feedback.




Subscribe to Our Youtube Channel

Follow Us On LinkedIn
wave