Turn a nested loop over every subarray into a single pass, by never recomputing what you already know.
The sliding window is the first pattern worth learning because it converts the most common brute force in interviews, check every subarray, from quadratic to linear. The brute force is O(n²) or O(n²·k). The window is O(n). The gap is the whole question.
Three signals put together tell you it is a window problem.
target” is a clean window problem when all values are positive. Put one negative number in the array and the window breaks, because total is no longer monotone in the window width. Always ask the interviewer whether values can be negative. Asking earns points. Assuming loses them.left and right, marking a half-open run s[left..right]. Keep alongside them a small summary of what is inside: a running sum, a character count, a number of distinct values. Move right forward to grow, move left forward to shrink. Each move updates the summary in O(1). Nothing is ever recomputed from scratch.The brute force recomputes the summary of each candidate run from its own elements, so an element is touched once per window that contains it. The window instead updates the summary incrementally: one addition when an element enters, one subtraction when it leaves.
Reading the figure. Blue cells are in the window. Red is the cell that leaves on the left. Green is the cell that enters on the right. The sum changes by two operations, however wide the window is.
The inner while loop that shrinks the window looks like it might make the algorithm quadratic. It does not, and the reason is worth being able to state cleanly in an interview.
left and right each only ever increase, and neither can exceed n. So across the whole run there are at most n increments of right and at most n increments of left, giving at most 2n pointer moves in total. Each move does O(1) work. Total: O(n), no matter how the inner loop is distributed.Put another way: every element enters the window exactly once and leaves it at most once. Two touches per element.
Every window problem has one sentence that is true at the top of each iteration. Write it as a comment. It is how you convince yourself, and the interviewer, that the code is right.
windowSum equals the sum of nums[right-k+1 .. right].nums[left..right] is valid, and no window ending at right that starts before left is valid.nums[left..right] is the shortest valid window ending at right, or no valid window ends at right.Nearly every window problem is one of these two. Learn both by heart.
public static class FixedWindowTemplate
{
/// <summary>Best value over every window of exactly k elements.</summary>
/// <param name="nums">Input numbers.</param>
/// <param name="k">Window width. Must satisfy 1 <= k <= nums.Length.</param>
/// <returns>The largest window sum.</returns>
/// <example><c>FixedWindow([2, 1, 5, 1, 3, 2], 3)</c> returns 9.</example>
public static int FixedWindow(int[] nums, int k)
{
// Pay for the first window once. Indices 0..k-1 are exactly k items.
int window = 0; // 0: the sum of an empty window
foreach (int x in nums.AsSpan(0, k)) // (0, k): start at index 0, take k items
window += x;
int best = window; // the first window is the best seen so far
// right: index of the item entering the window on this pass.
// Invariant: at the top, window == sum of nums[right - k .. right - 1].
for (int right = k; right < nums.Length; right++) // k: items 0..k-1 are summed
{
// right - k: the item k steps back is the one leaving on the left.
window += nums[right] - nums[right - k]; // add entering, drop leaving
best = Math.Max(best, window); // keep the best window so far
}
return best;
}
}
Use when the prompt names the width. There is no left variable, because left is always right - k + 1.
public static class VariableWindowTemplate
{
/// <summary>Longest window whose running sum keeps the rule.</summary>
/// <param name="items">Input numbers.</param>
/// <param name="isInvalid">Placeholder rule: true when the window broke the rule.
/// Example: <c>s => s > 7</c> means "sum above 7 is illegal".</param>
/// <returns>The length of the longest legal window.</returns>
/// <example><c>VariableWindow([2, 3, 1, 4, 2], s => s > 7)</c> returns 3.</example>
public static int VariableWindow(int[] items, Func<int, bool> isInvalid)
{
int left = 0; // 0: the window starts at the first item
int state = 0; // running summary of the window. A sum, so empty starts at 0
int best = 0; // 0: no window recorded yet
// right: index of the item that just entered.
// Invariant: at the top, items[left..right-1] is a legal window.
for (int right = 0; right < items.Length; right++) // 0: first item enters first
{
state += items[right]; // 1. grow: the item enters on the right
// Drop items from the left until the rule holds again.
while (isInvalid(state)) // 2. shrink until the window is legal again
{
state -= items[left]; // undo the leftmost item's share of state
left++; // +1: the window now starts one step right
}
// right - left + 1: window length. +1 because both ends count.
best = Math.Max(best, right - left + 1); // 3. record
}
return best;
}
}
The rule is passed in as a Func<int, bool> so the template compiles. In an interview you write the test inline. Three beats: grow, shrink, record. For a longest answer you record after the shrink loop. For a shortest answer you record inside the shrink loop, because each shrink step gives a smaller valid window.
Reading the figure. Blue cells are in the window. Amber is the cell that just entered. Red cells were dropped from the left. Green is the legal window that gets recorded. Notice that left only moves right.
best goes. Ask what the while condition means. If the loop runs while the window is illegal, the window is legal only after the loop, so record after. If the loop runs while the window is legal (you are shrinking a valid window to find the tightest one), record inside.[left, right] inclusive is right - left + 1. Say it out loud every time.left and remove items[left] from the state in the same breath, in that order: remove first, then move.list.Contains(ch) on a List<char> is O(n). It quietly makes the solution quadratic. Use a HashSet<char> or a Dictionary<char, int>.nums[left..(right + 1)].Sum() copies the range and sums it again. That throws away the whole point of the pattern.int is 32 bits and wraps silently past about 2.1 billion. If values or k are large, keep the running sum in a long.int.MaxValue. They also need a final check that a valid window was ever found.Given an array of integers nums and an integer k, return the maximum sum of any contiguous subarray of length exactly k.
n - k + 1 windows from scratch: O(n·k).public static class MaxSubarrayOfSizeK
{
/// <summary>Return the largest sum of any contiguous subarray of length k.</summary>
/// <param name="nums">Input numbers. Values may be negative.</param>
/// <param name="k">Window length. Must satisfy 1 <= k <= nums.Length.</param>
/// <returns>The maximum window sum.</returns>
/// <exception cref="ArgumentOutOfRangeException">k is outside 1..nums.Length.</exception>
/// <example><c>MaxSum([2, 1, 5, 1, 3, 2], 3)</c> returns 9.</example>
public static int MaxSum(int[] nums, int k)
{
// 1: a window needs at least one item. nums.Length: it cannot be bigger.
if (k < 1 || k > nums.Length)
throw new ArgumentOutOfRangeException(nameof(k), $"k must be in 1..{nums.Length}");
// Invariant: windowSum == sum of nums[right - k + 1 .. right] after each update.
// The +1 gives the k items that end at right.
int windowSum = 0; // 0: the sum of an empty window
for (int i = 0; i < k; i++) // i: index in the first window, 0..k-1
windowSum += nums[i];
int best = windowSum; // the first window is the best so far
// right: index of the item entering. Start at k: 0..k-1 are already summed.
for (int right = k; right < nums.Length; right++)
{
// right - k: the item k steps back slides out on the left.
windowSum += nums[right] - nums[right - k];
best = Math.Max(best, windowSum); // keep the largest window sum
}
return best;
}
}
With nums = [2, 1, 5, 1, 3, 2] and k = 3:
windowSum = 8, best = 8.right = 3. 1 enters, 2 leaves. windowSum = 7, best = 8.right = 4. 3 enters, 1 leaves. windowSum = 9, best = 9.right = 5. 2 enters, 5 leaves. windowSum = 6, best = 9.Reading the figure. Blue cells are in the window. Amber is the cell entering on the right. Red is the cell leaving on the left. The green box marks the best window seen.
k == nums.Length: there is one window. The loop body never runs, so the first sum is the answer.k > nums.Length or k < 1: undefined. Throw ArgumentOutOfRangeException rather than return a wrong number.best starts at the real first window, not at 0. Starting best = 0 is the classic bug here.int.MaxValue. Ask about the range, and switch to long if needed.k - 1 elements, so I only need the difference between them, which makes each step constant time.”Given a string s, return the length of the longest substring with no repeated characters. For "abcabcbb" the answer is 3, from "abc".
ch is already inside the window, the window is illegal. Every window starting at or before the previous occurrence of ch is also illegal, so jump left straight past it.public static class LongestSubstringNoRepeat
{
/// <summary>Length of the longest substring of s with all-distinct characters.</summary>
/// <param name="s">Input string. May be empty.</param>
/// <returns>The length of the longest run with no repeats. 0 for "".</returns>
/// <example><c>Length("pwwkew")</c> returns 3.</example>
public static int Length(string s)
{
var lastSeen = new Dictionary<char, int>(); // character -> index of its last copy
int left = 0; // first index inside the window. 0: start of s
int best = 0; // 0: right answer for an empty string
// right: index of the newest character. Invariant at the top of each pass:
// s[left..right-1] has no repeats, and best is the longest such run so far.
for (int right = 0; right < s.Length; right++) // 0: scan from the first char
{
char ch = s[right];
// Only a repeat inside the current window forces a jump.
// >= left: an older copy before left is already outside, so ignore it.
if (lastSeen.TryGetValue(ch, out int prev) && prev >= left)
left = prev + 1; // +1: start just past the old copy
lastSeen[ch] = right; // remember the newest position of ch
// +1: right - left counts gaps. Add 1 so both ends count.
best = Math.Max(best, right - left + 1);
}
return best;
}
}
>= left check mattersThe dictionary remembers characters that have already fallen out of the window. Take "abba". At right = 3 the character 'a' was last seen at index 0, but left is already 2, so 'a' is not in the window and no jump is needed. Without the guard, left would move backwards to 1 and the answer would be wrong. This one comparison is what the interviewer is watching for.
s = "abba":
right = 0, a. No jump. left = 0, window "a", best = 1.right = 1, b. No jump. left = 0, window "ab", best = 2.right = 2, b. Jump to 2. left = 2, window "b", best = 2.right = 3, a. No jump, because 0 < left. left = 2, window "ba", best = 2.Reading the figure. Blue cells are in the window. Amber is the new character. Red cells were skipped by the jump. In the last row the saved index of a is 0, which is left of left, so it must not move left back.
0. The loop never runs.1.char is one UTF-16 unit. An emoji takes two units, so it counts as two characters. Say so. If it matters, walk s.EnumerateRunes() and key on Rune.left past the previous occurrence, because every start before that point is already invalid.”Given an array of positive integers nums and a positive integer target, return the minimal length of a contiguous subarray whose sum is at least target. Return 0 if no such subarray exists.
target, the window is valid. Now shrink from the left as far as it will go while staying valid, recording the length at each step. That finds the shortest valid window ending at this right.best is updated inside the shrink loop.public static class MinSubarrayLen
{
/// <summary>Shortest contiguous subarray of nums with sum >= target.
/// Assumes every value is positive. That makes the running total grow with
/// the window width, which is what makes the shrink step valid.</summary>
/// <param name="target">Required minimum sum, positive.</param>
/// <param name="nums">Positive integers.</param>
/// <returns>The length of the shortest qualifying subarray, or 0 if none.</returns>
/// <example><c>Shortest(7, [2, 3, 1, 2, 4, 3])</c> returns 2.</example>
public static int Shortest(int target, int[] nums)
{
int left = 0; // 0: the window starts at the first item
long total = 0; // 0: sum of an empty window. long: no overflow
int best = int.MaxValue; // MaxValue: "no answer yet". Any length beats it
// right: index of the newest item. Invariant at the top of each pass:
// total == sum of nums[left..right-1] and total < target.
for (int right = 0; right < nums.Length; right++) // 0: first item enters first
{
total += nums[right]; // the item joins on the right
// The window is valid. Squeeze it from the left while it stays valid.
while (total >= target)
{
// +1: both ends count, so the length is right - left + 1.
best = Math.Min(best, right - left + 1);
total -= nums[left]; // the leftmost item leaves
left++; // +1: the window now starts one step right
}
}
// 0: the agreed answer when no window reaches target.
return best == int.MaxValue ? 0 : best;
}
}
target = 7, nums = [2, 3, 1, 2, 4, 3]:
right = 0..2. total goes 2, 5, 6. It stays below target, so no shrink. best = int.MaxValue.right = 3. total = 8. Drop 2 → 6, left = 1. best = 4.right = 4. total = 10. Drop 3 → 7, drop 1 → 6, left = 3. best = 3.right = 5. total = 9. Drop 2 → 7, drop 4 → 3, left = 5. best = 2.Reading the figure. Blue cells are in the window after the shrink. Red cells were dropped while the total stayed at least 7. Green is the answer window of length 2. Each record happens before the drop.
The answer is 2, from [4, 3].
LinkedList<int> or an int[] ring buffer. Prefix sums in a SortedSet give O(n log n). Naming the failure and the replacement is the answer they want.Array.BinarySearch to find the earliest start whose prefix is small enough. Worth mentioning as a second approach, but the window is strictly better.target: best stays int.MaxValue, so return 0.target: the shrink loop finds length 1.0.Given strings s and t, return the shortest substring of s that contains every character of t, counting repeats. Return "" if there is none. For s = "ADOBECODEBANC" and t = "ABC" the answer is "BANC".
need is a Dictionary<char, int> that starts as the counts in t. As characters enter the window it is decremented, so a value can go negative, meaning the window holds a surplus of that character.missing tracks how many required characters, counting repeats, are still unmet. The window is valid exactly when missing == 0. This is what keeps validity a O(1) test rather than a dictionary comparison.Counter with a default of zero. CollectionsMarshal.GetValueRefOrAddDefault gives a ref to the slot, adding a zero if it is missing. That is one lookup per update.using System.Runtime.InteropServices;
public static class MinWindowSubstring
{
/// <summary>Shortest substring of s containing every character of t, with repeats.</summary>
/// <param name="s">The string to search.</param>
/// <param name="t">The required characters, with multiplicity.</param>
/// <returns>The shortest qualifying substring, or "" if none exists.</returns>
/// <example><c>MinWindow("ADOBECODEBANC", "ABC")</c> returns "BANC".</example>
public static string MinWindow(string s, string t)
{
// Empty input, or t longer than s: no window can hold all of t.
if (s.Length == 0 || t.Length == 0 || t.Length > s.Length)
return "";
// need[c] > 0 means still owed. need[c] < 0 means surplus in the window.
var need = new Dictionary<char, int>();
foreach (char c in t)
CollectionsMarshal.GetValueRefOrAddDefault(need, c, out _)++; // ++: one more owed
int missing = t.Length; // required characters not yet covered
int bestStart = 0; // 0: placeholder start until a window is found
int bestLen = int.MaxValue; // MaxValue: "no window yet". Any length beats it
int left = 0; // 0: the window starts at the first char
// right: index of the newest char. Invariant at the top of each pass:
// missing > 0, so s[left..right-1] does not cover t yet.
for (int right = 0; right < s.Length; right++) // 0: scan from the first char
{
// Grow. A positive need means this character pays down a debt.
ref int owed = ref CollectionsMarshal.GetValueRefOrAddDefault(need, s[right], out _);
if (owed > 0) // > 0: t still wants a copy of this char
missing--; // -1: one fewer required char owed
owed--; // -1: the window holds one more copy
// Valid window. Shrink from the left while it stays valid.
while (missing == 0) // 0: nothing owed, so the window covers t
{
// +1: both ends count. Keep this window if it is the shortest yet.
if (right - left + 1 < bestLen)
(bestStart, bestLen) = (left, right - left + 1);
ref int back = ref CollectionsMarshal.GetValueRefOrNullRef(need, s[left]);
back++; // +1: the window hands this char back
if (back > 0) // > 0: we just gave back a char we needed
missing++; // +1: one required char is owed again
left++; // +1: the window now starts one step right
}
}
// MaxValue: no window ever covered t. Else take bestLen chars from bestStart.
return bestLen == int.MaxValue ? "" : s.Substring(bestStart, bestLen);
}
}
This is the subtle part, and the reason the code is short. Suppose t = "AB" and the window is "AAB". Then need['A'] == -1. When the leftmost 'A' leaves, need['A'] becomes 0, which is not positive, so missing stays at 0 and the window is still valid, correctly. Only when a genuinely needed character leaves does need rise above zero and missing tick back up. The sign of the counter encodes surplus versus debt for free.
s = "ADOBECODEBANC", t = "ABC". The window first becomes valid at "ADOBEC", length 6. Shrinking is blocked immediately, because dropping 'A' breaks it. Later the window "CODEBA" is valid at length 6, then "BANC" at length 4, which is the answer.
ADOBEC. Length 6. best becomes ADOBEC.CODEBA. Length 6. Not shorter, so best stays ADOBEC.BANC. Length 4. best becomes BANC.Reading the figure. Violet cells are the characters of t. Each bar is a window at the moment it becomes valid, with missing == 0. Blue bars are valid but not the best. The green bar is the answer.
need also picks up entries for characters of s that are not in t, so strictly it is O(|s| + |t|) keys in the worst case. Guarding with need.ContainsKey(ch) before touching the counter keeps it at O(|t|) and is worth a sentence if the interviewer pushes on memory.t longer than s: the early return handles it.t has repeats, such as t = "AABC": handled, because missing counts multiplicity rather than distinct characters.s == t: the whole string is the answer.bestLen stays int.MaxValue and the method returns "".missing, so checking whether the window is valid is O(1) instead of comparing two dictionaries. The counter goes negative to record surplus characters, which is what makes the shrink step correct.”left. Variable width uses Template B: grow, shrink, record.n times, so at most 2n moves in total.Pattern 2, Two Pointers, keeps the two-index idea but changes the motion: instead of both pointers walking forward, they start at opposite ends and converge. That small change unlocks sorted-array problems the window cannot touch.