Sliding window-based problems are easy to identify if we practice a few. Problems such as finding the longest substring or shortest substring with some constraints are mostly based on sliding windows.
List: https://leetcode.com/list/x1lbzfk3
We can precisely follow these templates and build our conditions according to the questions
int i = 0, j = 0, ans = 0;
for (; j < N; ++j) {
// CODE: use A[j] to update state which might make the window invalid
for (; invalid(); ++i) { // when invalid, keep shrinking the left edge until it's valid again
// CODE: update state using A[i]
}
ans = max(ans, j - i + 1); // the window [i, j] is the maximum window we've found thus far
}
return ans;
Essentially, we want to keep the window valid at the end of each outer for loop.
So
state? It should be the sum of numbers in the windowinvalid? The window is invalid if (j - i + 1) * A[j] - sum > k.FAQ:
O(NlogN)? The sorting takes O(NlogN). The two pointer part only takes O(N) because both the pointers i and j traverse the array ONLY ONCE.(j - i + 1) * A[j] - sum <= k valid? (j - i + 1) is the length of the window [i, j]. We want to increase all the numbers in the window to equal A[j], the number of operations needed is (j - i + 1) * A[j] - sum which should be <= k. For example, assume the window is [1,2,3], increasing all the numbers to 3 will take 3 * 3 - (1 + 2 + 3) operations.int i = 0, j = 0;
for (; j < N; ++j) {
// CODE: use A[j] to update state which might make the window invalid
if (invalid()) { // Increment the left edge ONLY when the window is invalid. In this way, the window GROWs when it's valid, and SHIFTs when it's invalid
// CODE: update state using A[i]
++i;
}
// after `++j` in the for loop, this window `[i, j)` of length `j - i` MIGHT be valid.
}
return j - i; // There must be a maximum window of size `j - i`.
Essentially, we GROW the window when it's valid, and SHIFT the window when it's invalid.
Note that there is only a SINGLE for loop now!
Ques: Frequency of the most frequent element: