🙏

জয়  শ্রী  রাম

🕉

---

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:

• Sliding Window Core Concept
• Grumpy Shopkeeper
• Longest Substring With Atmost Two Distinct Characters
• Longest Substring With Atmost K Distinct Characters
• Longest Substring Without Repeating Characters

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, if a problem seems like a great candidate to be solved using Sliding Window technique at first, but as you started solving it you became more and more unsure about it, you may quickly try to find if the below two conditions hold for your problem. If your problem is an optimization problem like finding longest or shortest something (for example, Longest Substring Without Repeating Characters), remove the optimization part (like shortest, longest etc) from the problem before applying the below two conditions. If any of below two conditions do not hold true then there are chances that the problem might not be solved using 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 .

Java:

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[]

Python:

def subarraySum(self, input, k):
    cache = {}
    count = 0
    sum = 0
    cache[0] = 1  # initialization
    # this will take care of if there is a
    # subarray starting from index 0 that sums up to k
    i = 0
    while i < len(input):
        sum += input[i]
        if sum - k in cache.keys():
            count += cache[sum - k]
        cache[sum] = cache.getOrDefault(sum, 0) + 1
        i += 1
    return count


# Time Complexity= O(n) where n = length of input[]
    

Instructor: