What kind of problems cannot be solved by Sliding Window approach ?

Algorithms and Data Structures: TheAlgorist.com

System Design: SystemsDesign.Cloud

Low Level Design: LowLevelDesign.io

Frontend Engineering: FrontendEngineering.io
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 Bartender
 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 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.
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:
If you have any feedback, please use this form: https://thealgorists.com/Feedback.
Follow Us On LinkedIn