Sliding Window

Problem: Given positive integers nums and target, return the length of the shortest contiguous subarray whose sum is ≥ target (0 if none).

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 1 ≤ target ≤ 10⁹ · 1 ≤ nums.length ≤ 10⁵ · 1 ≤ nums[i] ≤ 10⁴

From brute force to the pattern: Every start with every end is O(n²). Because values are positive, once a window reaches the target there's no point extending it further: shrink it from the left instead. Each index enters and leaves the window once: O(n).

Spot it: "shortest contiguous" + "sum ≥" + all positive. Adding makes the sum bigger, removing makes it smaller, so the condition is monotonic: shortest-valid window.

Key insight: as soon as the window is valid, record it and keep shrinking from the left while it stays valid. That squeezes out the shortest window ending at each right.

Approach:

1. left = 0, window_sum = 0, best_length = ∞.
2. For each right, add nums[right] to window_sum.
3. While window_sum ≥ target: record right − left + 1, subtract nums[left], then left = left + 1.
4. Return best_length, or 0 if the window never became valid.

from typing import List


class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        left = 0                          # left edge of the window
        window_sum = 0                    # sum of nums[left..right]
        best_length = float("inf")        # infinity = "no valid window found yet"

        for right in range(len(nums)):
            # Grow: bring nums[right] into the window
            window_sum = window_sum + nums[right]

            # The window is valid (sum >= target): record its length,
            # then drop nums[left] to see if a shorter window still works
            while window_sum >= target:
                window_length = right - left + 1
                if window_length < best_length:
                    best_length = window_length
                window_sum = window_sum - nums[left]
                left = left + 1

        # If no window ever reached the target, LeetCode wants 0
        if best_length == float("inf"):
            return 0
        else:
            return best_length

What the code is doing, line by line:

1. left = 0, window_sum = 0: the window starts empty at the left end. best_length = float("inf") means "nothing found yet".
2. for right in range(len(nums)): move the right edge over every index, one at a time.
3. window_sum = window_sum + nums[right]: the new number joins the window.
4. while window_sum >= target: the window is good enough. Compute window_length = right - left + 1 and keep it if it's smaller than best_length.
5. Still inside the while: subtract nums[left] and do left = left + 1. This shrinks the window from the left; the loop keeps going as long as the smaller window still reaches the target.
6. After the for loop: if best_length is still infinity, no window ever reached the target, so return 0. Otherwise return best_length.

Dry run on the example: target = 7, nums = [2, 3, 1, 2, 4, 3] → returns 2

Edge cases to test:

• No window reaches the target → 0.
• A single element ≥ target → 1.
• The whole array is needed.

Complexity: O(n) time, O(1) space.

Problem: Length of the longest substring of s with all distinct characters.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 0 ≤ s.length ≤ 10⁵ · s consists of English letters, digits, symbols and spaces.

From brute force to the pattern: Checking every substring for repeats is O(n³) (or O(n²) with a set per start). A window that only moves forward, plus a map of each character's last index, finds the longest valid substring in one pass: O(n).

Spot it: "longest substring" + a rule ("no repeats") that a shorter window can only satisfy more easily. The second visualizer above runs exactly this.

Key insight (optimised): store the last index of each character. When you see a repeat inside the window, jump left straight past the old copy instead of shrinking one step at a time.

Approach:

1. Keep last_seen[ch] = the last index where ch appeared, and left = the start of the window.
2. For each right: if s[right] was last seen at an index ≥ left, jump left to that index + 1.
3. Set last_seen[ch] = right.
4. Record right − left + 1 as a candidate.

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        last_seen = {}                    # character -> last index where we saw it
        left = 0                          # left edge of the window
        best_length = 0                   # longest window without repeats so far

        for right in range(len(s)):
            ch = s[right]
            # Have we seen ch before, and is that old copy INSIDE the window?
            if ch in last_seen:
                previous_index = last_seen[ch]
                if previous_index >= left:
                    # Jump left just past the old copy, so ch appears only once
                    left = previous_index + 1
            # Remember the newest position of ch
            last_seen[ch] = right

            # The window s[left..right] has no repeats now: measure it
            window_length = right - left + 1
            if window_length > best_length:
                best_length = window_length
        return best_length

What the code is doing, line by line:

1. last_seen is a dict: character → the last index where we saw it. left is the start of the window; best_length is the answer so far.
2. for right in range(len(s)) and ch = s[right]: look at each character in turn.
3. if ch in last_seen: we have met this character before. Read its old position into previous_index.
4. if previous_index >= left: the old copy is inside the current window, so the window now has a repeat. Jump left to previous_index + 1, just past the old copy. (If the old copy is to the left of left, it's already outside the window and we must not move left backwards: try "abba".)
5. last_seen[ch] = right: remember the newest position of ch.
6. window_length = right - left + 1: the window has no repeats now, so its length is a candidate. Keep the largest in best_length.

Dry run on the example: s = "pwwkew" → returns 3

Edge cases to test:

• Empty string → 0.
• All the same character, e.g. "bbbb" → 1.
• A repeat that's before the current window, e.g. "abba" (don't move the left edge backwards).

Complexity: O(n) time, O(min(n, σ)) space.

Problem: You may change at most k characters of uppercase string s. Return the length of the longest substring that can be made of one repeated letter.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 1 ≤ s.length ≤ 10⁵ · s consists of only uppercase English letters. · 0 ≤ k ≤ s.length

From brute force to the pattern: Trying every substring and every target letter is O(26 · n²). A sliding window with letter counts checks validity in O(1) (length − max count ≤ k), so one pass suffices: O(n).

Spot it: "longest substring" + "at most k changes". A window is fixable if window_length − count_of_most_common_letter ≤ k.

Key insight: max_freq never needs to decrease. The answer only grows when a window with a higher max_freq appears, so a stale (too high) value just keeps the window from shrinking. It never produces a wrong answer.

Approach:

1. Keep letter counts for the window and max_freq, the highest count seen so far.
2. Expand right; update its count and max_freq.
3. While window length − max_freq > k (too many letters to repaint), remove s[left] and move left.
4. Record the window length.

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        counts = {}                       # letter -> how many times it is in the window
        left = 0                          # left edge of the window
        max_freq = 0                      # biggest count of one letter seen in any window
        best_length = 0                   # answer so far

        for right in range(len(s)):
            ch = s[right]
            # Add s[right] to the window's letter counts
            if ch not in counts:
                counts[ch] = 0
            counts[ch] = counts[ch] + 1
            # Did this letter become the most common one?
            if counts[ch] > max_freq:
                max_freq = counts[ch]

            # Letters to repaint = window length - count of the most common letter.
            # If that is more than k, the window is too wide: shrink it.
            window_length = right - left + 1
            while window_length - max_freq > k:
                left_ch = s[left]
                counts[left_ch] = counts[left_ch] - 1   # s[left] leaves the window
                left = left + 1
                window_length = right - left + 1

            # The window can be fixed with at most k changes: record it
            if window_length > best_length:
                best_length = window_length
        return best_length

What the code is doing, line by line:

1. counts holds how many times each letter is in the window. max_freq is the biggest single-letter count we have seen.
2. For each right: add s[right] to counts (create the key with 0 first if needed), and if its count beats max_freq, update max_freq.
3. window_length - max_freq is how many letters we would have to repaint so the whole window is the most common letter.
4. while window_length - max_freq > k: too many repaints needed. Take s[left] out of counts, move left forward, and recompute window_length.
5. We never lower max_freq when letters leave. That's on purpose: the answer can only get bigger when some window has a higher max_freq, so an old (too high) value never gives a wrong answer.
6. After shrinking, the window can be fixed with at most k changes, so compare window_length with best_length.

Dry run on the example: s = "AABABBA", k = 1 → returns 4

Edge cases to test:

• k large enough to change everything → the whole length.
• k = 0 → the longest run of one letter.
• A single character.

Complexity: O(n) time, O(26) space.

Problem: Return every start index in s where a substring is an anagram (same letters, any order) of p.

Solve it on LeetCode ↗

Constraints: 1 ≤ s.length, p.length ≤ 3 * 10⁴ · s and p consist of lowercase English letters.

From brute force to the pattern: Sorting or counting every window from scratch is O(n · m). A fixed window whose counts are updated incrementally compares in O(26), so O(n) overall.

Spot it: an anagram of p has length len(p), so this is a fixed-size window. Compare letter counts.

Approach:

1. If p is longer than s, return [].
2. Count the letters of p into a dict need; have will hold the counts of the current window of s.
3. Slide one step at a time: add the new letter; once the window is longer than len(p), remove the one falling out (deleting zero counts).
4. Whenever have == need, record the window's start index.

from typing import List


class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        window_size = len(p)              # an anagram of p has exactly len(p) letters
        result = []
        if window_size > len(s):
            return result                 # s is too short to hold an anagram of p

        # need: letter -> how many times it appears in p
        need = {}
        for ch in p:
            if ch not in need:
                need[ch] = 0
            need[ch] = need[ch] + 1

        # have: letter -> how many times it appears in the current window of s
        have = {}
        for right in range(len(s)):
            # One letter slides IN on the right
            entering = s[right]
            if entering not in have:
                have[entering] = 0
            have[entering] = have[entering] + 1

            # Once the window would be too big, one letter slides OUT on the left
            if right >= window_size:
                leaving = s[right - window_size]
                have[leaving] = have[leaving] - 1
                if have[leaving] == 0:
                    # Delete zero counts so "have == need" compares fairly
                    del have[leaving]

            # Same letters with the same counts = anagram; remember where it starts
            if have == need:
                start = right - window_size + 1
                result.append(start)
        return result

What the code is doing, line by line:

1. window_size = len(p): an anagram of p always has exactly that many letters. If s is shorter than p, return the empty result right away.
2. The first loop fills need: letter → how many times it appears in p.
3. have will hold the letter counts of the current window of s. For each right, the letter s[right] slides in and its count goes up by 1.
4. if right >= window_size: the window would now be one letter too long, so the letter at right - window_size slides out and its count goes down by 1. If that count hits 0 we del the key, otherwise {'a': 1, 'b': 0} would not equal {'a': 1}.
5. if have == need: same letters with the same counts means the window is an anagram. It covers s[right - window_size + 1 .. right], so append that start index to result.
6. (During the first window_size - 1 steps the window is still too short to match, which is fine.)

Dry run on the example: s = "cbaebabacd", p = "abc", so need = {'a': 1, 'b': 1, 'c': 1} → returns [0, 6]

Edge cases to test:

• p longer than s → [].
• Overlapping matches, e.g. s = "abab", p = "ab" → [0, 1, 2].
• Repeated letters in p.

Complexity: O(n · 26) = O(n) time, O(26) space.

Problem: Return the shortest substring of s containing every character of t (with multiplicity). Return "" if none.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: m == s.length · n == t.length · 1 ≤ m, n ≤ 10⁵ · s and t consist of uppercase and lowercase English letters.

From brute force to the pattern: Checking every substring for containing t is O(n² · m). A variable window that expands until valid and then shrinks greedily visits each index at most twice: O(n + m).

Spot it: "minimum window" + "contains all of". Adding characters can only help coverage, so it's a shortest-valid window.

Key insight: keep need[c] = how many more of c the window still needs (can go negative for extras), and a single integer missing so the validity check is O(1).

Approach:

1. Count the letters of t into a dict need; set missing = len(t).
2. Expand right: if need[ch] > 0 the character was useful, so missing goes down by 1. Always lower need[ch] by 1.
3. While missing == 0 (the window covers t): record it if it's the shortest so far, give back s[left] (its need goes up by 1), and if that count turned positive, missing goes up by 1. Move left.
4. Return the best slice, or "".

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        # need[ch] = how many more copies of ch the window still needs.
        # It can drop below zero when the window holds extra copies.
        need = {}
        for ch in t:
            if ch not in need:
                need[ch] = 0
            need[ch] = need[ch] + 1
        missing = len(t)                  # characters of t not yet covered by the window
        left = 0                          # left edge of the window
        best_left = 0                     # best window found so far is s[best_left..best_right]
        best_right = -1                   # -1 means "no valid window found yet"

        for right in range(len(s)):
            ch = s[right]
            if ch not in need:
                need[ch] = 0              # a letter t does not contain starts at 0
            if need[ch] > 0:
                missing = missing - 1     # this copy was really needed
            need[ch] = need[ch] - 1       # the window now holds one more ch

            # Every character of t is covered: shrink while that stays true
            while missing == 0:
                window_length = right - left + 1
                best_length = best_right - best_left + 1
                if best_right == -1 or window_length < best_length:
                    best_left = left      # new shortest window: remember it
                    best_right = right
                left_ch = s[left]
                need[left_ch] = need[left_ch] + 1   # give s[left] back
                if need[left_ch] > 0:
                    missing = missing + 1 # we just lost a character we needed
                left = left + 1

        # Slicing with best_right = -1 gives "" (nothing found)
        return s[best_left:best_right + 1]

What the code is doing, line by line:

1. Build need from t: letter → how many copies we still need. missing = len(t) counts how many characters of t are not yet covered.
2. best_left = 0, best_right = -1: the best window is s[best_left..best_right]; -1 means nothing found yet.
3. For each right: if ch is a letter t doesn't have, give it a count of 0 so the dict lookups work.
4. if need[ch] > 0: we still needed this letter, so one fewer character is missing. Then need[ch] = need[ch] - 1 in every case (extra copies push the count below 0).
5. while missing == 0: the window contains all of t. If it's the first valid window or shorter than the best one, save left and right as the new best.
6. Still in the while: give s[left] back (need[left_ch] + 1). If its count turned positive, we just lost a character we really needed, so missing goes up and the loop will stop. Move left forward.
7. Finally return the slice s[best_left:best_right + 1]. If nothing was found, best_right is -1 and the slice s[0:0] is the empty string.

Dry run on the example: s = "ADOBECODEBANC", t = "ABC" → returns "BANC"

Edge cases to test:

• t longer than s → "".
• Duplicate letters in t, e.g. t = "aa".
• The answer is the whole of s.

Complexity: O(|s| + |t|) time, O(σ) space.

Problem: For every window of size k, report its maximum.

Solve it on LeetCode ↗

Constraints: 1 ≤ nums.length ≤ 10⁵ · -10⁴ ≤ nums[i] ≤ 10⁴ · 1 ≤ k ≤ nums.length

From brute force to the pattern: Taking max of every window is O(n · k). A monotonic deque keeps only candidates that could still become a maximum; each index is added and removed once, so O(n).

Spot it: fixed-size window, but "max" can't be undone by subtraction. Keep a monotonic deque of indices whose values decrease front→back; the front is the window max.

Key insight: when a bigger value arrives, everything smaller behind it can never be a maximum again (it's older and smaller), so pop it.

Approach:

1. Keep a deque of indices whose values decrease from front to back.
2. For each i: pop from the back while the back's value ≤ nums[i], then push i.
3. If the front index has slid out of the window (≤ i − k), pop it from the front.
4. Once i ≥ k − 1, the front holds the window maximum; append it.

from collections import deque
from typing import List


class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        # A deque ("double-ended queue") is a list that is fast at BOTH ends:
        # append() adds on the right, pop() removes from the right,
        # popleft() removes from the left.
        # Here it stores INDICES whose values get smaller from front to back,
        # so the front index always points at the current window's maximum.
        window_indices = deque()
        result = []

        for i in range(len(nums)):
            value = nums[i]
            # Throw away indices from the back whose values are <= value:
            # they are older AND not bigger, so they can never be a maximum again
            while len(window_indices) > 0 and nums[window_indices[-1]] <= value:
                window_indices.pop()
            window_indices.append(i)

            # The window is nums[i - k + 1 .. i]; if the front index is
            # older than that, it has slid out, so remove it
            if window_indices[0] <= i - k:
                window_indices.popleft()

            # From the first full window onwards, record the maximum (the front)
            if i >= k - 1:
                result.append(nums[window_indices[0]])
        return result

What the code is doing, line by line:

1. from collections import deque: a deque ("deck", double-ended queue) behaves like a list but adding/removing at both ends is fast. We use append() and pop() on the right end and popleft() on the left end.
2. window_indices stores indices (not values), ordered so their values get smaller from front to back. So nums[window_indices[0]] is always the biggest value in the window.
3. For each i: while the value at the back is <= value, pop it. Those numbers are older and not bigger than the new one, so they can never be a window maximum again.
4. window_indices.append(i): the new index joins at the back.
5. if window_indices[0] <= i - k: the window is nums[i - k + 1 .. i]; an index at or before i - k has slid out, so remove it from the front.
6. if i >= k - 1: from index k - 1 on, a full window exists, so append its maximum nums[window_indices[0]] to result.

Dry run on the example: nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3 → returns [3, 3, 5, 5, 6, 7]

Edge cases to test:

• k = 1 → the array itself.
• k = n → one value, the overall maximum.
• Decreasing input, so the deque grows to size k.

Complexity: O(n) time (each index pushed and popped once), O(k) space.

Problem: Find the largest average of any contiguous subarray of length exactly k.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: n == nums.length · 1 ≤ k ≤ n ≤ 10⁵ · -10⁴ ≤ nums[i] ≤ 10⁴

From brute force to the pattern: Summing each window from scratch is O(n · k). Updating the sum incrementally makes each slide O(1): O(n).

Spot it: "Length exactly k" → fixed-size window.

Approach:

1. Sum the first k numbers.
2. Slide: add nums[right], subtract nums[right − k].
3. Track the maximum window sum.
4. Return max / k (one division at the end).

from typing import List


class Solution:
    def findMaxAverage(self, nums: List[int], k: int) -> float:
        # Sum of the first window nums[0..k-1]
        window_sum = 0
        for i in range(k):
            window_sum = window_sum + nums[i]
        best_sum = window_sum

        # Slide: nums[right] comes in, nums[right - k] goes out
        for right in range(k, len(nums)):
            window_sum = window_sum + nums[right] - nums[right - k]
            if window_sum > best_sum:
                best_sum = window_sum

        # All windows have the same size k, so the biggest sum
        # is also the biggest average: divide only once at the end
        return best_sum / k

What the code is doing, line by line:

1. The first loop adds up nums[0] … nums[k-1] into window_sum; that's the first window, and also the best so far.
2. for right in range(k, len(nums)): nums[right] slides in, nums[right - k] slides out. One addition and one subtraction update the sum.
3. if window_sum > best_sum: remember the largest window sum.
4. return best_sum / k: every window has the same size, so the largest sum is also the largest average. We divide only once, at the end.

Dry run on the example: nums = [1, 12, -5, -6, 50, 3], k = 4 → returns 12.75 (= 51 / 4)

Edge cases to test:

• k = n → the average of everything.
• All negative numbers (start the best at the first window, not 0).
• k = 1 → the maximum element.

Complexity: O(n) time, O(1) space.

Problem: A binary array; you may flip at most k zeros into ones. What's the longest run of ones you can get?

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 1 ≤ nums.length ≤ 10⁵ · nums[i] is either 0 or 1. · 0 ≤ k ≤ nums.length

From brute force to the pattern: Trying every subarray and counting its zeros is O(n²). A window that tracks its zero count moves each edge forward only, giving O(n).

Spot it: Longest contiguous + "at most k" → variable window whose rule is "at most k zeros inside".

Approach:

1. Count the zeros inside the window.
2. Expand right; if nums[right] is 0, add 1 to zeros_in_window.
3. While zeros_in_window > k, shrink from the left (subtract 1 when a 0 leaves).
4. Record the window length.

from typing import List


class Solution:
    def longestOnes(self, nums: List[int], k: int) -> int:
        left = 0                          # left edge of the window
        zeros_in_window = 0               # zeros we would have to flip
        best_length = 0

        for right in range(len(nums)):
            # Bring nums[right] in; count it if it is a zero
            if nums[right] == 0:
                zeros_in_window = zeros_in_window + 1

            # More than k zeros: we cannot flip them all, so shrink from the left
            while zeros_in_window > k:
                if nums[left] == 0:
                    zeros_in_window = zeros_in_window - 1
                left = left + 1

            # The window has at most k zeros: all of it can become ones
            window_length = right - left + 1
            if window_length > best_length:
                best_length = window_length
        return best_length

What the code is doing, line by line:

1. zeros_in_window counts the zeros inside nums[left..right]; those are the ones we would have to flip.
2. For each right: if the new number is 0, add 1 to zeros_in_window.
3. while zeros_in_window > k: we can't flip that many. Move left forward; whenever the number leaving is a 0, subtract 1 from zeros_in_window.
4. After the loop the window has at most k zeros, so all of it can become ones: compare right - left + 1 with best_length.

Dry run on the example: nums = [1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0], k = 2 → returns 6

Edge cases to test:

• k = 0 → the longest run of 1s.
• k ≥ number of zeros → n.
• All zeros.

Complexity: O(n) time, O(1) space.

Problem: Does s2 contain a substring that's a rearrangement (permutation) of s1?

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 1 ≤ s1.length, s2.length ≤ 10⁴ · s1 and s2 consist of lowercase English letters.

From brute force to the pattern: Generating all permutations of s1 is factorial; sorting every window is O(n · m log m). A fixed-size window with 26 counts checks each position in O(1) (or O(26)): O(n).

Spot it: A permutation of s1 has exactly len(s1) letters → fixed window comparing letter counts.

Approach:

1. Count the letters of s1 into need[26].
2. Slide a window of size len(s1) over s2, keeping have[26] up to date (one in, one out).
3. After each step, compare have == need.
4. Return True on the first match, otherwise False.

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        window_size = len(s1)             # a permutation of s1 has exactly len(s1) letters
        if window_size > len(s2):
            return False

        # Two lists of 26 counters, one slot per letter: slot 0 = 'a', slot 25 = 'z'
        need = [0] * 26
        have = [0] * 26
        for ch in s1:
            letter_index = ord(ch) - ord("a")
            need[letter_index] = need[letter_index] + 1

        for right in range(len(s2)):
            # One letter slides IN on the right
            entering_index = ord(s2[right]) - ord("a")
            have[entering_index] = have[entering_index] + 1

            # Keep the window at most window_size long: one letter slides OUT
            if right >= window_size:
                leaving_index = ord(s2[right - window_size]) - ord("a")
                have[leaving_index] = have[leaving_index] - 1

            # Comparing two lists of 26 numbers is a constant amount of work
            if have == need:
                return True
        return False

What the code is doing, line by line:

1. window_size = len(s1); if s1 is longer than s2, no permutation can fit, so return False.
2. need and have are lists of 26 counters, one per letter. ord(ch) - ord("a") turns a letter into its slot number: 'a' → 0, 'b' → 1, … 'z' → 25.
3. The first loop counts the letters of s1 into need.
4. For each right in s2: the letter at right slides in (its slot goes up by 1).
5. if right >= window_size: the letter at right - window_size slides out (its slot goes down by 1), so the window never has more than window_size letters.
6. if have == need: Python compares the two lists slot by slot. Equal means the window is a permutation of s1, so return True immediately. If the loop finishes, return False.

Dry run on the example: s1 = "ab", s2 = "eidbaooo", so need holds a: 1, b: 1 → returns True

Edge cases to test:

• s1 longer than s2 → False.
• The match at the very end of s2.
• Repeated letters.

Complexity: O(26·n) = O(n) time, O(1) space.

Problem: Walk along a row of trees, taking one fruit per tree. You have two baskets, each holding one fruit type. The most fruit you can collect = the longest subarray with at most 2 distinct values.

Solve it on LeetCode ↗

Constraints: 1 ≤ fruits.length ≤ 10⁵ · 0 ≤ fruits[i] < fruits.length

From brute force to the pattern: Every subarray with a distinct-count check is O(n²). A window with a count map of at most three keys moves each edge forward only: O(n).

Spot it: Longest contiguous + "at most 2 distinct" → variable window with a count map.

Approach:

1. basket maps fruit type → how many are in the window.
2. Expand right and add its fruit.
3. While there are more than 2 types, remove fruits[left] (delete the key when it hits 0) and move left.
4. Record the window length.

from typing import List


class Solution:
    def totalFruit(self, fruits: List[int]) -> int:
        basket = {}                       # fruit type -> how many of it are in the window
        left = 0                          # left edge of the window
        best_length = 0

        for right in range(len(fruits)):
            # Pick the fruit at position right
            fruit = fruits[right]
            if fruit not in basket:
                basket[fruit] = 0
            basket[fruit] = basket[fruit] + 1

            # Three types but only two baskets: give back fruit from the left
            while len(basket) > 2:
                left_fruit = fruits[left]
                basket[left_fruit] = basket[left_fruit] - 1
                if basket[left_fruit] == 0:
                    del basket[left_fruit]    # that type has fully left the window
                left = left + 1

            # At most 2 types now: record how many fruits we hold
            window_length = right - left + 1
            if window_length > best_length:
                best_length = window_length
        return best_length

What the code is doing, line by line:

1. basket maps fruit type → how many fruits of that type are in the window. Its number of keys, len(basket), is how many types we're carrying.
2. For each right: add fruits[right] to the basket (create the key with 0 first if it's a new type).
3. while len(basket) > 2: three types but only two baskets. Give back the fruit at left (count minus 1), delete the type entirely when its count reaches 0, and move left forward.
4. After shrinking we hold at most 2 types, so right - left + 1 fruits is a valid amount; keep the largest in best_length.

Dry run on the example: fruits = [1, 2, 3, 2, 2] → returns 4

Edge cases to test:

• One fruit type only → n.
• Alternating types, e.g. [1, 2, 1, 2] → 4.
• Fewer than 3 elements.

Complexity: O(n) time, O(1) space (at most 3 keys).

Problem: Each operation removes the leftmost or rightmost number and subtracts it from x. What's the minimum number of operations to make x exactly 0 (or −1 if impossible)?

Solve it on LeetCode ↗

Constraints: 1 ≤ nums.length ≤ 10⁵ · 1 ≤ nums[i] ≤ 10⁴ · 1 ≤ x ≤ 10⁹

From brute force to the pattern: Trying every split between the left and right removals is O(n²). Inverting the problem (maximise the kept middle with sum total − x) makes it a positive-number sliding window: O(n).

Spot it: Removing from both ends is awkward. Flip it: what remains is a contiguous middle that sums to total − x. Fewest removals = longest such middle. All values are positive → sliding window.

Approach:

1. goal = sum(nums) − x. If goal < 0 return −1; if goal == 0 return n.
2. Expand right; while the window sum exceeds goal, shrink from the left.
3. If the window sum equals goal, record its length.
4. Answer = n − longest, or −1 if no window was found.

from typing import List


class Solution:
    def minOperations(self, nums: List[int], x: int) -> int:
        # Add up all the numbers
        total = 0
        for i in range(len(nums)):
            total = total + nums[i]

        # The untouched middle part must add up to goal
        goal = total - x
        if goal < 0:
            return -1                     # even removing everything is not enough
        if goal == 0:
            return len(nums)              # we must remove every number

        left = 0                          # left edge of the middle window
        window_sum = 0                    # sum of nums[left..right]
        longest = -1                      # longest middle with sum == goal (-1 = none yet)

        for right in range(len(nums)):
            window_sum = window_sum + nums[right]
            # All numbers are positive, so removing from the left lowers the sum
            while window_sum > goal:
                window_sum = window_sum - nums[left]
                left = left + 1
            if window_sum == goal:
                window_length = right - left + 1
                if window_length > longest:
                    longest = window_length

        # Fewest removals = everything except the longest middle
        if longest == -1:
            return -1
        else:
            return len(nums) - longest

What the code is doing, line by line:

1. The first loop adds up every number into total.
2. Removing numbers from the two ends always leaves a contiguous middle part. The removed numbers must add up to x, so the middle must add up to goal = total - x.
3. goal < 0: even removing everything isn't enough, return -1. goal == 0: we must remove every number, return len(nums).
4. Now find the longest middle window with sum exactly goal. For each right, add nums[right]; while window_sum > goal, subtract nums[left] and move left (all numbers are positive, so this lowers the sum).
5. if window_sum == goal: this middle works; keep its length in longest if it's the biggest so far.
6. At the end: if longest is still -1 nothing worked, return -1. Otherwise the fewest operations is everything outside the middle: len(nums) - longest.

Dry run on the example: nums = [3, 2, 20, 1, 1, 3], x = 10: total = 30, goal = 20 → returns 5 (= 6 − 1)

Edge cases to test:

• x == total → remove everything (n).
• x > total → −1.
• No valid middle exists → −1.

Complexity: O(n) time, O(1) space.

Problem: Count the subarrays that contain exactly k distinct integers.

Solve it on LeetCode ↗

Constraints: 1 ≤ nums.length ≤ 2 * 10⁴ · 1 ≤ nums[i], k ≤ nums.length

From brute force to the pattern: Counting distinct values in every subarray is O(n²). The at-most trick turns it into two linear sliding-window passes: O(n).

Spot it: "Exactly k" is not monotonic (growing a window can make it valid, then invalid), but "at most k" is. Use exactly(k) = atMost(k) − atMost(k − 1).

Key insight: In an at-most window [left, right], every subarray that ends at right and starts anywhere in [left, right] is also valid: that's right − left + 1 subarrays.

Approach:

1. Write a helper at_most(nums, max_distinct): a variable window that keeps ≤ max_distinct distinct values (a dict of counts; shrink while it has too many keys).
2. After shrinking for each right, add right − left + 1 to the total.
3. Return at_most(nums, k) − at_most(nums, k − 1).

from typing import List


class Solution:
    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:
        # "exactly k" = "at most k" minus "at most k - 1"
        at_most_k = self.at_most(nums, k)
        at_most_k_minus_1 = self.at_most(nums, k - 1)
        return at_most_k - at_most_k_minus_1

    def at_most(self, nums: List[int], max_distinct: int) -> int:
        # Counts subarrays that contain at most max_distinct different values
        counts = {}                       # value -> how many times it is in the window
        left = 0
        total = 0
        for right in range(len(nums)):
            value = nums[right]
            if value not in counts:
                counts[value] = 0
            counts[value] = counts[value] + 1

            # Too many different values: shrink from the left
            while len(counts) > max_distinct:
                left_value = nums[left]
                counts[left_value] = counts[left_value] - 1
                if counts[left_value] == 0:
                    del counts[left_value]
                left = left + 1

            # Every subarray that ends at right and starts anywhere in
            # [left, right] is valid: that is right - left + 1 subarrays
            total = total + (right - left + 1)
        return total

What the code is doing, line by line:

1. subarraysWithKDistinct calls the helper twice: subarrays with at most k distinct values, minus those with at most k - 1. What's left is exactly k.
2. at_most(nums, max_distinct) is a normal longest-valid window. counts maps value → how many times it's in the window, so len(counts) is the number of distinct values.
3. For each right: add nums[right] to counts.
4. while len(counts) > max_distinct: too many distinct values. Remove nums[left] (delete the key when its count reaches 0) and move left.
5. total = total + (right - left + 1): every subarray that ends at right and starts anywhere from left to right is valid. There are right - left + 1 of them, and each is counted exactly once (at its end index).
6. When max_distinct is 0, the window is always shrunk to empty and adds 0, so at_most(nums, 0) correctly returns 0.

Dry run on the example: nums = [1, 2, 1, 2, 3], k = 2: at_most(2) = 12, at_most(1) = 5, so it returns 12 − 5 = 7

Edge cases to test:

• k = 1 → count runs of equal values.
• k larger than the number of distinct values → 0.
• All elements the same.

Complexity: O(n) time, O(n) space for the counts.

Problem: prices[i] is a stock's price on day i. Choose one day to buy and a later day to sell. Return the maximum profit, or 0 if no profit is possible.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 1 ≤ prices.length ≤ 10⁵ · 0 ≤ prices[i] ≤ 10⁴

From brute force to the pattern: Trying every buy day with every later sell day is O(n²). The best buy for any sell day is simply the minimum so far, which a single variable tracks: O(n).

Spot it: A pair (buy, sell) with buy < sell that maximises prices[sell] − prices[buy]. Think of it as a window: sell scans forward, and buy stays on the cheapest day seen so far.

Key insight: If today's price is lower than the current buy price, any future sale is better from today, so the left edge of the window jumps here. Otherwise, today is a candidate sell day.

Approach:

1. buy = 0, best = 0.
2. For each later day sell: if prices[sell] < prices[buy], move buy to sell (a new, cheaper starting point).
3. Otherwise compute the profit prices[sell] − prices[buy] and keep the maximum.

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        buy = 0      # day of the cheapest price seen so far (left edge of the window)
        best = 0     # no transaction at all gives 0 profit
        for sell in range(1, len(prices)):
            if prices[sell] < prices[buy]:
                # a cheaper day: every later sale is better from here
                buy = sell
            else:
                profit = prices[sell] - prices[buy]
                best = max(best, profit)
        return best

What the code is doing, line by line:

1. buy = 0: the left edge of the window, always the cheapest day so far.
2. best = 0: if prices only fall, we simply don't trade.
3. for sell in range(1, len(prices)): the right edge walks forward one day at a time.
4. if prices[sell] < prices[buy]: buy = sell: today is cheaper than our buy day, so restart the window here.
5. else: today could be a sell day: compute the profit and keep the best.

Dry run on the example:

prices = [7, 1, 5, 3, 6, 4] (LeetCode Example 1). Returns 5 (buy at 1, sell at 6).

Edge cases to test:

• Prices only fall → 0.
• A single day → 0.
• The minimum comes after the maximum, e.g. [3, 5, 1] → 2 (not 4).

Complexity: O(n) time, O(1) space.

Problem: Return True if there are two indices i ≠ j with nums[i] == nums[j] and |i − j| ≤ k.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 1 ≤ nums.length ≤ 10⁵ · -10⁹ ≤ nums[i] ≤ 10⁹ · 0 ≤ k ≤ 10⁵

From brute force to the pattern: Comparing every pair within distance k is O(n · k). A set holding just the current window answers "seen recently?" in O(1): O(n).

Spot it: "Within distance k" = within a window of the last k elements. Keep those values in a set: a value already in the set is a close duplicate.

Approach:

1. Walk the array. The set window holds the values of the previous k positions.
2. If nums[i] is already in window, a duplicate within distance k exists: return True.
3. Add nums[i]. If the window now holds more than k values, remove the one that just fell out, nums[i − k].
4. If the loop ends, no close duplicate exists.

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        # the values of the last k positions
        window = set()
        for i in range(len(nums)):
            if nums[i] in window:
                # the same value appeared at most k positions ago
                return True
            window.add(nums[i])
            if len(window) > k:
                # nums[i - k] is now too far away to pair with anything ahead
                window.remove(nums[i - k])
        return False

What the code is doing, line by line:

1. window = set(): at most k values, the ones close enough to pair with the current position.
2. if nums[i] in window: return True: an O(1) set lookup finds a duplicate within distance k.
3. window.add(nums[i]): the current value joins the window for the positions that follow.
4. if len(window) > k: window.remove(nums[i - k]): keep the window at k values. The window never holds a duplicate (we would have returned), so its size equals the number of positions it covers.
5. return False: no pair was close enough.

Dry run on the example:

nums = [1, 2, 3, 1, 2, 3], k = 2 (LeetCode Example 3). Returns False: equal values are always 3 apart.

The loop ends without a hit, so the answer is False. With nums = [1, 2, 3, 1], k = 3 the second 1 would find the first one still in the window.

Edge cases to test:

• k = 0 → always False.
• The duplicate exactly k apart → True.
• Duplicates only further apart than k → False.

Complexity: O(n) time, O(k) space.

Problem: words are all the same length. Return every starting index in s of a substring that is some concatenation of all the words, each used exactly as many times as it appears in words (any order).

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 1 ≤ s.length ≤ 10⁴ · 1 ≤ words.length ≤ 5000 · 1 ≤ words[i].length ≤ 30 · s and words[i] consist of lowercase English letters.

From brute force to the pattern: Checking every start index by slicing len(words) words and comparing counts is O(n · m · L). A word-sized sliding window per offset reuses the counts as it moves, so each word slice is handled a constant number of times: O(n · L).

Spot it: "Contiguous substring" + "contains exactly these counts" → a variable sliding window with a count map, like Minimum Window Substring. The twist: the window's unit is a whole word of length L, so it moves in jumps of L.

Key insight: A match can start at any index, but jumping by L only visits indices with the same remainder mod L. So run the word-sized window L times, once for each offset 0 .. L − 1. Each run is linear.

Approach:

1. Count how many times each word is needed (need).
2. For each offset 0 .. L − 1: start an empty window at left = offset and read words at right = offset, offset + L, ….
3. If the word is not in need, no answer can include it. Clear the window and restart just after it.
4. Otherwise add it to seen. If that word now appears too often, drop words from the left until it doesn't.
5. If the window holds exactly len(words) words, record left, then drop one word from the left to keep searching.

class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        word_len = len(words[0])
        total_words = len(words)
        # how many copies of each word a valid window must contain
        need = {}
        for w in words:
            need[w] = need.get(w, 0) + 1
        result = []
        # the window jumps a whole word at a time, so try every starting offset
        for offset in range(word_len):
            left = offset
            seen = {}    # word counts inside the current window
            count = 0    # number of words in the current window
            for right in range(offset, len(s) - word_len + 1, word_len):
                word = s[right:right + word_len]
                if word not in need:
                    # this word can never be part of an answer: restart after it
                    seen = {}
                    count = 0
                    left = right + word_len
                    continue
                seen[word] = seen.get(word, 0) + 1
                count = count + 1
                # too many copies of this word: shrink from the left until it fits again
                while seen[word] > need[word]:
                    left_word = s[left:left + word_len]
                    seen[left_word] = seen[left_word] - 1
                    count = count - 1
                    left = left + word_len
                if count == total_words:
                    # every word is present the right number of times
                    result.append(left)
                    # drop the leftmost word and keep sliding
                    left_word = s[left:left + word_len]
                    seen[left_word] = seen[left_word] - 1
                    count = count - 1
                    left = left + word_len
        return result

What the code is doing, line by line:

1. need: a count map of the words, e.g. {"foo": 1, "bar": 1}. Words can repeat, so this must be a count, not a set.
2. for offset in range(word_len): answers can start at any index, but one pass of jumps only reaches indices with the same remainder. word_len passes cover them all.
3. for right in range(offset, len(s) - word_len + 1, word_len): right is the start of the next word to bring into the window.
4. if word not in need: a foreign word poisons every window containing it, so reset and start the window after it.
5. seen[word] = seen.get(word, 0) + 1, count = count + 1: grow the window by one word.
6. while seen[word] > need[word]: the new word appears too often; remove words from the left (updating seen and count) until it fits.
7. if count == total_words: the window is a full concatenation: record its start, then drop its first word so the search continues.

Dry run on the example:

s = "barfoothefoobarman", words = ["foo", "bar"] (LeetCode Example 1). word_len = 3. Returns [0, 9]. Offset 0 finds both answers; offsets 1 and 2 find nothing.

Edge cases to test:

• Repeated words in words, e.g. ["foo", "foo"].
• A foreign word in the middle resets the window.
• s shorter than all the words together → [].

Complexity: O(n · L) time: L offsets, each scanning about n / L words, and slicing a word costs O(L). O(m) space for the two maps, where m is the number of words.

Problem: Return the length of the longest substring in which every character appears at least k times.

Solve it on LeetCode ↗

Constraints: 1 ≤ s.length ≤ 10⁴ · s consists of only lowercase English letters. · 1 ≤ k ≤ 10⁵

From brute force to the pattern: Checking every substring is O(n²). Fixing the number of distinct letters makes the window monotonic, giving 26 linear passes.

Spot it: A plain window fails: adding a character can make the window invalid or valid, so it's not monotonic. Fixing the number of distinct letters t restores monotonicity: for each t in 1..26, keep a window with at most t distinct letters and check whether all of them reach k.

Why not another pattern? Divide and conquer also works: any character with total count < k can't be in the answer, so split the string around it and recurse (O(26 · n) too). Checking every substring is O(n²).

Approach:

1. For each target from 1 to 26 (number of distinct letters allowed):
2. Slide a window: add s[right]; while the window has more than target distinct letters, shrink from the left.
3. Track distinct and at_least_k (letters whose count reached k). If both equal target, the window is valid.
4. Keep the longest valid window over all targets.

class Solution:
    def longestSubstring(self, s: str, k: int) -> int:
        best = 0
        for target in range(1, 27):  # exactly `target` distinct letters in the window
            count = [0] * 26
            distinct = 0  # letters present in the window
            at_least_k = 0  # letters present at least k times
            left = 0
            for right in range(len(s)):
                c = ord(s[right]) - ord("a")
                if count[c] == 0:
                    distinct = distinct + 1
                count[c] = count[c] + 1
                if count[c] == k:
                    at_least_k = at_least_k + 1
                while distinct > target:  # too many letters: shrink
                    d = ord(s[left]) - ord("a")
                    if count[d] == k:
                        at_least_k = at_least_k - 1
                    count[d] = count[d] - 1
                    if count[d] == 0:
                        distinct = distinct - 1
                    left = left + 1
                if distinct == target and at_least_k == target:
                    best = max(best, right - left + 1)  # every letter appears >= k times
        return best

What the code is doing, line by line:

1. The outer loop fixes how many different letters the window may contain; with that fixed, "too many letters" is a monotonic condition again.
2. distinct and at_least_k are updated exactly when a count crosses 0 or k, so both stay O(1) per step.
3. The inner while restores "at most target distinct letters" by shrinking from the left.
4. A window is valid when it has exactly target letters and all of them reached k.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• k = 1 → the whole string.
• k larger than the string → 0.
• A letter that appears fewer than k times splits the string.

Complexity: O(26 · n) time, O(1) space.

Problem: Count the contiguous subarrays of length ≥ 3 whose consecutive differences are all equal.

Solve it on LeetCode ↗

Constraints: 1 ≤ nums.length ≤ 5000 · -1000 ≤ nums[i] ≤ 1000

From brute force to the pattern: Testing every subarray is O(n²). A run of length L contains (L−1)(L−2)/2 slices, and counting them incrementally as the run grows takes one pass.

Spot it: Arithmetic slices live inside maximal runs with a constant difference. Extending a run by one element creates new slices that end at that element: a window that grows while the difference stays the same.

Why not another pattern? Checking every subarray is O(n²) (or O(n³) naively). This is also a tiny DP: dp[i] = dp[i − 1] + 1 when the difference repeats.

Approach:

1. current = number of arithmetic slices ending at the current index.
2. If nums[i] − nums[i−1] == nums[i−1] − nums[i−2], every slice ending at i − 1 extends, plus one new length-3 slice: current += 1.
3. Otherwise the run breaks: current = 0. Add current to the total each step.

class Solution:
    def numberOfArithmeticSlices(self, nums: List[int]) -> int:
        total = 0
        current = 0  # arithmetic slices ending at index i
        for i in range(2, len(nums)):
            if nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]:
                current = current + 1  # the run grows: one more slice ends here than before
            else:
                current = 0  # the difference changed: the run is broken
            total = total + current
        return total

What the code is doing, line by line:

1. Start at index 2: a slice needs three elements.
2. Same difference as before: all slices ending at i − 1 extend to i, and [i−2, i−1, i] is new, hence + 1.
3. A different difference resets the run.
4. total accumulates the slices ending at each index.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Fewer than 3 elements → 0.
• One long run, e.g. [1, 2, 3, 4] → 3.
• Constant arrays (difference 0) count too.

Complexity: O(n) time, O(1) space.

Problem: Count the contiguous subarrays whose product is strictly less than k (all numbers are positive).

Solve it on LeetCode ↗

Constraints: 1 ≤ nums.length ≤ 3 * 10⁴ · 1 ≤ nums[i] ≤ 1000 · 0 ≤ k ≤ 10⁶

From brute force to the pattern: Multiplying out every subarray is O(n²). The window stays valid as it slides, and counting right − left + 1 per step counts all valid subarrays in one pass.

Spot it: Positive numbers mean the product only grows when the window grows and only shrinks when it shrinks: a variable sliding window. When the window [left, right] is valid, every subarray ending at right inside it is valid too.

Why not another pattern? Checking all subarrays is O(n²). Logarithms plus prefix sums and binary search work but add floating-point risk and log n.

Approach:

1. If k ≤ 1, no product of positive integers is below it: return 0.
2. Extend right, multiplying product by nums[right].
3. While product ≥ k, divide out nums[left] and move left right.
4. Add right − left + 1: the number of valid subarrays ending at right.

class Solution:
    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
        if k <= 1:
            return 0  # products of positive integers are at least 1
        product = 1
        left = 0
        count = 0
        for right in range(len(nums)):
            product = product * nums[right]  # grow the window
            while product >= k:
                product = product // nums[left]  # shrink until valid again
                left = left + 1
            count = count + (right - left + 1)  # subarrays ending at right
        return count

What the code is doing, line by line:

1. k <= 1 guard: otherwise the shrinking loop could move left past right.
2. Multiplying by nums[right] adds the new element to the window's product.
3. The while divides out elements from the left until the product is below k again (exact integer division because nums[left] divides the product).
4. right - left + 1: subarrays [left..right], [left+1..right], …, [right..right] all have product < k.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• k = 0 or k = 1 → 0.
• A single element ≥ k (the window becomes empty).
• All ones with k = 2 → n(n + 1)/2.

Complexity: O(n) time (each index enters and leaves the window once), O(1) space.

Problem: Return the length of the longest subarray that appears in both nums1 and nums2.

Solve it on LeetCode ↗

Constraints: 1 ≤ nums1.length, nums2.length ≤ 1000 · 0 ≤ nums1[i], nums2[i] ≤ 100

From brute force to the pattern: Comparing every pair of start positions and extending is O(m · n · min(m, n)). Each alignment is scanned once with a running streak, so the whole thing is O(m · n).

Spot it: A common subarray is a run of matches on one alignment (offset) of the two arrays. Sliding one array across the other and scanning each alignment for its longest run of equal elements is a window-style scan with O(1) memory.

Why not another pattern? The classic DP dp[i][j] = dp[i−1][j−1] + 1 on matches is also O(m · n) but uses O(m · n) (or O(n)) memory. Binary search on the length with rolling hashes is O((m + n) log) but more complex.

Approach:

1. For every offset (how far nums2 is shifted relative to nums1), walk the overlapping positions together.
2. Keep run = length of the current streak of equal pairs; reset it on a mismatch.
3. The best streak over all offsets is the answer.

class Solution:
    def findLength(self, nums1: List[int], nums2: List[int]) -> int:
        m = len(nums1)
        n = len(nums2)
        best = 0
        for offset in range(-(n - 1), m):  # nums2[j] lines up with nums1[j + offset]
            run = 0
            for j in range(n):
                i = j + offset
                if i < 0 or i >= m:
                    continue  # outside the overlap
                if nums1[i] == nums2[j]:
                    run = run + 1  # the matching streak continues
                    best = max(best, run)
                else:
                    run = 0  # a mismatch breaks the streak
        return best

What the code is doing, line by line:

1. offset covers every way of lining up the two arrays.
2. For a fixed offset, a common subarray is a run of consecutive equal pairs.
3. run counts the current streak; best keeps the longest streak seen on any alignment.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• No common elements → 0.
• Identical arrays → their length.
• The common part at the end of one array and the start of the other.

Complexity: O(m · n) time, O(1) space.

Problem: Count the subarrays of length k whose average is at least threshold.

Solve it on LeetCode ↗

Constraints: 1 ≤ arr.length ≤ 10⁵ · 1 ≤ arr[i] ≤ 10⁴ · 1 ≤ k ≤ arr.length · 0 ≤ threshold ≤ 10⁴

From brute force to the pattern: Recomputing each window's sum is O(n · k). Updating it as the window slides is O(1) per step: O(n) total.

Spot it: Every window has the same size k: a fixed sliding window whose sum is updated in O(1) per step.

Why not another pattern? Summing each window from scratch is O(n · k). Prefix sums also give each window sum in O(1), at the cost of an extra array.

Approach:

1. Compare sums instead of averages: average ≥ threshold ⇔ sum ≥ k · threshold (no division).
2. Sum the first k elements.
3. Slide: add the entering element, subtract the leaving one; count windows whose sum reaches the target.

class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        target = k * threshold  # compare sums instead of averages
        window = sum(arr[:k])
        count = 1 if window >= target else 0
        for right in range(k, len(arr)):
            window = window + arr[right] - arr[right - k]  # slide by one
            if window >= target:
                count = count + 1
        return count

What the code is doing, line by line:

1. target = k * threshold: multiplying both sides by k avoids floating-point averages.
2. window = sum(arr[:k]): the first window.
3. Each slide adds arr[right] and removes arr[right - k], the element that just left.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• k = n → one window.
• threshold = 0 → every window counts.
• k = 1 → count the elements ≥ threshold.

Complexity: O(n) time, O(1) space.

Problem: Count the substrings of s (made of a, b, c) that contain at least one of each letter.

Solve it on LeetCode ↗

Constraints: 3 ≤ s.length ≤ 5 x 10⁴ · s only consists of 'a', 'b' or 'c' characters.

From brute force to the pattern: Checking every substring for the three letters is O(n²). Validity is monotonic in the start position, so a window counts all valid starts for each end in amortised O(1).

Spot it: "At least one of each" is monotonic: once a window is valid, extending it stays valid. So for each right edge, find the largest left edge that still keeps it valid; every start at or before that edge works.

Why not another pattern? Checking every substring is O(n²). Tracking the last index of each letter is an even shorter equivalent (count += min(last) + 1).

Approach:

1. Grow the window to the right, counting letters.
2. While the window has all three letters, shrink from the left.
3. After shrinking, left is the number of valid starts for this right edge (starts 0..left−1); add it.

class Solution:
    def numberOfSubstrings(self, s: str) -> int:
        count = {"a": 0, "b": 0, "c": 0}
        left = 0
        total = 0
        for right in range(len(s)):
            count[s[right]] = count[s[right]] + 1
            while count["a"] > 0 and count["b"] > 0 and count["c"] > 0:
                count[s[left]] = count[s[left]] - 1  # shrink while still containing all three
                left = left + 1
            total = total + left  # starts 0..left-1 all give a valid substring ending here
        return total

What the code is doing, line by line:

1. count holds the letters inside s[left..right].
2. The while shrinks until the window is just missing one letter; at that point s[left − 1 .. right] was the shortest valid window.
3. Any start from 0 to left − 1 gives a valid substring ending at right, so add left.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• A string missing a letter → 0.
• "abc" → 1.
• Long runs of one letter.

Complexity: O(n) time, O(1) space.

Problem: Take exactly k cards, each from the left or right end of the row. Maximise the total points.

Solve it on LeetCode ↗

Constraints: 1 ≤ cardPoints.length ≤ 10⁵ · 1 ≤ cardPoints[i] ≤ 10⁴ · 1 ≤ k ≤ cardPoints.length

From brute force to the pattern: Trying every sequence of left/right picks is 2ᵏ. Thinking about the leftover block turns it into a fixed sliding window: O(n).

Spot it: Whatever you take from the ends, the cards left over form one contiguous block of length n − k. Maximising what you take means minimising that block's sum: a fixed-size sliding window.

Why not another pattern? Trying every split (i from the left, k − i from the right) with prefix sums is also O(k) and equally good. Recursion over choices is exponential.

Approach:

1. window = n − k. Sum the first window cards.
2. Slide the window across, tracking the minimum window sum.
3. Answer = total − minimum window sum.

class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        n = len(cardPoints)
        size = n - k  # the cards we leave behind form one block of this size
        total = sum(cardPoints)
        if size == 0:
            return total  # take everything
        window = sum(cardPoints[:size])
        smallest = window
        for right in range(size, n):
            window = window + cardPoints[right] - cardPoints[right - size]  # slide the block
            smallest = min(smallest, window)
        return total - smallest  # what's not left behind is what we took

What the code is doing, line by line:

1. size = n - k: the untouched middle block always has this length.
2. if size == 0: taking all cards is the only option.
3. The fixed window slides over all blocks of length size, tracking the smallest sum.
4. total - smallest: the best score.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• k = n → the total.
• k = 1 → the larger end card.
• All cards equal.

Complexity: O(n) time, O(1) space.

Problem: Return True if every binary string of length k appears as a substring of s.

Solve it on LeetCode ↗

Constraints: 1 ≤ s.length ≤ 5 * 10⁵ · s[i] is either '0' or '1'. · 1 ≤ k ≤ 20

From brute force to the pattern: Slicing every window costs O(k) each; a rolling integer makes each step O(1), so the scan is O(n).

Spot it: All substrings of length k are the windows of a fixed size. A rolling bit value (shift left, add the new bit, mask to k bits) gives each window's code in O(1); collect them in a set and check whether there are 2ᵏ of them.

Why not another pattern? Slicing each window as a string is O(k) per window. Generating all 2ᵏ codes and searching for each is O(2ᵏ · n).

Approach:

1. If there are fewer than 2ᵏ windows, return False early.
2. Keep value = the last k bits as an integer: value = ((value << 1) & mask) | bit.
3. Once at least k bits have been read, add value to a set.
4. Return whether the set has 2ᵏ codes.

class Solution:
    def hasAllCodes(self, s: str, k: int) -> bool:
        need = 1 << k  # 2^k different codes
        if len(s) - k + 1 < need:
            return False  # not enough windows to contain every code
        mask = need - 1  # keeps only the last k bits
        seen = set()
        value = 0
        for i in range(len(s)):
            value = ((value << 1) & mask) | (s[i] == "1")  # slide the k-bit window
            if i >= k - 1:
                seen.add(value)  # the window s[i-k+1 .. i]
        return len(seen) == need

What the code is doing, line by line:

1. 1 << k is 2ᵏ; with fewer windows than that, some code must be missing.
2. (value << 1) & mask: shift in a new bit and drop the oldest one; | (s[i] == "1") adds the new bit (True counts as 1).
3. From index k − 1 on, value encodes a full window.
4. Distinct window codes are collected in seen.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• k larger than len(s) → False.
• k = 1: both 0 and 1 must appear.
• Many repeated windows.

Complexity: O(n) time, O(2ᵏ) space.

Problem: Erase one subarray with all unique elements; its score is the sum of its elements. Return the maximum score.

Solve it on LeetCode ↗

Constraints: 1 ≤ nums.length ≤ 10⁵ · 1 ≤ nums[i] ≤ 10⁴

From brute force to the pattern: Summing every unique subarray is O(n²). A window that only moves forward handles each element twice: O(n).

Spot it: "Contiguous + all unique" is the Longest Substring Without Repeating Characters window, keeping a running sum instead of a length.

Why not another pattern? Checking every subarray is O(n²). Prefix sums alone can't enforce uniqueness. The window works because all values are positive: extending a valid window can only increase its sum, so the best window ending at each position is the longest unique one.

Approach:

1. Grow the window to the right, adding to window_sum.
2. If the new value is already in the window, remove from the left until it isn't.
3. Track the best window_sum.

class Solution:
    def maximumUniqueSubarray(self, nums: List[int]) -> int:
        inside = set()  # values currently in the window
        left = 0
        window_sum = 0
        best = 0
        for x in nums:
            while x in inside:
                inside.remove(nums[left])  # drop from the left until x is unique
                window_sum = window_sum - nums[left]
                left = left + 1
            inside.add(x)
            window_sum = window_sum + x
            best = max(best, window_sum)
        return best

What the code is doing, line by line:

1. inside is the set of values in the window, so the uniqueness check is O(1).
2. The while removes elements from the left until the old copy of x is gone.
3. Add x and update the running sum and the best score.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• All values distinct → the whole sum.
• All values equal → that value.
• A duplicate far back in the window.

Complexity: O(n) time, O(n) space.

Problem: In one operation you can increment any element by 1. With at most k operations, maximise the frequency of some element.

Solve it on LeetCode ↗

Constraints: 1 ≤ nums.length ≤ 10⁵ · 1 ≤ nums[i] ≤ 10⁵ · 1 ≤ k ≤ 10⁵

From brute force to the pattern: For every target value, raising the closest smaller values greedily is O(n²). Sorting makes the cost of a window easy to compute, and the window only moves forward: O(n log n) total.

Spot it: After sorting, it's best to raise a contiguous block of values up to its largest element. The cost of a window [left, right] is nums[right] × size − window_sum, which only grows when the window grows: a variable sliding window.

Why not another pattern? For each target value, binary-searching the farthest start with prefix sums is O(n log n) after sorting; the window is O(n) after sorting.

Approach:

1. Sort nums.
2. Extend right, adding to window_sum.
3. While raising everything in the window to nums[right] costs more than k, remove nums[left].
4. Track the longest window.

class Solution:
    def maxFrequency(self, nums: List[int], k: int) -> int:
        nums = sorted(nums)
        left = 0
        window_sum = 0
        best = 0
        for right in range(len(nums)):
            window_sum = window_sum + nums[right]
            # cost to raise every element of the window up to nums[right]
            while nums[right] * (right - left + 1) - window_sum > k:
                window_sum = window_sum - nums[left]  # too expensive: drop the smallest
                left = left + 1
            best = max(best, right - left + 1)
        return best

What the code is doing, line by line:

1. Sorting puts the cheapest values to raise right next to the target.
2. nums[right] * size - window_sum is exactly how many increments the window needs.
3. If that exceeds k, drop the leftmost (smallest) element, which is the most expensive to raise.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• k = 0 → the highest existing frequency.
• All equal values → n.
• Large k that can raise everything → n.

Complexity: O(n log n) time for the sort, O(n) for the window.

Problem: You may rotate s (move the first character to the end) any number of times, then flip characters. Return the minimum number of flips to make s alternating.

Solve it on LeetCode ↗

Constraints: 1 ≤ s.length ≤ 10⁵ · s[i] is either '0' or '1'.

From brute force to the pattern: For each of the n rotations, counting mismatches is O(n): O(n²). In s + s consecutive rotations differ by one character in and one out, so the counts update in O(1).

Spot it: Every rotation of s is a window of length n in s + s. Compare each window with the two alternating patterns: the number of mismatches changes by at most one character in and one out as the window slides.

Why not another pattern? Rebuilding each rotation and counting mismatches is O(n²).

Approach:

1. Let t = s + s; every rotation of s is one window of length n in t.
2. Slide a window of length n over t, keeping mismatch counts against both patterns 0101… and 1010….
3. Each full window gives a candidate: the smaller of the two counts.

class Solution:
    def minFlips(self, s: str) -> int:
        n = len(s)
        t = s + s  # every rotation is a window of length n
        diff_a = 0  # mismatches against "0101..."
        diff_b = 0  # mismatches against "1010..."
        best = n
        for i in range(len(t)):
            expect_a = "0" if i % 2 == 0 else "1"
            if t[i] != expect_a:
                diff_a = diff_a + 1
            else:
                diff_b = diff_b + 1  # matching "0101..." means mismatching "1010..."
            if i >= n:  # the character at i - n leaves the window
                old = t[i - n]
                old_expect_a = "0" if (i - n) % 2 == 0 else "1"
                if old != old_expect_a:
                    diff_a = diff_a - 1
                else:
                    diff_b = diff_b - 1
            if i >= n - 1:
                best = min(best, diff_a, diff_b)  # a full rotation is in the window
        return best

What the code is doing, line by line:

1. t = s + s: rotating by r gives t[r : r + n].
2. The patterns are fixed to positions in t; a window starting at an odd index simply uses them shifted, which is why both patterns are tracked.
3. Each character either matches pattern A or pattern B, so exactly one of the two counters goes up.
4. When the window is longer than n, the character leaving it is removed from whichever counter it was in.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Already alternating → 0.
• Odd length (rotation actually helps), e.g. "111000" → 2.
• A single character → 0.

Complexity: O(n) time, O(n) space for s + s.

Problem: Among subarrays of length k whose elements are all distinct, return the maximum sum (0 if none).

Solve it on LeetCode ↗

Constraints: 1 ≤ k ≤ nums.length ≤ 10⁵ · 1 ≤ nums[i] ≤ 10⁵

From brute force to the pattern: Checking each window with a fresh set is O(n · k). A count map updated as the window slides is O(1) per step.

Spot it: Fixed-length windows (k) with a property of their contents (all distinct): slide the window and keep counts of the values inside.

Why not another pattern? Rebuilding a set for every window is O(n · k). A count map updated by one add and one remove per slide is O(1) per step.

Approach:

1. Slide a window of size k, keeping count of each value and the window sum.
2. When a value's count drops to 0, delete it, so len(count) is the number of distinct values.
3. If len(count) == k, the window is valid: update the best sum.

class Solution:
    def maximumSubarraySum(self, nums: List[int], k: int) -> int:
        count = {}  # value -> occurrences inside the window
        window_sum = 0
        best = 0
        for right in range(len(nums)):
            x = nums[right]
            count[x] = count.get(x, 0) + 1
            window_sum = window_sum + x
            if right >= k:
                old = nums[right - k]  # the element leaving the window
                count[old] = count[old] - 1
                if count[old] == 0:
                    del count[old]
                window_sum = window_sum - old
            if right >= k - 1 and len(count) == k:
                best = max(best, window_sum)  # all k values are distinct
        return best

What the code is doing, line by line:

1. Add the entering element to count and to the sum.
2. Once the window is longer than k, remove nums[right - k]; deleting zero counts keeps len(count) equal to the number of distinct values.
3. A full window with k distinct keys has no duplicates.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• No valid window → 0.
• k = 1 → the maximum element.
• A duplicate that enters and leaves the window.

Complexity: O(n) time, O(k) space.

Problem: Return the length of the longest subarray in which every value occurs at most k times.

Solve it on LeetCode ↗

Constraints: 1 ≤ nums.length ≤ 10⁵ · 1 ≤ nums[i] ≤ 10⁹ · 1 ≤ k ≤ nums.length

From brute force to the pattern: Counting frequencies for every subarray is O(n²). The window keeps counts incrementally and each index moves at most twice: O(n).

Spot it: Longest contiguous window satisfying a frequency limit: a variable sliding window. The only value that can exceed k after adding nums[right] is nums[right] itself, so shrink until its count is back to k.

Why not another pattern? Checking every subarray is O(n²). Binary search on the length with a check per length is O(n log n); the window is linear.

Approach:

1. Add nums[right] to the counts.
2. While its count exceeds k, remove nums[left] and move left right.
3. Track the longest window.

class Solution:
    def maxSubarrayLength(self, nums: List[int], k: int) -> int:
        count = {}
        left = 0
        best = 0
        for right in range(len(nums)):
            x = nums[right]
            count[x] = count.get(x, 0) + 1
            while count[x] > k:
                count[nums[left]] = count[nums[left]] - 1  # shrink until x is allowed again
                left = left + 1
            best = max(best, right - left + 1)
        return best

What the code is doing, line by line:

1. count tracks frequencies inside the window.
2. Only x can have just gone over the limit, so the loop shrinks until count[x] ≤ k.
3. right - left + 1 is the current valid window length.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• k ≥ n → the whole array.
• All elements equal → k.
• k = 1 → the longest subarray of distinct values.

Complexity: O(n) time, O(n) space.

Problem: Query [l, r, val] lets you decrement each element in l..r by up to val. Return the smallest k such that the first k queries can turn nums into all zeros, or −1.

Solve it on LeetCode ↗

Constraints: 1 ≤ nums.length ≤ 10⁵ · 0 ≤ nums[i] ≤ 5 * 10⁵ · 1 ≤ queries.length ≤ 10⁵ · queries[i].length == 3 · 0 ≤ li ≤ ri < nums.length · 1 ≤ vali ≤ 5

From brute force to the pattern: Trying each k and simulating all k queries is O(q · (n + q)). Because the first k queries are always used in order, one left-to-right sweep that pulls queries only when needed finds the minimum k in O(n + q).

Spot it: Walk the array left to right keeping how much decrement is available at the current index. Whenever it's not enough, pull in the next query; queries only ever move forward, so this is a two-pointer sweep with a difference array for the ranges.

Why not another pattern? Binary search on k with a difference-array check per guess is O((n + q) log q) and also fine; the sweep avoids the log factor.

Approach:

1. diff records where each applied query's decrement starts and stops; power is the running sum at index i.
2. At index i, add diff[i] to power.
3. While power < nums[i]: apply query k. If it covers i, it contributes now (power += val) and stops after r; if it starts later, record it in diff. If no queries are left, return −1.
4. After the sweep, k is the answer.

class Solution:
    def minZeroArray(self, nums: List[int], queries: List[List[int]]) -> int:
        n = len(nums)
        diff = [0] * (n + 1)  # decrement starting/stopping at each index
        power = 0  # total decrement available at the current index
        k = 0  # number of queries used so far
        for i in range(n):
            power = power + diff[i]
            while power < nums[i]:
                if k == len(queries):
                    return -1  # every query used and nums[i] still can't reach 0
                l, r, val = queries[k]
                k = k + 1
                if r < i:
                    continue  # this query only covers indices we've already handled
                start = max(l, i)
                if start == i:
                    power = power + val  # covers i right now
                else:
                    diff[start] = diff[start] + val  # starts later
                diff[r + 1] = diff[r + 1] - val  # stops after r
        return k

What the code is doing, line by line:

1. power is the sum of val over the applied queries that cover index i (a running prefix sum of diff).
2. The while pulls in queries in order only when needed, so k ends as small as possible.
3. A query that ends before i is still "processed" (it counts toward k) but can't help anymore.
4. Queries starting at or before i add to power immediately; later ones are scheduled in diff. All of them stop at r + 1.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Already all zeros → 0.
• Not enough total decrement → −1.
• A query that ends before the index that needs it (it still counts toward k).

Complexity: O(n + q) time, O(n) space.

Problem: Return the maximum number of vowels in any substring of length k.

Solve it on LeetCode ↗

Constraints: 1 ≤ s.length ≤ 10⁵ · s consists of lowercase English letters. · 1 ≤ k ≤ s.length

From brute force to the pattern: Recounting each window is O(nk); sliding is O(n).

Spot it: Every window has the same length → fixed-size sliding window: one character enters and one leaves per step.

Why not another pattern? Recounting each window is O(n · k).

Approach:

1. Count vowels in the first k characters.
2. Slide: +1 if s[i] is a vowel, −1 if s[i − k] was.
3. Track the maximum.

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        vowels = set("aeiou")
        count = sum(ch in vowels for ch in s[:k])  # first window
        best = count
        for i in range(k, len(s)):
            count += (s[i] in vowels) - (s[i - k] in vowels)  # one enters, one leaves
            best = max(best, count)
        return best

What the code is doing, line by line:

1. Booleans add as 0/1 in Python.
2. Each step costs O(1).

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• k == len(s).
• No vowels → 0.
• All vowels → k.

Complexity: O(n) time, O(1) space.

Problem: Return every 10-letter substring that occurs more than once.

Solve it on LeetCode ↗

Constraints: 1 ≤ s.length ≤ 10⁵ · s[i] is either 'A', 'C', 'G', or 'T'.

From brute force to the pattern: Pairwise comparison is O(n²); a set of windows is linear.

Spot it: Fixed-size sliding window of 10 characters with a hash set of windows seen so far.

Why not another pattern? Comparing every pair of windows is O(n²).

Approach:

1. For each start i: w = s[i:i + 10].
2. If w is in seen, add it to repeated; else add it to seen.

class Solution:
    def findRepeatedDnaSequences(self, s: str) -> List[str]:
        seen, repeated = set(), set()
        for i in range(len(s) - 9):
            window = s[i:i + 10]
            if window in seen:
                repeated.add(window)  # second (or later) occurrence
            else:
                seen.add(window)
        return list(repeated)

What the code is doing, line by line:

1. A set for repeats avoids listing the same sequence twice.
2. A 2-bit encoding per letter (rolling hash in 20 bits) avoids slicing, but slicing 10 letters is cheap.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Shorter than 10 → [].
• Overlapping repeats (AAAAAAAAAAA).
• Same sequence many times (listed once).

Complexity: O(10n) time, O(10n) space.

Problem: Return the minimum swaps (of any two elements) to group all 1s together.

Solve it on LeetCode ↗ (Premium)

Constraints: 1 ≤ data.length ≤ 10⁵ · data[i] is either 0 or 1

From brute force to the pattern: Counting each window from scratch is O(nm); sliding is O(n).

Spot it: All m ones end up in some window of length m. Every 0 inside that window needs one swap, so find the window with the most ones: a fixed-size sliding window.

Why not another pattern? Trying every target window and counting from scratch is O(n · m).

Approach:

1. m = sum(data).
2. Slide a window of size m, tracking its ones.
3. Answer m − max ones in a window.

class Solution:
    def minSwaps(self, data: List[int]) -> int:
        m = sum(data)  # the group's final length
        if m <= 1:
            return 0
        ones = best = sum(data[:m])
        for i in range(m, len(data)):
            ones += data[i] - data[i - m]  # slide by one
            best = max(best, ones)
        return m - best  # each 0 in the best window needs one swap

What the code is doing, line by line:

1. Any swap can bring one outside 1 into the window, replacing a 0.
2. The window with the most ones needs the fewest swaps.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• No ones or one one → 0.
• All ones → 0.
• Ones at both ends.

Complexity: O(n) time, O(1) space.

Problem: Return the longest subarray in which every pair differs by at most limit.

Solve it on LeetCode ↗

Constraints: 1 ≤ nums.length ≤ 10⁵ · 1 ≤ nums[i] ≤ 10⁹ · 0 ≤ limit ≤ 10⁹

From brute force to the pattern: All subarrays: O(n²); a sorted structure: O(n log n); two deques: O(n).

Spot it: "Longest subarray with a condition that only gets worse as it grows" → sliding window. The condition is max − min ≤ limit, so keep the window max and min in two monotonic deques.

Why not another pattern? Recomputing max and min for every window is O(n²).

Approach:

1. maxq decreasing, minq increasing (indices).
2. Add right; while max − min > limit, move left and drop deque fronts that fall out.
3. Track the longest window.

from collections import deque

class Solution:
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        maxq, minq = deque(), deque()  # indices; values decreasing / increasing
        left = best = 0
        for right, x in enumerate(nums):
            while maxq and nums[maxq[-1]] <= x:
                maxq.pop()
            maxq.append(right)
            while minq and nums[minq[-1]] >= x:
                minq.pop()
            minq.append(right)
            while nums[maxq[0]] - nums[minq[0]] > limit:
                left += 1  # shrink until the window is valid
                if maxq[0] < left:
                    maxq.popleft()
                if minq[0] < left:
                    minq.popleft()
            best = max(best, right - left + 1)
        return best

What the code is doing, line by line:

1. The deque fronts are always the current window's max and min.
2. Each index enters and leaves each deque once.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• limit = 0 (runs of equal values).
• All equal.
• Large swings.

Complexity: O(n) time, O(n) space.

Problem: Tile ranges [l, r] are white (non-overlapping). Place one carpet of length carpetLen. Return the most white tiles covered.

Solve it on LeetCode ↗

Constraints: 1 ≤ tiles.length ≤ 5 * 10⁴ · tiles[i].length == 2 · 1 ≤ li ≤ ri ≤ 10⁹ · 1 ≤ carpetLen ≤ 10⁹ · The tiles are non-overlapping.

From brute force to the pattern: Every start coordinate is infeasible; starting at range ends gives O(n log n).

Spot it: A best carpet can start at some range's left end (shifting it right to one never loses tiles). Then it's a sliding window over ranges: add fully covered ranges, plus the partly covered one.

Why not another pattern? Trying every start position is impossible with coordinates up to 10⁹.

Approach:

1. Sort ranges.
2. For each start range i: end = l_i + len − 1; advance j over ranges ending ≤ end, summing their lengths.
3. Add the partial overlap of range j; then remove range i.

class Solution:
    def maximumWhiteTiles(self, tiles: List[List[int]], carpetLen: int) -> int:
        tiles = sorted(tiles)
        best = covered = 0
        j = 0
        for i, (l, r) in enumerate(tiles):
            end = l + carpetLen - 1
            while j < len(tiles) and tiles[j][1] <= end:
                covered += tiles[j][1] - tiles[j][0] + 1  # fully under the carpet
                j += 1
            partial = max(0, end - tiles[j][0] + 1) if j < len(tiles) else 0
            best = max(best, covered + partial)
            if j > i:
                covered -= r - l + 1  # the carpet moves past range i
            else:
                j = i + 1  # range i itself was only partly covered
        return best

What the code is doing, line by line:

1. Starting at a range's left end is never worse than starting in a gap or partway into a range.
2. When the carpet is shorter than range i, j stays at i, the partial covers carpetLen, and nothing is subtracted.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Carpet longer than all tiles.
• Carpet shorter than one range.
• Big gaps.

Complexity: O(n log n) time, O(1) extra space.

Problem: For each window of size k, return its x-th smallest negative number, or 0 if there are fewer than x negatives.

Solve it on LeetCode ↗

Constraints: n == nums.length · 1 ≤ n ≤ 10⁵ · 1 ≤ k ≤ n · 1 ≤ x ≤ k · -50 ≤ nums[i] ≤ 50

From brute force to the pattern: Sorting every window is O(nk log k); counting is O(50n).

Spot it: Fixed-size sliding window with a tiny value range: a count array over −50..−1 lets you find the x-th smallest negative in 50 steps.

Why not another pattern? Sorting each window is O(n · k log k).

Approach:

1. count[v + 50] for negatives in the window.
2. Slide: add the new value, remove the old one.
3. Walk counts from −50 upward until x values are passed.

class Solution:
    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:
        count = [0] * 50  # count[v + 50] for v in -50..-1
        result = []
        for i, v in enumerate(nums):
            if v < 0:
                count[v + 50] += 1
            if i >= k and nums[i - k] < 0:
                count[nums[i - k] + 50] -= 1  # leaves the window
            if i >= k - 1:
                seen = 0
                beauty = 0
                for j in range(50):  # smallest negatives first
                    seen += count[j]
                    if seen >= x:
                        beauty = j - 50
                        break
                result.append(beauty)
        return result

What the code is doing, line by line:

1. Only negatives matter, and there are just 50 possible values.
2. Walking the counts in increasing value finds the x-th smallest.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Fewer than x negatives → 0.
• All negative.
• k = 1.

Complexity: O(50 · n) time, O(1) extra space.

Problem: Count subarrays where every pair of elements differs by at most 2.

Solve it on LeetCode ↗

Constraints: 1 ≤ nums.length ≤ 10⁵ · 1 ≤ nums[i] ≤ 10⁹

From brute force to the pattern: Checking all subarrays is O(n²); the counting window is O(n).

Spot it: Same window as the previous problem (max − min ≤ limit with monotonic deques), but count: each valid window [left, right] adds right − left + 1 subarrays ending at right.

Why not another pattern? Checking every subarray is O(n²).

Approach:

1. Slide with max/min deques; shrink while max − min > 2.
2. Add right − left + 1 for each right.

from collections import deque

class Solution:
    def continuousSubarrays(self, nums: List[int]) -> int:
        maxq, minq = deque(), deque()
        left = count = 0
        for right, x in enumerate(nums):
            while maxq and nums[maxq[-1]] <= x:
                maxq.pop()
            maxq.append(right)
            while minq and nums[minq[-1]] >= x:
                minq.pop()
            minq.append(right)
            while nums[maxq[0]] - nums[minq[0]] > 2:
                left += 1
                if maxq[0] < left:
                    maxq.popleft()
                if minq[0] < left:
                    minq.popleft()
            count += right - left + 1  # every start in [left, right] works
        return count

What the code is doing, line by line:

1. If [left, right] is valid, every shorter subarray ending at right is too.
2. The total can exceed 32 bits.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• All equal → n(n + 1)/2.
• Differences exactly 2.
• n = 1.

Complexity: O(n) time and space.

Problem: Non-overlapping segments [l, r] hold c coins per bag. Collect k consecutive bags (positions up to 10⁹) for the most coins.

Solve it on LeetCode ↗

Constraints: 1 ≤ coins.length ≤ 10⁵ · 1 ≤ k ≤ 10⁹ · coins[i] == [li, ri, ci] · 1 ≤ li ≤ ri ≤ 10⁹ · 1 ≤ ci ≤ 1000 · The given segments are non-overlapping.

From brute force to the pattern: Sliding over every coordinate is infeasible; aligning windows to segment ends gives O(n log n).

Spot it: Positions are huge, but an optimal window can always be shifted until it starts at a segment's left end or ends at a segment's right end without losing coins. So try windows aligned to segments with a sliding window over segments (full segments summed, one partial), once forwards and once on the mirrored line.

Why not another pattern? Sliding over every position is impossible with coordinates up to 10⁹.

Approach:

1. best(segs): segments sorted by start; for each segment i, the window is [l_i, l_i + k − 1].
2. Advance j while segment j ends inside the window, adding its full coins; add the partial overlap of segment j.
3. Remove segment i when moving on. Run it on the segments and on their mirror images (−r, −l).

class Solution:
    def maximumCoins(self, coins: List[List[int]], k: int) -> int:
        def best(segs):  # windows that start at a segment's left end
            segs.sort()
            res = full = 0
            j = 0
            for i, (l, r, c) in enumerate(segs):
                if j < i:
                    j, full = i, 0  # previous window didn't even cover segment i
                end = l + k - 1
                while j < len(segs) and segs[j][1] <= end:
                    full += (segs[j][1] - segs[j][0] + 1) * segs[j][2]  # segment fully inside
                    j += 1
                partial = 0
                if j < len(segs) and segs[j][0] <= end:
                    partial = (end - segs[j][0] + 1) * segs[j][2]  # cut-off segment at the end
                res = max(res, full + partial)
                if j > i:
                    full -= (r - l + 1) * c  # slide past segment i
            return res

        forward = best([s[:] for s in coins])
        backward = best([[-r, -l, c] for l, r, c in coins])  # windows that end at a right end
        return max(forward, backward)

What the code is doing, line by line:

1. If a window starts inside a gap or mid-segment, shifting it toward the richer side never loses coins until an endpoint aligns; that's why only aligned windows are needed.
2. Mirroring positions (x → −x) turns "ends at a right end" into "starts at a left end", so one helper handles both.
3. full holds the coins of segments completely inside the window; at most one segment is cut at the right edge.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• k longer than all segments combined.
• One very long segment (window inside it).
• Gaps between segments.

Complexity: O(n log n) time, O(n) space.

Problem: Return the fewest adjacent swaps to make k consecutive 1s.

Solve it on LeetCode ↗

Constraints: 1 ≤ nums.length ≤ 10⁵ · nums[i] is 0 or 1. · 1 ≤ k ≤ sum(nums)

From brute force to the pattern: Trying every window and simulating swaps is O(nk); the median formula is O(n).

Spot it: Choose k consecutive ones (a sliding window over the ones' positions) and gather them together. Gathering into a block is like gathering to one point after the shift q_i = p_i − i; the best meeting point is the median, and prefix sums give the cost of each window in O(1).

Why not another pattern? Simulating swaps for every window is O(n · k) or worse.

Approach:

1. pos = indices of ones; q[i] = pos[i] − i; prefix sums P of q.
2. For each window q[i..i+k−1] with median index m = i + k // 2: cost = q[m]·(m − i) − (P[m] − P[i]) + (P[i+k] − P[m+1]) − q[m]·(i + k − m − 1).
3. Return the minimum.

class Solution:
    def minMoves(self, nums: List[int], k: int) -> int:
        q = [p - i for i, p in enumerate(i for i, x in enumerate(nums) if x)]  # positions minus rank
        P = [0]
        for v in q:
            P.append(P[-1] + v)
        best = float("inf")
        for i in range(len(q) - k + 1):
            m = i + k // 2  # median of this window
            left = q[m] * (m - i) - (P[m] - P[i])  # pull the left part up to the median
            right = (P[i + k] - P[m + 1]) - q[m] * (i + k - m - 1)  # pull the right part down
            best = min(best, left + right)
        return best

What the code is doing, line by line:

1. Subtracting each one's rank turns "make them consecutive" into "move them all to the same value", which costs Σ|q − target|.
2. That sum is minimised at the median, and with prefix sums it's computed per window in O(1).
3. Windows of consecutive ones are optimal: skipping a one in between would only add distance.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• k = 1 → 0.
• Ones already together → 0.
• Ones spread far apart.

Complexity: O(n) time, O(n) space.

Problem: Replace elements so the array has distinct values with max − min = n − 1. Return the fewest replacements.

Solve it on LeetCode ↗

Constraints: 1 ≤ nums.length ≤ 10⁵ · 1 ≤ nums[i] ≤ 10⁹

From brute force to the pattern: Trying every block start is infeasible; a window over sorted distinct values is O(n log n).

Spot it: The final values are a block [v, v + n − 1]. Keep as many existing distinct values inside some such block as possible: over the sorted distinct values, a sliding window where vals[right] − vals[left] ≤ n − 1.

Why not another pattern? Trying every starting value v up to 10⁹ is impossible.

Approach:

1. vals = sorted(set(nums)).
2. For each left, extend right while vals[right] ≤ vals[left] + n − 1.
3. Answer n − max(window size).

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        n = len(nums)
        vals = sorted(set(nums))  # duplicates must be replaced anyway
        best = right = 0
        for left in range(len(vals)):
            while right < len(vals) and vals[right] <= vals[left] + n - 1:
                right += 1  # still fits in a block starting at vals[left]
            best = max(best, right - left)  # values we can keep
        return n - best

What the code is doing, line by line:

1. Starting the block at an existing value is never worse.
2. Values kept must be distinct and fit in the block; everything else is replaced.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Already continuous → 0.
• Many duplicates.
• Values far apart.

Complexity: O(n log n) time, O(n) space.

Problem: Count substrings in which every letter that appears occurs exactly count times.

Solve it on LeetCode ↗ (Premium)

Constraints: 1 ≤ s.length ≤ 3 * 10⁴ · 1 ≤ count ≤ 3 * 10⁴ · s consists only of lowercase English letters

From brute force to the pattern: All substrings with counts: O(26 n²); one fixed window per u: O(26 n).

Spot it: If such a substring has u distinct letters, its length is exactly u · count. So for each u from 1 to 26, a fixed-size sliding window with letter counts, tracking how many letters sit at exactly count.

Why not another pattern? Checking every substring's letter counts is O(26 n²).

Approach:

1. For u = 1..26: window length L = u · count (skip if > n).
2. Slide, updating counts and exact = letters with count == count.
3. When exact == u, the window qualifies.

class Solution:
    def equalCountSubstrings(self, s: str, count: int) -> int:
        n = len(s)
        total = 0
        for u in range(1, 27):  # number of distinct letters in the substring
            L = u * count
            if L > n:
                break
            freq = [0] * 26
            exact = 0  # letters occurring exactly `count` times in the window
            for i, ch in enumerate(s):
                c = ord(ch) - 97
                freq[c] += 1
                if freq[c] == count:
                    exact += 1
                elif freq[c] == count + 1:
                    exact -= 1
                if i >= L:
                    o = ord(s[i - L]) - 97  # character leaving the window
                    if freq[o] == count:
                        exact -= 1
                    freq[o] -= 1
                    if freq[o] == count:
                        exact += 1
                if i >= L - 1 and exact == u:
                    total += 1  # u letters, each exactly count times, fill all L positions
        return total

What the code is doing, line by line:

1. A window of length u · count with u letters at exactly count has no room for any other letter.
2. Only the entering and leaving letters change, so each step is O(1).

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• count larger than the string → 0.
• Single letter repeated.
• All 26 letters.

Complexity: O(26 · n) time, O(1) space.

Problem: Changing s[i] to t[i] costs |s[i] − t[i]|. Return the longest substring you can make equal within maxCost.

Solve it on LeetCode ↗

Constraints: 1 ≤ s.length ≤ 10⁵ · t.length == s.length · 0 ≤ maxCost ≤ 10⁶ · s and t consist of only lowercase English letters.

From brute force to the pattern: All substrings: O(n²); sliding window: O(n).

Spot it: Costs are non-negative, so a longer window never costs less → variable sliding window.

Why not another pattern? Checking every substring is O(n²).

Approach:

1. Extend right, adding its cost.
2. While the total exceeds maxCost, remove left's cost and move left.
3. Track the longest window.

class Solution:
    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
        left = total = best = 0
        for right in range(len(s)):
            total += abs(ord(s[right]) - ord(t[right]))
            while total > maxCost:
                total -= abs(ord(s[left]) - ord(t[left]))  # shrink from the left
                left += 1
            best = max(best, right - left + 1)
        return best

What the code is doing, line by line:

1. Non-negative costs make the window monotone.
2. Each index enters and leaves once.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• maxCost = 0 (only equal characters).
• Everything affordable.
• Nothing affordable → 0.

Complexity: O(n) time, O(1) space.

Problem: Return whether two indices i ≠ j exist with |i − j| ≤ indexDiff and |nums[i] − nums[j]| ≤ valueDiff.

Solve it on LeetCode ↗

Constraints: 2 ≤ nums.length ≤ 10⁵ · -10⁹ ≤ nums[i] ≤ 10⁹ · 1 ≤ indexDiff ≤ nums.length · 0 ≤ valueDiff ≤ 10⁹

From brute force to the pattern: Check all pairs within indexDiff: O(n · indexDiff); buckets make it O(n).

Spot it: The index limit is a sliding window of the last indexDiff values. To find a close value inside it in O(1), put values into buckets of width valueDiff + 1 (a hash map bucket → value): two values in one bucket are close, and a match can otherwise only be in a neighbouring bucket.

Why not another pattern? Comparing each value with the whole window is O(n · indexDiff); a sorted container works in O(n log k) but buckets are O(n).

Approach:

1. w = valueDiff + 1; bucket id x // w (floor division handles negatives).
2. For each value: if its bucket is occupied → true; if a neighbouring bucket holds a value within valueDiff → true.
3. Store the value in its bucket; drop nums[i − indexDiff]'s bucket so the window stays indexDiff wide.

class Solution:
    def containsNearbyAlmostDuplicate(self, nums: List[int], indexDiff: int, valueDiff: int) -> bool:
        width = valueDiff + 1  # any two values in one bucket differ by at most valueDiff
        buckets = {}  # bucket id -> the value in the window that falls there
        for i, x in enumerate(nums):
            b = x // width
            if b in buckets:
                return True
            if b - 1 in buckets and x - buckets[b - 1] <= valueDiff:
                return True
            if b + 1 in buckets and buckets[b + 1] - x <= valueDiff:
                return True
            buckets[b] = x
            if i >= indexDiff:
                del buckets[nums[i - indexDiff] // width]  # slide the window: that index is now too far back
        return False

What the code is doing, line by line:

1. Each bucket holds at most one value: a second one would already have returned true.
2. A close value is either in the same bucket or in a neighbour; anything two buckets away differs by more than valueDiff.
3. Removing the value from indexDiff positions back keeps only indices within range.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• valueDiff = 0 (exact duplicates).
• Negative numbers (floor division).
• indexDiff ≥ n.

Complexity: O(n) time, O(min(n, indexDiff)) space.