Introduction
Sliding window problems require you to keep a fixed size window that satisfies a certain criteria and shift or slide the window as soon as a violation is encountered.
A Few Examples
Problem
Given an array of integers A and an integer limit, return the size of the longest non-empty subarray such that the absolute difference between any two elements of this subarray is less than or equal to limit.
Algorithm
The key idea is to maintain an ordered multiset of elements and compare the max and the min values to see if they exceed limit. Each time we encounter a violation we will decrease the window size by one beginning from the left hand side. The gap of the largest possible subarray we have seen will remain and at the end the array size - our ending left pointer (i) will give us the answer.
Problem
Given an array of integers nums and an integer k. A continuous subarray is called nice if there are k odd numbers on it. Return the number of nice sub-arrays.
Algorithm
There are several problems that will ask you to find the number of continuous subarrays containing k properties (odd #s in this example). The key insight to remember here is that to arrive at exactly k items which satisfy a certain property, we just have to count the total length of continuous subarrays which satisfy atmost k elements and those that satisfy at most k-1 elements and take the difference between two. Where the at most k-1 and the at most k differ means we have exclusive subarrays that only work for the exactly k case. Solution follows below:
Practice Problems
MEDIUM
Count Number of Nice Subarrays
Number of Substrings Containing All Three Characters
Replace the Substring for Balanced String
HARD
Shortest Subarray with Sum at least K
Subarrays with K Different Integers
