Sliding Window: Examples
Worked problems from the questions chapter, reasoning and code together, one shape at a time.
Fixed Size
Maximum Average Subarray I gives an array and an integer k, and asks for the contiguous subarray of length k with the highest average, returning that average. The size is handed over directly, which makes this the cleanest place to see the mechanics with nothing else in the way.
Brute force computes the sum of every window of size k from scratch, adding up k elements each time, O(n * k) overall. But two neighboring windows share k - 1 elements, sliding forward by one only changes two of them, one leaves from the left, one enters from the right. The sum doesn’t need rebuilding, only adjusting by the difference between those two.
The one question this whole pattern comes down to, what moves left forward, has the simplest possible answer here. Nothing about the window’s contents matters, only its length, once the window would grow past k, the oldest element has to leave. The code never even tracks left explicitly, right - k is always the element about to leave.
Take nums = [1, 12, -5, -6, 50, 3], k = 4. The first window, [1, 12, -5, -6], sums to 2.
right enters leaves windowSum bestSum
4 50 1 51 51
5 3 12 42 51
bestSum ends at 51, from the window [12, -5, -6, 50], and 51 / 4 = 12.75, the answer.
This array has negative numbers, and nothing breaks. The direction check from Question 3, whether growing the window always moves the tracked value the same way, only matters when the shrinking condition is derived from the window’s contents. Here the condition is just size, so it never comes up.
// Maximum Average Subarray I
// https://leetcode.com/problems/maximum-average-subarray-i/description/
//
// Problem: given an array and an integer k, find the contiguous
// subarray of length k with the highest average, and return that
// average.
//
// The window's size is given directly, so what moves left forward
// is just the window's length reaching past k, nothing about its
// contents. Build the sum of the first k elements once, then slide,
// adding the element entering and subtracting the one leaving.
function findMaxAverage(nums, k) {
let windowSum = 0;
for (let i = 0; i < k; i++) {
windowSum += nums[i];
}
let bestSum = windowSum;
for (let right = k; right < nums.length; right++) {
// nums[right] enters, nums[right - k] leaves, the window
// stays exactly k wide without any separate size check.
windowSum += nums[right] - nums[right - k];
bestSum = Math.max(bestSum, windowSum);
}
return bestSum / k;
}
module.exports = { findMaxAverage };
Permutation in String gives two strings, s1 and s2, and asks whether s2 contains a permutation of s1 as a contiguous substring.
Read the statement the same way as before, and notice what’s missing. There’s no min or max ask, the answer is a yes or no. But “substring” is still the contiguous range, and the window’s size is handed over directly, a permutation of s1 has exactly s1’s length. So this is the fixed-size shape, and the answer to “what moves left” is the same as in Maximum Average Subarray, the window’s length reaching past s1’s length.
A permutation of s1 is an anagram of s1, same letters, same counts. That’s the Valid Anagram question from the Hashing chapter, asked of every window of s2 that is exactly s1’s length. Checking each window from scratch would rebuild its letter counts every time. Sliding window supplies the other half of the solution, moving the window forward changes exactly two letters, one leaves, one enters, so the counts adjust in constant time. Hashing decides what a match means, sliding window decides how to check it at every position without redoing the work.
Comparing the two count arrays in full after every move would cost a scan of 26 letters each time. The same idea from Minimum Window Substring applies here, keep a counter, matches, of how many of the 26 letters currently have equal counts in both. A letter becomes matched when its count reaches the target, and stops being matched when it moves one past it. The window is a permutation exactly when matches reaches 26.
Take s1 = "ab", s2 = "eidbaooo", so the window is 2 wide. The first window, ei, has 22 letters matching, every letter except a, b, e, and i.
right window entering leaving matches
2 id d e 22
3 db b i 24
4 ba a d 26
At right = 2, d enters and stops matching, e leaves and starts matching again, so matches holds at 22. At right = 3, b enters and reaches its target, i leaves and starts matching, matches goes to 24. At right = 4, a enters and reaches its target, d leaves and starts matching, matches reaches 26, and the answer is true, the window ba is a permutation of ab.
// Permutation in String
// https://leetcode.com/problems/permutation-in-string/description/
//
// Problem: given two strings of lowercase letters, s1 and s2,
// return true if s2 contains a permutation of s1 as a contiguous
// substring.
//
// A permutation of s1 is an anagram of s1, same letters, same
// counts. That's the Valid Anagram question from the Hashing
// chapter, asked of every window of s2 that is exactly s1's length.
// Sliding window supplies the other half, sliding forward changes
// only two letters, so the counts adjust in constant time instead
// of being rebuilt for every window.
//
// Instead of comparing the two count arrays in full every step,
// keep a counter, matches, of how many of the 26 letters currently
// have equal counts in both. The window is a permutation exactly
// when matches reaches 26.
function checkInclusion(s1, s2) {
const k = s1.length;
if (k > s2.length) return false;
const index = (ch) => ch.charCodeAt(0) - "a".charCodeAt(0);
const need = new Array(26).fill(0);
const window = new Array(26).fill(0);
for (let i = 0; i < k; i++) {
need[index(s1[i])]++;
window[index(s2[i])]++;
}
let matches = 0;
for (let i = 0; i < 26; i++) {
if (need[i] === window[i]) matches++;
}
if (matches === 26) return true;
for (let right = k; right < s2.length; right++) {
const entering = index(s2[right]);
const leaving = index(s2[right - k]);
// Update matches after each change, a letter becomes matched
// when its count reaches the need, and stops being matched
// when it moves one past the need.
window[entering]++;
if (window[entering] === need[entering]) matches++;
else if (window[entering] === need[entering] + 1) matches--;
window[leaving]--;
if (window[leaving] === need[leaving]) matches++;
else if (window[leaving] === need[leaving] - 1) matches--;
if (matches === 26) return true;
}
return false;
}
module.exports = { checkInclusion };
Sliding Window Maximum gives an array and a window size k, and asks for an array containing the maximum of every window as it slides across, one number per window position. For nums = [1, 3, -1, -3, 5, 3, 6, 7] and k = 3, the answer is [3, 3, 5, 5, 6, 7].
The size is given, so this is the fixed-size shape, and left moves when the window’s length passes k. The maximum being asked for is the largest value inside each window, not a window size, so there’s no min or max ask over sizes here, same as Permutation in String.
The brute force finds the max of every window by scanning all k of its elements, n - k + 1 windows at k elements each, O(n * k). Each slide changes exactly two things, one element leaves, one enters, and the other k - 1 elements stay exactly as they were. The brute force ignores that and re-reads them anyway.
For a sum, using that is one line, add the entering number, subtract the leaving one. A maximum has no such shortcut. A single running max works until the max itself leaves the window, and then there’s nothing to subtract, the next biggest has to come from somewhere in the elements that stayed, and a lone variable never recorded it. So the question becomes: for the k - 1 elements that stay, what is the least that needs to be remembered so the next max can be answered without re-reading them?
Remembering only the max and the second max feels like enough, and it isn’t. Take nums = [9, 8, 7, 6, 5], k = 3, correct answers [9, 8, 7]. The first window [9, 8, 7] has max 9, second 8, and 7 gets thrown away. Slide, 9 leaves, 6 enters, the window is [8, 7, 6], the max is 8, correct, but the new second max should be 7, which was discarded, so 6 takes its place. Slide again, 8 leaves, the window is [7, 6, 5], and the tracker only knows 6, so it reports 6 when the true max is 7. In a decreasing run, every number in the window gets its turn as the max, one after another, as the bigger ones ahead of it leave, so every one of them has to be remembered.
What can be forgotten is a number that will never get a turn. A number that is both older and smaller than something that arrived after it. Take [3, 1, 2]. 1 sits before 2, so 1 leaves the window before 2 does, and 2 is bigger the whole time they share the window. 1 will never be the max, so it can be dropped. Smaller numbers that arrive later are the ones to keep, since they are still in the window after the bigger ones ahead of them leave.
That list of surviving candidates is kept in a deque, short for double-ended queue, a list where items can be added and removed at both ends. A regular queue only adds at the back and removes from the front, a stack only touches one end, a deque allows both, and this problem uses both.
A new number arrives, and everything smaller than or equal to it is removed from the back, one at a time, stopping at the first number that is bigger, then the new number is added at the back. The front number’s position has slid out of the window, so it is removed from the front. The current max is needed, so the front is read.
The deque ends up in decreasing order from front to back, but nothing sorts it. The order is a side effect of the removal rule, every number gets removed if something bigger and newer arrives behind it, so whatever sits in front of any number is bigger or equal. That’s why the front is always the max, and finding the max costs nothing, no scan. It also never holds the whole window, only the survivors, and can be shorter than the window, never longer. Numbers equal to the new one are removed too, the newer copy leaves later and is just as large, so the older one never matters.
If a new number is smaller than the front but bigger than the back, removal continues from the back until it reaches something bigger, and the new number goes right after it. With deque values [7, 5, 2] and a new number 4, 2 is removed, 5 is bigger so removal stops, and 4 is added, giving [7, 5, 4]. It sits in the middle of the old contents by value but at the back of the deque, since everything that was behind it was removed.
Take nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3, showing the deque’s values.
new number deque after max
1 [1] -
3 [3] - (1 dropped, 3 beats it)
-1 [3, -1] 3
-3 [3, -1, -3] 3
5 [5] 5 (-3, -1, 3 all dropped)
3 [5, 3] 5
6 [6] 6 (3 and 5 dropped)
7 [7] 7
When 5 arrives, the window is [-1, -3, 5], but the deque holds only 5. -1 and -3 sit before 5 and leave sooner, so they can never win again. The result is [3, 3, 5, 5, 6, 7].
Nothing in that trace ever removed the front for sliding out of the window, because every number arriving was big enough to clear things first. That case shows up in a decreasing run. Take nums = [9, 8, 7, 6, 5], k = 3.
new number deque before front check front out of window? deque after max
9 [9] no [9] -
8 [9, 8] no [9, 8] -
7 [9, 8, 7] no [9, 8, 7] 9
6 [9, 8, 7, 6] yes, 9 slid out [8, 7, 6] 8
5 [8, 7, 6, 5] yes, 8 slid out [7, 6, 5] 7
Nothing new beats anything ahead of it, so the deque keeps everything, and the front leaves purely because its position slid out of the window. The result is [9, 8, 7], the correct answer, and the exact case where keeping only the max and the second max failed.
Each number is added to the deque once and removed at most once, so the whole thing runs in O(n), even though a single step can remove many numbers. The code stores indices instead of values, since the front’s position is what says whether it has slid out.
// Sliding Window Maximum
// https://leetcode.com/problems/sliding-window-maximum/description/
//
// Problem: given an array and a window size k, return an array where
// each entry is the maximum of one window as it slides across, so
// the result has one number per window position.
//
// The window's size is given, so this is the fixed-size shape. The
// difficulty is the tracked value. A maximum has no undo, when the
// current max leaves the window there is nothing to subtract, and
// the next biggest has to already be known.
//
// A deque of indices solves it. It holds only the numbers that could
// still become the max, in decreasing order of value, so the front
// is always the current max.
//
// New number arrives: remove from the back while the back is
// smaller than or equal to it, those are older and smaller, so
// they leave the window first and can never win again. Then add
// the new number at the back.
//
// Front number has slid out of the window: remove it from the
// front.
//
// Max needed: read the front.
//
// JavaScript has no built-in deque. An array handles the back
// (push and pop are fast). For the front, a head index moves forward
// instead of calling shift(), which can be slow on large arrays.
function maxSlidingWindow(nums, k) {
const deque = []; // indices into nums, values decreasing
let head = 0; // deque[head] is the front
const result = [];
for (let right = 0; right < nums.length; right++) {
// Drop everything at the back that the new number beats.
while (deque.length > head && nums[deque[deque.length - 1]] <= nums[right]) {
deque.pop();
}
deque.push(right);
// The window covers right - k + 1 through right. If the
// front's index is older than that, it has slid out.
if (deque[head] <= right - k) {
head++;
}
// Windows only exist once the first k numbers have arrived.
if (right >= k - 1) {
result.push(nums[deque[head]]);
}
}
return result;
}
module.exports = { maxSlidingWindow };
Variable Size, Maximizing
Longest Substring Without Repeating Characters gives a string and asks for the length of the longest substring with no repeated character.
Read the problem statement word by word. “Longest” is a max ask, the first signal. “Substring” is a contiguous range, the second signal, stronger. “Without repeating characters” is the third, it hands over the condition that moves left, the window is invalid the moment a character shows up twice inside it. It also passes the direction check on its own, dropping a character off the left edge can only reduce or keep the same number of duplicates, never create a new one.
The brute force checks every substring for duplicates, rebuilding a set of its characters each time. The window keeps one set alive instead, holding exactly the characters currently inside it, added to as right grows, removed from as left shrinks. That removal is the undo step, and it’s what marks this as sliding window rather than plain two pointers.
Each time right reaches a new character, one question decides everything, is that character already inside the window. If not, add it and move on. If yes, left has to step forward, dropping characters off the left edge one at a time, until the duplicate is gone, and only then does the new character go in.
That check has to happen before adding, not after. A Set silently ignores an attempt to add a value it already holds, so adding first would hide the very duplicate we need to notice.
Take s = "abcabcbb".
right char window before action left window after best
0 a {} add 0 {a} 1
1 b {a} add 0 {a, b} 2
2 c {a, b} add 0 {a, b, c} 3
3 a {a, b, c} a inside, drop a, then add 1 {b, c, a} 3
4 b {b, c, a} b inside, drop b, then add 2 {c, a, b} 3
5 c {c, a, b} c inside, drop c, then add 3 {a, b, c} 3
6 b {a, b, c} b inside, drop a, drop b, add 5 {c, b} 3
7 b {c, b} b inside, drop c, drop b, add 7 {b} 3
best ends at 3, from the window abc, matching the known answer.
// Longest Substring Without Repeating Characters
// https://leetcode.com/problems/longest-substring-without-repeating-characters/description/
//
// Problem: given a string, return the length of the longest
// substring that contains no repeated character.
//
// "Longest" is the max ask, "substring" is the contiguous range,
// "without repeating" is the condition that moves left forward.
// The tracked value is a set of the characters currently inside
// the window, added to as right grows, removed from as left shrinks.
function lengthOfLongestSubstring(s) {
const inWindow = new Set();
let left = 0;
let best = 0;
for (let right = 0; right < s.length; right++) {
// A Set can't hold a duplicate, so the check has to happen
// before adding, not after. If the character entering is
// already inside the window, shrink from the left until it
// isn't.
while (inWindow.has(s[right])) {
inWindow.delete(s[left]);
left++;
}
inWindow.add(s[right]);
best = Math.max(best, right - left + 1);
}
return best;
}
module.exports = { lengthOfLongestSubstring };
Longest Repeating Character Replacement gives a string of uppercase letters and an integer k. Up to k characters can be replaced with any other letter, and the question is the length of the longest substring that can be made all one letter.
“Longest” is the max ask, “substring” is the contiguous range. The third piece, the condition that moves left, isn’t stated anywhere in the problem, it has to be derived. A window can be turned into all one letter by replacing every character that isn’t its most frequent letter, so the number of replacements needed is windowSize - countOfMostFrequentLetter. The window is valid while that stays at most k, and invalid the moment it goes over, which is when left steps forward.
The tracked value here is a frequency map of the letters currently inside the window, incremented as right adds a letter, decremented as left drops one. That’s the Frequency bucket from the Hashing chapter sitting inside the window. Sliding window decides how the window moves, hashing supplies what gets tracked inside it, and most non-trivial sliding window problems are one wrapped around the other.
Take s = "AABABBA", k = 1.
right char window after shrinking counts size most size - most best
0 A A A1 1 1 0 1
1 A AA A2 2 2 0 2
2 B AAB A2 B1 3 2 1 3
3 A AABA A3 B1 4 3 1 4
4 B BAB A1 B2 3 2 1 4
5 B BABB A1 B3 4 3 1 4
6 A BBA A1 B2 3 2 1 4
At right = 4 the window AABAB needs 5 - 3 = 2 replacements, over k = 1, so left steps forward twice, first dropping an A, then another A, until the window is BAB. The same thing happens at right = 6. best ends at 4, the known answer for this input.
A widely used version of this solution skips recomputing the most frequent count on every shrink, it keeps a running maximum that only ever goes up and never lowers it. That saves scanning the map each time and gives correct answers, but proving that a stale maximum can never inflate the result takes a subtler argument than belongs here. The version below recomputes exactly, which stays cheap since the map never holds more than 26 letters.
// Longest Repeating Character Replacement
// https://leetcode.com/problems/longest-repeating-character-replacement/description/
//
// Problem: given a string of uppercase letters and an integer k,
// you may replace up to k characters with any other letter. Return
// the length of the longest substring that can be made all one
// letter this way.
//
// "Longest" is the max ask, "substring" is the contiguous range.
// The condition that moves left isn't stated, it has to be derived.
// A window can be made all one letter if the characters that aren't
// its most frequent letter number at most k, those are the ones
// that get replaced. So the window is valid while
// windowSize - countOfMostFrequentLetter <= k.
//
// The tracked value is a frequency map of the letters currently in
// the window, incremented as right grows, decremented as left shrinks.
function characterReplacement(s, k) {
const counts = new Map();
let left = 0;
let best = 0;
for (let right = 0; right < s.length; right++) {
counts.set(s[right], (counts.get(s[right]) || 0) + 1);
// Recompute the most frequent letter's count from the map
// each time. At most 26 entries, so this stays cheap.
while (right - left + 1 - Math.max(...counts.values()) > k) {
counts.set(s[left], counts.get(s[left]) - 1);
left++;
}
best = Math.max(best, right - left + 1);
}
return best;
}
module.exports = { characterReplacement };
Variable Size, Minimizing
Minimum Size Subarray Sum gives an array of positive integers and a target, and asks for the length of the shortest contiguous subarray whose sum is at least the target, or 0 if no such subarray exists.
The problem guarantees every number is positive, no zeros, no negatives. That guarantee is what makes everything below work, and it’s worth holding onto from the start.
“Minimum” is the min ask, “subarray” is the contiguous range. The condition that moves left flips direction from the last two problems. Those shrank while the window was invalid. Here, growing right pushes the sum toward the target, so once the sum reaches it, the window is valid, and left keeps stepping forward for as long as the window stays valid, recording a smaller answer at every step, stopping only when dropping one more element would break it.
Because every number is positive, growing the window can only raise the sum and shrinking it can only lower it. That’s the direction check passing, and it’s the reason it’s safe to stop shrinking the moment the sum drops below the target, nothing further along could have brought it back up.
Take target = 7, nums = [2, 3, 1, 2, 4, 3].
right added sum shrink steps left sum after best
0 2 2 none 0 2 -
1 3 5 none 0 5 -
2 1 6 none 0 6 -
3 2 8 record 4, drop 2 1 6 4
4 4 10 record 4, drop 3, record 3, drop 1 3 6 3
5 3 9 record 3, drop 2, record 2, drop 4 5 3 2
best ends at 2, from the window [4, 3], the known answer for this input.
Now the same idea with a negative number, to see exactly what breaks. Take target = 5, nums = [4, -5, 6]. The true answer is 1, the single element [6]. Running the same loop, right = 2 gives a sum of 4 - 5 + 6 = 5, valid, record a length of 3. Then left drops the 4, the sum falls to 1, below the target, and the loop stops, reporting 3. It stopped too early. The element actually blocking a smaller answer was the -5 in the middle, and dropping it would have raised the sum, but the loop only shrinks while the sum stays at or above the target, so it never got that far. With negatives in the array, growing or shrinking the window no longer moves the sum in one predictable direction, and this shrinking condition stops being trustworthy. That’s the case Subarray Sum Equals K in the Hashing chapter handles with prefix sums instead.
// Minimum Size Subarray Sum
// https://leetcode.com/problems/minimum-size-subarray-sum/description/
//
// Problem: given an array of POSITIVE integers and a target, return
// the length of the shortest contiguous subarray whose sum is at
// least the target, or 0 if none exists.
//
// "Minimum" is the min ask, "subarray" is the contiguous range.
// The condition that moves left is the window's sum reaching the
// target. Once it does, the window is valid, and left keeps stepping
// forward for as long as it stays valid, recording a smaller answer
// at every step.
//
// This only works because every number is positive. Growing the
// window can only raise the sum, shrinking it can only lower it,
// so once dropping the leftmost element breaks the window, nothing
// further along could have helped.
function minSubArrayLen(target, nums) {
let left = 0;
let windowSum = 0;
let best = Infinity;
for (let right = 0; right < nums.length; right++) {
windowSum += nums[right];
while (windowSum >= target) {
best = Math.min(best, right - left + 1);
windowSum -= nums[left];
left++;
}
}
return best === Infinity ? 0 : best;
}
module.exports = { minSubArrayLen };
Minimum Window Substring gives two strings, s and t, and asks for the shortest substring of s that contains every character of t, duplicates included, or an empty string if none exists.
“Minimum” is the min ask, “substring” is the contiguous range. The condition that moves left is the window containing everything t needs, so the shape matches the last problem, right grows until the window becomes valid, then left shrinks for as long as it stays valid, recording the smallest window along the way.
What’s different is how validity works. The last problem checked a single running sum against a target. Here, validity is about how many of each specific character the window holds, which points to a frequency map, two of them, one for what t requires, built once, and one for what the window currently holds, adjusted as right grows and left shrinks. The direction check still holds, adding a character can never reduce what the window covers, and dropping one can never add coverage.
Comparing the two maps in full after every move would cost a scan each time. The usual trick keeps a single counter instead, formed, the number of distinct required characters that currently have enough copies in the window. It only changes at the exact moment a character’s count reaches its required amount going up, or drops below it going down. Extra copies beyond the requirement change nothing, and neither does dropping one of them. Validity becomes one comparison, formed against the number of distinct characters in t.
Take s = "ADOBECODEBANC", t = "ABC", so A, B, and C are each required once.
right char formed events left best
0-2 A D O 1 none 0 -
3 B 2 none 0 -
4 E 2 none 0 -
5 C 3 valid, record ADOBEC (6), drop A, formed back to 2 1 ADOBEC
6-8 O D E 2 none 1 ADOBEC
9 B 2 B count is now 2, formed unchanged 1 ADOBEC
10 A 3 valid, windows of 10, 9, 8, 7, 6 are none smaller, 6 ADOBEC
dropping C at left 5 sends formed back to 2
11 N 2 none 6 ADOBEC
12 C 3 valid, 7 and 6 are not smaller, record EBANC (5), 10 BANC
record BANC (4), drop B, formed back to 2
At right = 9, the second B arrives and formed doesn’t move, B was already covered. Later, when left drops the first B, its count falls from 2 to 1, still enough, so formed doesn’t move then either. The answer is BANC, the known result for this input.
// Minimum Window Substring
// https://leetcode.com/problems/minimum-window-substring/description/
//
// Problem: given strings s and t, return the shortest substring of
// s that contains every character of t, duplicates included, or an
// empty string if no such substring exists.
//
// "Minimum" is the min ask, "substring" is the contiguous range.
// The condition that moves left is the window containing everything
// t needs. Two frequency maps are involved, what t requires (built
// once) and what the window currently holds (adjusted as right grows
// and left shrinks).
//
// Comparing the two maps in full after every move would cost a scan
// each time. Instead, keep a single counter, formed, of how many
// distinct required characters currently have enough copies in the
// window, and only touch it when a character's count crosses its
// required amount. Validity then becomes one comparison.
function minWindow(s, t) {
if (t.length > s.length) return "";
const need = new Map();
for (const ch of t) {
need.set(ch, (need.get(ch) || 0) + 1);
}
const required = need.size;
const window = new Map();
let formed = 0;
let left = 0;
let bestLength = Infinity;
let bestStart = 0;
for (let right = 0; right < s.length; right++) {
const entering = s[right];
window.set(entering, (window.get(entering) || 0) + 1);
// Only the exact moment the count reaches the required
// amount counts. Extra copies beyond that change nothing.
if (need.has(entering) && window.get(entering) === need.get(entering)) {
formed++;
}
while (formed === required) {
if (right - left + 1 < bestLength) {
bestLength = right - left + 1;
bestStart = left;
}
const leaving = s[left];
window.set(leaving, window.get(leaving) - 1);
// Only dropping below the required amount breaks it.
if (need.has(leaving) && window.get(leaving) < need.get(leaving)) {
formed--;
}
left++;
}
}
return bestLength === Infinity ? "" : s.substring(bestStart, bestStart + bestLength);
}
module.exports = { minWindow };
Twists on the Standard Shapes
The problems above each fit one of the three shapes as stated. The four below need one extra move before the window applies, a reframing, a subtraction, a sort, or a baseline. Three of them have a hidden window, one the statement never mentions, covered in Question 5 of Asking the Right Questions. Each one still comes down to the same question, what moves left, but the work is in getting the problem into a shape where that question has an answer.
Maximum Points You Can Obtain from Cards lays cards in a row, each with a point value. In each of k steps, take one card from either the left end or the right end, and the goal is the maximum total points.
Read the statement the way the earlier problems were read. “Maximum” is the max ask, the first signal. But the cards come off the two ends, so there is no contiguous range in what gets taken, and the second signal doesn’t fire on the surface. The window in this problem is hidden, and the steps below are how it comes out.
Only the first k and the last k cards matter. Exactly k cards get taken, so at most k of them come from the left, and nothing past the first k cards on the left can ever be reached. The same holds on the right. In [1, 2, 3, 4, 5, 6, 1] with k = 3, the reachable cards are 1, 2, 3 on the left and 5, 6, 1 on the right. The 4 in the middle can never be taken, whatever the choices are.
When k is more than half of n, the two ends overlap. The first k and the last k cards then share some cards, and every card is reachable, so nothing drops out of the problem. Nothing gets counted twice either. A choice takes i cards from the left and k - i from the right, those add up to exactly k, and k is at most n, so the two ends never reach the same card. At the extreme, k = n, every card is taken and the answer is the total.
Picking the bigger end each step fails. Each step only offers the leftmost or the rightmost card, which suggests two pointers, one at each end, taking whichever card is bigger. Take [1, 2, 100000, 3, 4, 5] with k = 3. Comparing the ends takes 5, then 4, then 3, for 12. The best answer is 1 + 2 + 100000 = 100003, taking three cards from the left. This fails the test from the Two Pointers chapter, a pointer is only safe to move when it can never lose a better answer, and here taking the bigger end can lose one, since a small card at the edge can sit directly in front of a huge one. The decision can’t be made one card at a time by looking at the two ends, it has to be made about the split as a whole, how many cards come from the left.
The cards left behind form a window. Take i cards from the left and k - i from the right, and what remains is exactly n - k cards in one unbroken block in the middle. Sliding that block from one end of the array to the other covers every split, from i = 0 to i = k. The points taken are the total minus the sum of that block, so taking the most points is the same as leaving the least. The window is hidden because it isn’t in the cards taken, it’s in the ones not taken. Its size is fixed at n - k, and what is being asked for is its smallest sum, so this is the fixed-size shape. The answer is the total of all cards minus the smallest window sum.
That settles the [1, 2, 100000, 3, 4, 5] case. The window is 6 - 3 = 3 wide and the total is 100015. The window sums are 100003, 100005, 100007, and 12. The smallest is 12, from the block [3, 4, 5], so the answer is 100015 - 12 = 100003, with no card-by-card choice made anywhere.
The cue to carry to other problems is the wording, “from either end” or “from the edges” is a hint to look at what sits in the middle, not at the ends.
Take cardPoints = [1, 2, 3, 4, 5, 6, 1], k = 3. The total is 22, and the window is 7 - 3 = 4 wide. The first window, [1, 2, 3, 4], sums to 10.
right enters leaves windowSum minWindow
4 5 1 14 10
5 6 2 18 10
6 1 3 16 10
The smallest window sum is 10, so the answer is 22 - 10 = 12, taking 5, 6, and 1 from the right end.
// Maximum Points You Can Obtain from Cards
// https://leetcode.com/problems/maximum-points-you-can-obtain-from-cards/description/
//
// Problem: cards lie in a row, each with a point value. In each of
// k steps, take one card from either the left end or the right end.
// Return the maximum total points obtainable.
//
// The cards taken are never a contiguous range, they come from the
// two ends. The cards left behind are. Taking i cards from the left
// and k - i from the right always leaves exactly n - k cards in a
// row in the middle, and every position of that middle block is
// reachable. So maximizing what is taken means minimizing what is
// left, the smallest sum of any window of size n - k.
function maxScore(cardPoints, k) {
const n = cardPoints.length;
const windowSize = n - k;
let total = 0;
for (const points of cardPoints) {
total += points;
}
// Taking every card leaves an empty window.
if (windowSize === 0) return total;
let windowSum = 0;
for (let i = 0; i < windowSize; i++) {
windowSum += cardPoints[i];
}
let minWindow = windowSum;
for (let right = windowSize; right < n; right++) {
windowSum += cardPoints[right] - cardPoints[right - windowSize];
minWindow = Math.min(minWindow, windowSum);
}
return total - minWindow;
}
module.exports = { maxScore };
Count Number of Nice Subarrays gives an array of positive integers and an integer k, and asks for the number of contiguous subarrays that contain exactly k odd numbers.
Read the statement the usual way. There’s no min or max ask, the answer is a count. “Subarray” is the contiguous range. So the recognition only half fires, and the third stage, the condition that moves left, is where it gets stuck. A window handles “at most k odd numbers” cleanly, adding an element can only keep or raise the odd count and dropping one from the left can only keep or lower it. “Exactly k” breaks that. A window with too few odd numbers and one with too many are both invalid, so no single direction of shrinking fixes both.
A first attempt, and what it misses. Grow right until the window holds k odd numbers, then walk left forward over the leading even numbers, adding one to a count at each step, since each step is another valid start. Take [2, 1, 1] with k = 2. At right = 2, the valid starts are index 0, giving [2, 1, 1], and index 1, giving [1, 1]. That’s two subarrays, not one. The leading 2 is an even number, so starting before it or after it gives the same odd count.
It still isn’t enough to stop there. Take [2, 1, 1, 2]. When right moves onto the trailing 2, the window still holds exactly two odd numbers, and two more subarrays appear, [1, 1, 2] and [2, 1, 1, 2]. Even numbers on the right give the same kind of extra freedom as even numbers on the left, and a walk that has already moved left forward can’t count them.
What actually decides a subarray. Only which k consecutive odd numbers it contains. The even numbers around them don’t change the odd count, so they only add freedom in where the subarray starts and where it ends. That suggests listing the positions of the odd numbers and working from that list.
In [2, 1, 1, 2] the odd numbers sit at indices 1 and 2. Put a marker at -1 before the first and one at 4, the array’s length, after the last, giving [-1, 1, 2, 4]. For the group of two odd numbers, 1 and 2:
start choices = 1 - (-1) = 2 (start at index 0 or 1)
end choices = 4 - 2 = 2 (end at index 2 or 3)
count = 2 * 2 = 4
The four subarrays are [1, 1], [2, 1, 1], [1, 1, 2], and [2, 1, 1, 2]. The two choices multiply because any start pairs with any end. The markers stand in for “no previous odd number” and “no next odd number”, so the first and last groups need no special case.
Take nums = [1, 1, 2, 1, 1], k = 3. The odd numbers sit at indices 0, 1, 3, 4, and with the markers the list is [-1, 0, 1, 3, 4, 5]. A window of size k = 3 slides over that list, one odd number at a time.
group of odd positions start choices end choices product
0, 1, 3 0 - (-1) = 1 4 - 3 = 1 1
1, 3, 4 1 - 0 = 1 5 - 4 = 1 1
The total is 2, matching the two subarrays that contain exactly three odd numbers, [1, 1, 2, 1] and [1, 2, 1, 1]. This is a sliding window too, fixed at k odd positions wide, moving over the list of odd positions instead of over the array itself.
A more general route. Every subarray with at most k odd numbers either has exactly k or has at most k - 1, so the count with exactly k is the count with at most k minus the count with at most k - 1. “At most” passes the direction check, so each count is a plain window. Inside one, once [left, right] holds at most k odd numbers, every subarray ending at right and starting anywhere from left to right does too, which is right - left + 1 new subarrays per position of right.
On the same input, counting at most 3 odd numbers:
right odds left new subarrays running count
0 1 0 1 1
1 2 0 2 3
2 2 0 3 6
3 3 0 4 10
4 4->3 1 4 14
At right = 4 the fourth odd number pushes the count over the limit, so left drops the first 1, and the total is 14. Counting at most 2 the same way gives 12, and 14 - 12 = 2, the same answer. This version is longer here, but it carries over unchanged to problems like Subarrays with K Different Integers, where there’s no easy list of positions to slide over.
// Count Number of Nice Subarrays
// https://leetcode.com/problems/count-number-of-nice-subarrays/description/
//
// Problem: given an array of positive integers and an integer k,
// count the contiguous subarrays that contain exactly k odd numbers.
//
// "Exactly k" doesn't fit a window that grows and shrinks, a window
// with too few odd numbers and one with too many are both invalid,
// so no single direction of shrinking fixes both.
//
// What decides a subarray is only which k consecutive odd numbers it
// contains. Even numbers around them change nothing. So list the
// positions of the odd numbers, and slide a window of size k over
// that list. For each group of k odd positions, the subarray can
// start anywhere after the previous odd number up to the group's
// first odd, and end anywhere from the group's last odd up to just
// before the next odd number. Those two counts multiply.
//
// Markers at -1 and at nums.length stand in for "no previous odd"
// and "no next odd", so the first and last groups need no special case.
function numberOfSubarrays(nums, k) {
const oddPositions = [-1];
for (let i = 0; i < nums.length; i++) {
if (nums[i] % 2 === 1) oddPositions.push(i);
}
oddPositions.push(nums.length);
const realOdds = oddPositions.length - 2;
let count = 0;
// A group covers oddPositions[i] through oddPositions[i + k - 1].
for (let i = 1; i + k - 1 <= realOdds; i++) {
const leftChoices = oddPositions[i] - oddPositions[i - 1];
const rightChoices = oddPositions[i + k] - oddPositions[i + k - 1];
count += leftChoices * rightChoices;
}
return count;
}
// The general alternative: exactly k = (at most k) - (at most k - 1).
// Every subarray with at most k odd numbers either has exactly k or
// has at most k - 1. "At most" passes the direction check, so it is
// a plain window. Once [left, right] holds at most k odd numbers,
// every subarray ending at right and starting anywhere from left to
// right does too, which is right - left + 1 new subarrays.
function atMost(nums, k) {
if (k < 0) return 0;
let left = 0;
let odds = 0;
let count = 0;
for (let right = 0; right < nums.length; right++) {
if (nums[right] % 2 === 1) odds++;
while (odds > k) {
if (nums[left] % 2 === 1) odds--;
left++;
}
count += right - left + 1;
}
return count;
}
function numberOfSubarraysBySubtraction(nums, k) {
return atMost(nums, k) - atMost(nums, k - 1);
}
module.exports = { numberOfSubarrays, numberOfSubarraysBySubtraction };
Frequency of the Most Frequent Element gives an array and a budget k. One operation increases any element by 1, at most k operations are allowed, and the question is the highest frequency any single value can reach.
Read the statement the usual way. “Highest” is the max ask, the first signal. The second signal, a contiguous range, is nowhere in the statement. The array comes in whatever order it was given, and the elements that end up equal can come from any positions. This is a hidden window, one that only appears after a reframing, here a sort.
Increments only go up. Elements can only be raised, never lowered. So when a group of elements is made equal, the value they all end at is the group’s largest element. Raising the group past that only spends operations for nothing.
The cheapest group for a target. Raising an element to a target costs the target minus that element, so the elements closest below the target are the cheapest to raise. Once the array is sorted, the elements closest below a given element are exactly the ones just before it. So for a target sorted[right], the best group of any size is a stretch of the sorted array ending at right. That stretch is the window, and it exists only because the array was sorted first.
The cost is a formula, and it has to be derived. Raising every element in [left, right] up to sorted[right] costs the sum of the gaps:
(sorted[right] - sorted[left]) + (sorted[right] - sorted[left + 1]) + ... + (sorted[right] - sorted[right - 1])
Written without listing the gaps, that is sorted[right] * windowSize - windowSum. windowSum is the running value that gets added to as right grows and subtracted from as left shrinks, the same running sum used in the earlier problems. The window is valid while that cost stays within k.
What moves left. The direction check holds. Growing right to the next element can only raise the cost, since the array is sorted, the target gets bigger, and there is one more element to raise. Dropping from left can only lower it. So left moves while the cost is over k, and the answer is the largest window size seen.
Take nums = [1, 4, 8, 13], k = 5, already sorted.
right window cost valid? left best
0 [1] 1*1 - 1 = 0 yes 0 1
1 [1, 4] 4*2 - 5 = 3 yes 0 2
2 [1, 4, 8] 8*3 - 13 = 11 no 0 2
[4, 8] 8*2 - 12 = 4 yes 1 2
3 [4, 8, 13] 13*3 - 25 = 14 no 1 2
[8, 13] 13*2 - 21 = 5 yes 2 2
At right = 2, raising 1 and 4 up to 8 costs 11, over the budget, so left drops the 1, and the window [4, 8] costs 4. At right = 3, the same thing happens again. The best window stays at size 2, the known answer for this input.
// Frequency of the Most Frequent Element
// https://leetcode.com/problems/frequency-of-the-most-frequent-element/description/
//
// Problem: in one operation, increase any element by 1. With at most
// k operations, return the highest frequency any single value can
// reach.
//
// Increments only go up, so a group of elements can only be raised
// to the group's largest value. The cheapest group of a given size
// to raise to a target is the elements closest to it just below it,
// which is a contiguous stretch once the array is sorted. That is
// what makes sorting first the right move, and what makes a window
// over the sorted array valid.
//
// The condition that moves left is a cost, not a count or a sum on
// its own. Raising every element in a window to the value at right
// costs nums[right] * windowSize - windowSum, and the window is
// valid while that stays within k.
//
// Growing right can only raise that cost (the array is sorted, so
// the target only gets bigger), and dropping from left can only
// lower it, so shrinking from the left is safe.
function maxFrequency(nums, k) {
const sorted = [...nums].sort((a, b) => a - b);
let left = 0;
let windowSum = 0;
let best = 1;
for (let right = 0; right < sorted.length; right++) {
windowSum += sorted[right];
while (sorted[right] * (right - left + 1) - windowSum > k) {
windowSum -= sorted[left];
left++;
}
best = Math.max(best, right - left + 1);
}
return best;
}
module.exports = { maxFrequency };
Grumpy Bookstore Owner gives the number of customers arriving each minute, and for each minute whether the owner is grumpy, in which case those customers leave unsatisfied. The owner can stay calm for minutes consecutive minutes, once, and the goal is the maximum number of satisfied customers.
Read the statement the usual way. “Maximum” is the max ask. The contiguous range is written right in the statement, minutes consecutive minutes, and its size is handed over. So this is the fixed-size shape, and unlike the last few problems there is no hidden window to find. The work here is deciding what the window should track. It takes five steps, on customers = [1, 0, 1, 2, 1, 1, 7, 5], grumpy = [0, 1, 0, 1, 0, 1, 0, 1], minutes = 3.
1. What the problem says. Each minute, some customers walk in, and the owner is either calm (0) or grumpy (1). Customers who arrive while the owner is grumpy leave unhappy. The owner can pick one stretch of 3 minutes in a row and stay calm for all of them. The goal is the most happy customers possible.
2. Start with no technique at all. Only customers arriving in calm minutes are happy. Minutes 0, 2, 4, 6 are calm, so 1 + 1 + 1 + 7 = 10. Call that the baseline. It doesn’t depend on where the stretch goes, since the technique can never make anyone unhappy.
3. What the technique actually changes. Inside the chosen stretch, a minute that was already calm stays the same, its customers were happy already. A minute that was grumpy becomes calm, so its customers flip from unhappy to happy. The gain from a stretch is therefore only the customers in grumpy minutes inside it. The total is the baseline plus the gain, so the best total comes from the stretch with the biggest gain.
4. Now it is a window question. Write out the customers in grumpy minutes, with 0 for calm minutes, [0, 0, 0, 2, 0, 1, 0, 5]. The gain of any 3-minute stretch is the sum of 3 neighbors in that list:
minutes 0-2: 0
minutes 1-3: 2
minutes 2-4: 2
minutes 3-5: 3
minutes 4-6: 1
minutes 5-7: 6 <- biggest
The best gain is 6, so the answer is 10 + 6 = 16. The window is 3 wide, given by the problem, and it asks for the largest sum, the fixed-size shape.
5. Sliding instead of re-adding. Adding 3 numbers for every stretch is the same repeated work as before. Moving the stretch by one minute changes only two things, one minute leaves and one enters. So the gain is adjusted by adding the entering minute’s customers if that minute is grumpy, and subtracting the leaving minute’s customers if that minute was grumpy. left moves when the window would be longer than minutes, the same as in Maximum Average Subarray. The window tracks only the extra, not the total, with the calm customers sitting outside it as a fixed baseline. Starting from the first window, minutes 0 to 2, with a gain of 0:
right enters leaves gain best gain
3 2 0 2 2
4 0 0 2 2
5 1 0 3 3
6 0 2 1 3
7 5 0 6 6
An entering value only counts if that minute is grumpy, and a leaving value only comes out if it was counted. The best gain is 6, the window covering minutes 5 to 7, so the answer is 10 + 6 = 16.
// Grumpy Bookstore Owner
// https://leetcode.com/problems/grumpy-bookstore-owner/description/
//
// Problem: customers[i] people enter during minute i. If grumpy[i]
// is 1, the owner is grumpy that minute and those customers leave
// unsatisfied. The owner can use a technique once, staying calm for
// `minutes` consecutive minutes. Return the maximum number of
// satisfied customers.
//
// Some customers are satisfied no matter what, the ones arriving
// while the owner is calm. That is a fixed baseline. The technique
// only changes customers arriving during grumpy minutes inside its
// window, so the gain of a window is the customers in grumpy minutes
// inside it. The window tracks only that gain, not the total.
// Fixed size, `minutes`, maximize the gain. The answer is the
// baseline plus the best gain.
function maxSatisfied(customers, grumpy, minutes) {
let baseline = 0;
for (let i = 0; i < customers.length; i++) {
if (grumpy[i] === 0) baseline += customers[i];
}
let gain = 0;
for (let i = 0; i < minutes; i++) {
if (grumpy[i] === 1) gain += customers[i];
}
let bestGain = gain;
for (let right = minutes; right < customers.length; right++) {
// The entering minute only adds to the gain if it is grumpy.
if (grumpy[right] === 1) gain += customers[right];
// The leaving minute only comes out if it was counted.
if (grumpy[right - minutes] === 1) gain -= customers[right - minutes];
bestGain = Math.max(bestGain, gain);
}
return baseline + bestGain;
}
module.exports = { maxSatisfied };