Topic 5: Sliding Window

Table of Contents

Key Intuition #

Key Intuition: Sliding window exploits the fact that many substring/subarray problems can be solved by maintaining a contiguous interval and moving its boundaries dynamically—either always of fixed size or adaptively to meet constraints.
The sliding window algorithm is mainly used to solve subarray problems, such as finding the longest or shortest subarray that meets certain conditions.
Typically, when we face a problem about subarrays or substrings, if we can answer these questions, we can consider using the sliding window algorithm:
1. what does the window represent?
2. when should we expand the window?
3. when should we shrink/contract the window?
4. when / how should we update the accumulated var / answer?
5. ask the following questions also:
  1. is it a fixed window or a dynamic window size?
  2. dynamic window: the visual imagery is that of a caterpillar moving along.

Canonical Questions #

Fixed-Size Sliding Window #

Objective: Maintain a window of exact length k and compute or collect something for each position as the window moves.

Problems #

Keep an heapq as an aux ds to help within the window (of fixed size k). Then just keep using that heapq to get the max value for every left pointer location that the window will live on.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
   import heapq

   class Solution:
      def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
         # Store (-value, index) to simulate max-heap
          heap = [(-nums[i], i) for i in range(k)]
          heapq.heapify(heap)

          res = [-heap[0][0]]  # just need to store the -val and the start idx for the window.

          for i in range(k, len(nums)):
             heapq.heappush(heap, (-nums[i], i))
             # Remove elements outside the window
              while (top_idx:=heap[0][1]) <= (left_idx:=i - k):
                 heapq.heappop(heap)

              res.append(-heap[0][0])

          return res

Code Snippet 1: Sliding Window Maximum (239)

Better Approach: Use a monotonic deque to keep track of the “current window” and left and right pointers. When shifting the window, flush out anything from the window based on idx. Then after inserting a new entry, if that is biggest, it will last k iterations, so we also flush out anything based on value (compared to the new max).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
   from collections import deque

   class Solution:
      def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
         # keeping indices here, this is a monotonically decreasing queue, so left to right is largest to smallest valued-indices
          dq = deque()
          res = []
          for idx, num in enumerate(nums):
             # remove those outside the window, it iterates "left to right"
              if dq and dq[0] <= (idx - k):
                 dq.popleft()
                 # since num comes into the window,
                 # if it's the max value, then the ones less than num are irrelevant, we remove them
              while dq and nums[dq[-1]] < num:
                 dq.pop()
                 dq.append(idx)
                 # at least it's the correct window size:
              if (idx >= k - 1):
                 res.append(nums[dq[0]])

          return res

Code Snippet 2: Sliding Window Maximum (239)

Maximum Number of Vowels in a Substring of Given Length (1456)

Use a fixed size window and just accumulate the max number of vowels seen. Handle incoming and outgoing in a bubbling fashion so everything is nice and linear.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
   class Solution:
      def maxVowels(self, s: str, k: int) -> int:
         vowels = set("aeiou")
         max_count = curr_count = sum(1 for c in s[:k] if c in vowels)

          for i in range(k, len(s)):
             outgoing = s[i - k]
             incoming = s[i]
              if outgoing in vowels:
                 curr_count -= 1
              if incoming in vowels:
                 curr_count += 1
                 max_count = max(max_count, curr_count)

          return max_count

Code Snippet 3: Maximum Number of Vowels in a Substring of Given Length (1456)

Pattern Extraction

Core Insight: Fixed-size sliding window of size $k$. Count vowels; slide by subtracting the exiting character and adding the entering character. Track the maximum count. Pattern Name: Fixed-Size Sliding Window with Counter Canonical Section: Sliding Window > Fixed-Size Window Recognition Signals:

Fixed window size $k$
“Maximum/minimum count of X in any window of size $k$”
$O(n)$ expected

Anti-Signals:

Variable window size – different pattern
Need the actual substring, not just the count – same algorithm, track start index

Decision Point: Fixed-size window with a simple counter. The simplest sliding window problem.

Pitfalls and Misconceptions

Trap: Recomputing the vowel count for each window from scratch. Why: $O(nk)$ instead of $O(n)$. The sliding window incremental update is $O(1)$ per step. Correction: Subtract exiting character’s contribution, add entering character’s contribution.

Problem Mutations

What if $k$ varied per query? (stress-tests: fixed $k$) Need to answer for multiple $k$ values. Precompute prefix counts of vowels for $O(1)$ per query.
What if you needed the minimum vowels instead of maximum? (stress-tests: max vs min) Same algorithm, track minimum instead of maximum.

AI usage disclosure Claude Opus 4.6 · content enrichment

Batch annotation for Maximum Number of Vowels in a Substring of Given Length.

Number of People Aware of a Secret (2327)

This one is a time simulation with a fixed sized sliding window. We could choose to represent that as a fixed-capacity deque or we could use a DP for it.

This is an example of a “window-maintained DP” and that’s the most optimal way of solving this problem.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
   ## M1: DP version (optimal)
   class Solution:
      def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:
         MOD = 10**9 + 7
         new_people_per_day = [0] * n
         new_people_per_day[0] = 1
         active_tellers_sum = 0
          for day in range(delay, n):
             active_tellers_sum += new_people_per_day[day - delay]
             new_people_per_day[day] = active_tellers_sum
              if day - forget + 1 >= 0: # if there are people who may forget
                 active_tellers_sum -= new_people_per_day[day - forget + 1]
          return sum(new_people_per_day[-forget:]) % MOD
       ## M2: pure time simulation, fixed size deque
   from collections import deque

   class Solution:
      def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:
         """
          We're modelling states and doing a time-sim. Let's just sim the 1000 max days

          Each day, we need to get the final number of people that know the secret

          final = new_people + old_people - people_who_forgot

          people that can say the secret at the beginning of each day will tell it to one person each

          secret_sayers = new_people = old_people - people_who_forgot - delayed_people
          """
         MOD = ( 10 ** 9 ) + 7
         days = deque([(0, 0), (1, 1)], maxlen=(forget + 1)) # to help us with 1-dx, (new_people, total) for each elem


          for i in range(2, n + 1):
             prev_new, old_people = days[- 1]
             people_who_forgot = days[1][0] if i - forget > 0 else 0
             delayed_people = sum((diff for diff, total in list(days)[max(len(days) - delay + 1, 0):i]))
             new_people = old_people - people_who_forgot - delayed_people
             new_total = (new_people + old_people - people_who_forgot) % MOD
             days.append((new_people, new_total))

          return days[-1][1]

Code Snippet 4: Number of People Aware of a Secret (2327)

Pattern Extraction

Core Insight: Sliding window DP: people who learn the secret on day $d$ can share it during days $[d + \text{delay}, d + \text{forget} - 1]$, then forget. Track new learners per day using a contribution window. Pattern Name: Sliding Window DP with Delayed Contribution Canonical Section: Sliding Window > Fixed-Size Window (DP variant) Recognition Signals:

Spreading/contribution with delay and expiry
Each entity contributes to a time range
Rolling window of active contributors

Anti-Signals:

No delay or expiry – simple exponential growth
Entities interact (not independent contributions) – more complex DP

Decision Point: The delay and forget parameters create a contribution window for each person. Track the sum of active contributors using a sliding window.

Pitfalls and Misconceptions

Trap: Simulating each person individually. Why: $O(n \cdot \text{days})$ if tracking each person. Aggregate by day instead. Correction: Track new_people[day] and use a rolling sum of active contributors.
Trap: Forgetting the modular arithmetic. Why: Numbers grow exponentially. Without % MOD, overflow occurs. Correction: Apply % (10^9 + 7) at every addition.

Problem Mutations

What if people could spread to variable numbers of new people? (stress-tests: one-to-one) Each contributor’s daily output becomes a multiplier in the contribution window.
What if the forget time were infinite? (stress-tests: finite forget) Contributors never stop sharing. Growth becomes exponential after the delay period.

AI usage disclosure Claude Opus 4.6 · content enrichment

Batch annotation for Number of People Aware of a Secret.

Maximum Sum of Subarray of Size K (643)

This is pretty straightforward, we just wanna accumulate best value by sliding a fixed sized window from left to right. Just the indices for the borders have to be careful about our accuracy of it.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
   class Solution:
     def findMaxAverage(self, nums: List[int], k: int) -> float:
       """
         Fixed size window that we will just slide and accumulate
         """
       window = nums[:k]
       curr_sum = best_sum = sum(window)
         for i in range(len(nums) - k):
           outgoing = nums[i]
           incoming = nums[i + k]
           curr_sum += (incoming - outgoing)
           best_sum = max(best_sum, curr_sum)

         return best_sum / k

Code Snippet 5: Maximum Sum of Subarray of Size K (643)

Pattern Extraction

Core Insight: Fixed-size sliding window of size $k$. Maintain running sum; slide by subtracting the exiting element and adding the entering element. Pattern Name: Fixed-Size Sliding Window with Running Sum Canonical Section: Sliding Window > Fixed-Size Window Recognition Signals:

Fixed window size $k$
“Maximum/average of any window of size $k$”
$O(n)$ expected

Anti-Signals:

Variable window size – different pattern
Need more than sum (e.g., median) – need different data structure within the window

Decision Point: The most basic fixed-size sliding window problem. Template problem for the pattern.

Pitfalls and Misconceptions

Trap: Using nested loops to compute each window sum from scratch. Why: $O(nk)$ instead of $O(n)$. Correction: Running sum: window_sum = window_sum - nums[i-k] + nums[i].

Problem Mutations

What if you needed the window median? (stress-tests: sum) Need two heaps or a sorted set within the window. Connects to LC 480.
What if $k$ could change per query? (stress-tests: fixed $k$) Precompute prefix sums. Window sum = prefix[i] - prefix[i-k]. $O(1)$ per query.

AI usage disclosure Claude Opus 4.6 · content enrichment

Batch annotation for Maximum Sum of Subarray of Size K.

Variable-Size / Expand-Contract Window (Pattern/Constraint Driven) #

Objective: Find shortest/longest subarray/substring satisfying a property, expanding and contracting dynamically. Caterpillar questions.

Problems #

Best Time to Buy and Sell Stock (121)

Idea here is to follow a Kadane-like approach (because we getting the max subarray sum), the “window” only expands and represents the buy dates in consideration.

1
2
3
4
5
6
7
8
9
    class Solution:
        def maxProfit(self, prices: List[int]) -> int:
            min_buy = float('inf')
            max_profit = 0
            for price in prices:
                min_buy = min(min_buy, price)
                profit = price - min_buy
                max_profit = max(max_profit, profit)
            return max_profit

Code Snippet 6: Best Time to Buy and Sell Stock (121)

Pattern Extraction

Core Insight: Track the minimum price seen so far. At each day, the profit is price - min_price. Track the global maximum profit. One pass, $O(1)$ space. Pattern Name: Single-Pass Min-Tracking Greedy Canonical Section: Sliding Window > Variable-Size Dynamic Window / 1D DP > Stock Trading Recognition Signals:

“Buy low, sell high” with one transaction
Selling must occur after buying (causal ordering)
$O(n)$ time, $O(1)$ space

Anti-Signals:

Multiple transactions allowed – state machine DP (LC 122)
Cooldown between transactions – three-state DP (LC 309)
At most $k$ transactions – $k$-dimensional DP (LC 188)

Decision Point: Single transaction = greedy min-tracking. Multiple transactions = state machine DP. The transaction count is the key discriminator within the stock family.

Pitfalls and Misconceptions

Trap: Reaching for DP or two-pointer when a greedy one-pass suffices. Why: Single transaction has optimal substructure that collapses to just tracking the running minimum. Correction: min_buy = min(min_buy, price); max_profit = max(max_profit, price - min_buy).
Trap: Computing all pairs of buy/sell days ($O(n^2)$). Why: Unnecessary. The running minimum already captures the best buy day for any given sell day. Correction: One pass with running minimum.

Problem Mutations

What if you could make unlimited transactions? (stress-tests: single transaction) State machine DP with hold/empty states. Connects to LC 122.
What if there’s a cooldown after selling? (stress-tests: no cooldown) Add a third state (cooldown). Connects to LC 309.
What if at most $k$ transactions are allowed? (stress-tests: unlimited/single) Add transaction count as a second DP dimension. Connects to LC 188.

AI usage disclosure Claude Opus 4.6 · content enrichment

Batch annotation for Best Time to Buy and Sell Stock.

Longest Substring Without Repeating Characters (3)

Keep expanding as much as possible until we get a duplicate. Then contract efficiently by using the same aux map object.

The optimisation here is when we use the last_seen to do huge jumps to the next sensible start point rather than doing one by one. It’s like a map for us.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
   class Solution:
       def lengthOfLongestSubstring(self, s: str) -> int:
           last_seen = {} # char to the index that it was last seen
           longest, left = 0, 0
           for right, char in enumerate(s):
               if found_duplicate:=(char in last_seen and last_seen[char] >= left):
                   # jump straight without needing to one-by-one sweep through
                   left = last_seen[char] + 1 # one after the previous instance of this char
                   last_seen[char] = right
                   longest = max(
                       longest,
                       right - left + 1 # curr length
                   )

           return longest

Code Snippet 7: Longest Substring Without Repeating Characters (3)

Pattern Extraction

Core Insight: Expand the window right; when a duplicate enters, shrink from the left until the window contains only unique characters. The window always represents the longest valid substring ending at right. Pattern Name: Variable-Size Sliding Window (Shrink on Violation) Canonical Section: Sliding Window > Variable-Size Dynamic Window Recognition Signals:

“Longest substring” with a uniqueness/frequency constraint
Contiguous elements (substring, not subsequence)
Window shrinks when constraint is violated
Hash map/set tracks window contents

Anti-Signals:

Subsequence, not substring – DP/greedy, not sliding window
Fixed window size – simpler fixed-window pattern
Need ALL valid substrings, not just the longest – may need different approach

Decision Point: “Longest substring with at most K distinct/unique characters” is the general family. K=all-unique (no repeats) is this specific case.

Pitfalls and Misconceptions

Trap: Using a set but forgetting to remove characters from the left when shrinking. Why: The set grows unboundedly and never reflects the actual window contents. Invalid characters remain, causing the window to shrink too aggressively or not enough. Correction: When advancing left, remove s[left] from the set.
Trap: Using an $O(n^2)$ approach checking each substring for uniqueness. Why: TLEs on long strings. The sliding window achieves $O(n)$ because each character enters and exits the window at most once. Correction: Maintain a hash map of character positions or a set of window contents.

Problem Mutations

What if you allowed at most $k$ repeating characters instead of zero? (stress-tests: uniqueness constraint) Use a Counter tracking frequencies; shrink when any frequency exceeds $k$. Generalises to LC 424 Longest Repeating Character Replacement. (notes)
What if you needed the shortest substring containing all unique characters of the input? (stress-tests: longest vs shortest) This is closer to LC 76 Minimum Window Substring. Same sliding window but shrink to find the minimum valid window.
What if characters were from a stream? (stress-tests: random access assumption) Sliding window is inherently online – it processes one character at a time from left to right. Works unchanged for streams.

AI usage disclosure Claude Opus 4.6 · content enrichment

Standardised annotation dropdowns for Longest Substring Without Repeating Characters generated via batch canonical enrichment pass. Review against personal solving experience and adjust.

Minimum Window Substring (76)

Given a source, we have to check if some conditions are met within the window w.r.t the target.

Use the target counter, keep expanding window (gathering) until all the frequencies are met. Then trim the fat as much as possible and keep tracking the min window formed. Caterpillar style.

Here we use two counts for unique characters: required and formed to guide our logic. These refer to the number of characters that have already met the matching conditions (whatever their required freq may be) – which helps us figure out when the window is valid or not.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
   from collections import Counter, defaultdict

   class Solution:
       def minWindow(self, s: str, t: str) -> str:
           if not t or not s or len(t) > len(s):
               return ""

           t_count = Counter(t)
           required = len(t_count) # the num of distinct chars to gather
           left, right = 0, 0
           formed = 0 # the num of chars that have the same freq as what the target requires
           window_counts = defaultdict(int)
           ans = float('inf'), None, None  # window length, left, right (inclusive)

           while right < len(s):
               c = s[right]
               window_counts[c] += 1

               if c in t_count and window_counts[c] == t_count[c]:
                   formed += 1

               # Try to contract the window until it's no longer valid
               while left <= right and formed == required:
                   if right - left + 1 < ans[0]: # if is a shorter substring:
                       ans = (right - left + 1, left, right)
                       window_counts[s[left]] -= 1
                       # only decrements if it's no longer valid
                   if s[left] in t_count and window_counts[s[left]] < t_count[s[left]]:
                       formed -= 1
                       left += 1

               right += 1

           return "" if ans[0] == float('inf') else s[ans[1]:ans[2]+1]

Code Snippet 8: Minimum Window Substring (76)

Pattern Extraction

Core Insight: Expand right to include all required characters, then shrink left to find the minimum valid window. Track satisfaction using a counter of remaining required characters. Pattern Name: Variable-Size Sliding Window (Expand then Shrink) Canonical Section: Sliding Window > Variable-Size Dynamic Window Recognition Signals:

“Minimum/shortest window containing all of X”
Two strings: source and target
Window must contain all characters of target (with counts)
$O(n)$ or $O(n + m)$ required

Anti-Signals:

Characters must appear in order – not a window problem, more like subsequence matching
Target has no duplicates and only checking containment – set-based approach might suffice

Decision Point: “Minimum window containing all characters of T” = expand right until valid, then shrink left to minimise. Track a remaining counter that hits zero when the window is valid. Interviewer Comms: “I use two pointers defining a window. I expand right until the window contains all required characters, tracked by a remaining counter. Then I shrink left while the window stays valid, updating the answer. $O(n)$ since each pointer moves right at most $n$ times.”

Pitfalls and Misconceptions

Trap: Using two Counters and comparing them at each step ($O(\Sigma)$ per comparison). Why: Comparing full counters is $O(|\Sigma|)$ per step, degrading total to $O(n \cdot |\Sigma|)$. Correction: Track a single integer remaining (count of unsatisfied unique characters). Decrement when a character reaches its required count; increment when it drops below.
Trap: Forgetting to handle duplicate characters in the target (e.g., t = "AAB"). Why: A simple set membership check doesn’t account for needing two A’s. The window must satisfy frequency requirements, not just presence. Correction: Use a Counter for the target; the window satisfies a character when its window count reaches the target count.
Trap: Not updating the answer while shrinking (only checking at expansion). Why: The minimum window is found during the shrinking phase. Checking only during expansion misses shorter valid windows. Correction: Update the answer inside the shrink loop, not outside it.

Problem Mutations

What if you needed the maximum window containing at most $k$ distinct characters? (stress-tests: all-of vs at-most) Shrink when distinct count exceeds $k$, not when satisfaction drops. Connects to LC 340.
What if the window had to be an anagram of $t$ (exact counts, no extra characters)? (stress-tests: superset vs exact) Fixed window size len(t); slide and compare counts. Connects to LC 438 Find All Anagrams. (ref notes)
What if there were multiple targets and you needed the minimum window containing any one of them? (stress-tests: single target) Run the algorithm for each target independently, or merge target requirements with OR semantics.

AI usage disclosure Claude Opus 4.6 · content enrichment

Standardised annotation dropdowns for Minimum Window Substring generated via batch canonical enrichment pass. Review against personal solving experience and adjust.

Find All Anagrams in a String (438) – ref this

Sliding Window with Hash/Counter Maintenance #

Objective: Maintain counts/frequencies or histograms as the window slides, to track frequency- or set-based constraints.

Problems #

Longest Repeating Character Replacement (424) Keep a char counter representing everything within the current window. Try to expand then contract until the window is valid, and take note of the length.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
   from collections import defaultdict
      class Solution:
        def characterReplacement(self, s: str, k: int) -> int:
            char_to_freq = defaultdict(int)

            # count of most freq char in the window, just need to track the number
            max_count = 0 # we do this because the number of edits = length of window - max_count
            max_length = 0
            left = 0

            for right in range(len(s)):
                curr_char = s[right]
                char_to_freq[curr_char] += 1
                max_count = max(max_count, char_to_freq[curr_char])

                # contract until threshold no longer violated:
                while threshold_violated:= ((right - left + 1) - max_count) > k:
                    left_char = s[left]
                    char_to_freq[left_char] -= 1
                    left += 1

                # valid threshold, register:
                max_length = max(max_length, (right - left + 1))

            return max_length

Code Snippet 9: Longest Repeating Character Replacement (424)

Pattern Extraction

Core Insight: The window is valid when window_size - max_freq < k= (at most $k$ characters need replacement). Expand right always; shrink left only when the window becomes invalid. Pattern Name: Variable-Size Sliding Window with Max-Frequency Tracking Canonical Section: Sliding Window > Variable-Size Dynamic Window Recognition Signals:

“Longest substring with at most K replacements”
Window validity depends on the most frequent character in the window
Need to track character frequencies within the window

Anti-Signals:

Replacements are not character-level (e.g., substring replacements) – different problem
Need to actually perform the replacements – this only counts the longest valid window

Decision Point: The key insight is that you DON’T need to decrement max_freq when shrinking. Since you’re maximising window size, a window can only beat the current best if max_freq increases. So max_freq is a high-water mark, and the window size minus this high-water mark determines validity.

Pitfalls and Misconceptions

Trap: Recalculating max_freq from scratch when shrinking the window. Why: Recomputing max frequency after each shrink is $O(26)$ per step, still $O(n)$ total. But more importantly, it’s unnecessary – the window can’t improve unless max_freq increases. Correction: Only update max_freq = max(max_freq, count[c]) on expansion. The stale high-water mark is safe for maximisation.
Trap: Using k as a running budget that decrements with each replacement. Why: This conflates the window validity condition with replacement counting. The condition is about the window STATE, not a depleting budget. Correction: Check window_size - max_freq < k= at each step. k is a constant threshold, not a budget.

Problem Mutations

What if you could replace at most $k$ characters but each replacement had a cost? (stress-tests: uniform cost assumption) Need DP or a more complex window tracking the total cost of replacements in the window.
What if the alphabet were much larger (e.g., Unicode)? (stress-tests: small alphabet) Same algorithm, but max_freq computation requires a hash map instead of a fixed-size array. Still $O(n)$.
What if instead of replacements, you could delete at most $k$ characters? (stress-tests: replacement vs deletion) With deletions, the remaining characters must be identical AND contiguous in the original string. The window validity condition changes. Connects to LC 1004 Max Consecutive Ones III.

AI usage disclosure Claude Opus 4.6 · content enrichment

Standardised annotation dropdowns for Longest Repeating Character Replacement generated via batch canonical enrichment pass. Review against personal solving experience and adjust.

Permutation in String (567)

Do character counting on fixed size windows and check if anything returns favourably. Solution here is slow (but passes all), optimise using fixed length char arrays if required.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
   from collections import Counter

      class Solution:
          def checkInclusion(self, s1: str, s2: str) -> bool:
              window_size = len(s1)
              if window_size > len(s2):
                  return False

              target_counter = Counter(s1)
              counter = Counter(s2[:window_size])
              right = window_size

              while right < len(s2):
                  if counter == target_counter:
                      return True

                  # Add new character
                  counter[s2[right]] += 1
                  # Remove old character
                  left_char = s2[right - window_size]
                  counter[left_char] -= 1
                  if counter[left_char] == 0:
                      del counter[left_char] # COUNTER GOTCHA: have to del key manually if <= 0 freq for a key

                  right += 1

              # Check the last window
              if counter == target_counter:
                  return True

              return False

Code Snippet 10: Permutation in String (567)

Pattern Extraction

Core Insight: Identical to Find All Anagrams (LC 438) but returns boolean: is there any window of size len(s1) in s2 that matches s1’s character frequencies? Pattern Name: Fixed-Size Sliding Window with Counter Matching Canonical Section: Sliding Window > Fixed-Size Window Recognition Signals:

“Is s1 a permutation of a substring of s2?” is equivalent to “does s2 contain an anagram of s1?”
Fixed window size = len(s1)

Anti-Signals:

Need all positions, not just existence – that’s LC 438

Decision Point: This is LC 438 with early return. Recognise the equivalence immediately.

Pitfalls and Misconceptions

Trap: Not recognising this as identical to Find All Anagrams. Why: The phrasing (“permutation of a substring”) sounds different from “anagram,” but they’re the same: same characters, same frequencies, any order. Correction: Apply the LC 438 fixed-window counter approach and return True on first match.

Problem Mutations

What if you needed the starting index of the permutation, not just existence? (stress-tests: boolean vs position) Return the index instead of True. Same algorithm.
What if s1 could be much longer than s2? (stress-tests: relative lengths) If len(s1) > len(s2), immediately return False. No window of the required size fits.

AI usage disclosure Claude Opus 4.6 · content enrichment

Standardised annotation dropdowns for Permutation in String generated via batch canonical enrichment pass. Review against personal solving experience.

Find All Anagrams in a String (438)

Keep track of the target character frequencies, then use a fixed size window to slide around and maintain a charcount properly.

M2 is my favourite even though it’s sub-optimal because it’s easier to implement it. Just remember the counter gotcha that if the frequency goes <= 0, that entry won’t automatically be removed so comparing two counters that should be the same may not return True.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
       from collections import Counter
       from typing import List

       class Solution:
           def findAnagrams(self, s: str, p: str) -> List[int]:
               n, m = len(s), len(p)
               if m > n:
                   return []

               target_counts = Counter(p)
               curr_counts = Counter()
               required = len(target_counts)
               formed = 0

               res = []
               left = 0
               for right in range(n):
                   char = s[right]
                   curr_counts[char] += 1
                   if char in target_counts and curr_counts[char] == target_counts[char]:
                       formed += 1

                   # flush until threshold no longer violated:
                   while right - left + 1 > m:
                       outgoing_char = s[left]
                       if outgoing_char in target_counts and curr_counts[outgoing_char] == target_counts[outgoing_char]:
                           formed -= 1
                           curr_counts[outgoing_char] -= 1
                       if curr_counts[outgoing_char] == 0:
                           del curr_counts[outgoing_char]
                           left += 1

                   if right - left + 1 == m and formed == required:
                       res.append(left)

               return res

Code Snippet 11: Find All Anagrams in a String (438) – uses char counters for required and formed

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
      from collections import Counter
      class Solution:
          def findAnagrams(self, s: str, p: str) -> List[int]:
              # p's anagrams in s
              n, m = len(s), len(p)
              if m > n:
                  return []

              target_counts = Counter(p)
              # window size is m, it will always be fixed.
              left = 0
              curr_counts = Counter(s[:m])
              res = []


              while left <= (n - m):
                  if is_anagram:=(curr_counts == target_counts):
                      res.append(left)

                  if (incoming_idx:=(left + m)) < n:
                      outgoing, incoming = s[left], s[incoming_idx]
                      curr_counts[incoming] += 1
                      curr_counts[outgoing] -= 1
                      if curr_counts[outgoing] <= 0:
                          del curr_counts[outgoing]

                  left += 1

              return res

Code Snippet 12: Find All Anagrams in a String (438) – suboptimal, simpler first-pass attempt

Pattern Extraction

Core Insight: Fixed-size sliding window of length len(p). Maintain a frequency counter for the window; when it matches the target counter, the window start is an anagram position. Pattern Name: Fixed-Size Sliding Window with Counter Matching Canonical Section: Sliding Window > Fixed-Size Window Recognition Signals:

Fixed window size (len(p))
“Find all positions where window matches a pattern” (anagram = same character frequencies)
$O(n)$ expected with $O(1)$ counter comparison per step

Anti-Signals:

Pattern matching with order (not anagram) – use KMP, Rabin-Karp, or Z-algorithm
Variable window size – different sliding window variant

Decision Point: Anagram detection = fixed-size window with frequency matching. Substring search = KMP or rolling hash. The lack of ordering constraint is what makes this a window/counter problem rather than a string matching problem.

Pitfalls and Misconceptions

Trap: Recomputing the frequency counter from scratch for each window position. Why: $O(n \cdot m)$ where $m = len(p)$. The sliding window update is $O(1)$: subtract the exiting character, add the entering character. Correction: Incrementally update the window counter and compare with the target counter.
Trap: Comparing two Counter objects at each step ($O(26)$ per comparison). Why: Counter comparison is $O(|\Sigma|)$. Better to track a matches count of satisfied characters. Correction: Track how many characters have matching frequencies. When matches = len(target_counter)=, it’s an anagram.

Problem Mutations

What if you only needed to check if ANY anagram exists (not all positions)? (stress-tests: all vs any) Same algorithm, early return on first match. Or use LC 567 Permutation in String, which is the boolean version.
What if the pattern could have wildcards? (stress-tests: exact matching) Wildcards match any character, reducing the number of constrained positions. Adjust the match count accordingly.
What if the “anagram” definition included character ordering within groups? (stress-tests: pure frequency matching) Then it’s closer to substring matching. Different algorithm entirely.

AI usage disclosure Claude Opus 4.6 · content enrichment

Standardised annotation dropdowns for Find All Anagrams in a String generated via batch canonical enrichment pass. Review against personal solving experience.

Contains Duplicate II (219)

Kind of straightforward here as well.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
   class Solution:
       def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
           if len(nums) <= 1 or k < 1:
               return False

           window = set(nums[:(k + 1)])
           expected_first_window_length = k + 1 if len(nums) >= k + 1 else len(nums)
           if len(window) < expected_first_window_length:
               return True

           for idx in range(k + 1, len(nums) ):
               incoming, outgoing = nums[idx], nums[idx - (k + 1)]
               window.discard(outgoing)

               if incoming in window:
                   return True

               window.add(incoming)

           return False

Code Snippet 13: Contains Duplicate II (219) – maintaining a fixed set for the sliding window

1
2
3
4
5
6
7
8
      class Solution:
          def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
              index_map = {}
              for i, num in enumerate(nums):
                  if num in index_map and i - index_map[num] <= k:
                      return True
                  index_map[num] = i
              return False

Code Snippet 14: Contains Duplicate II (219) – Using a last-seen map

Pattern Extraction

Core Insight: Maintain a set of the last $k$ elements (sliding window of size $k$). If a new element is already in the set, duplicates exist within distance $k$. Pattern Name: Fixed-Size Sliding Window with Hash Set Canonical Section: Sliding Window > Fixed-Size Window Recognition Signals:

“Duplicate within distance $k$” (proximity-constrained duplicate detection)
Fixed window size $k$
Hash set for $O(1)$ membership checking within the window

Anti-Signals:

No distance constraint – just use a set for all elements (LC 217)
Need the actual duplicate pair, not just existence – track values and indices
Value-based proximity (within $t$ value difference) – sorted set or bucket sort. Connects to LC 220

Decision Point: Distance constraint = sliding window with set. No constraint = global set. Value constraint (within $t$) = sorted set or bucket sort.

Pitfalls and Misconceptions

Trap: Using a hash map of value-to-index and checking abs(i - map[val]) < k=. Why: Works but is unnecessarily complex. A sliding window set of size $k$ is cleaner. Correction: Maintain a set; evict the element at i - k when the window exceeds size $k$.

Problem Mutations

What if the constraint were on VALUE difference (not just equality) within distance $k$? (stress-tests: equality vs range) Need a sorted set (SortedList) to find elements within value range in $O(\log k)$ per step. Connects to LC 220 Contains Duplicate III.
What if the array were a stream? (stress-tests: static array) The sliding window approach is inherently online. Works unchanged for streams.

AI usage disclosure Claude Opus 4.6 · content enrichment

Standardised annotation dropdowns for Contains Duplicate II generated via batch canonical enrichment pass. Review against personal solving experience.

Dual/Multiple Windows (Two Pointers / Two Windows) #

Objective: Use two simultaneous windows to partition or maintain distinct constraints across intervals.

Problems #

Subarrays with K Different Integers (992)

The key insight here is that inorder to count subarrays with exactly k distinct elements, exactly_k = atMostK(nums, k) - atMostK(nums, k - 1), so we have to figure out how to get atMost(k).

To get the number of good subarrays, realise that the window is just going to be holding the “next possible ending element” to the subarray, so we can just sum up the window size each time.

The metric to use to expand and contract then becomes just “the number of distinct elements within the window”.

We do use a 2pointer (left, right) approach to search through for the counting of atMostK(k)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
   from collections import defaultdict
   from typing import List

   class Solution:
       def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:

           def atMostK(k):
               count = defaultdict(int)
               left = 0
               res = 0
               distinct = 0
               for right, val in enumerate(nums):
                   if count[val] == 0:
                       distinct += 1
                       count[val] += 1
                   while distinct > k:
                       count[nums[left]] -= 1
                       if count[nums[left]] == 0:
                           distinct -= 1
                           left += 1
                           res += right - left + 1
               return res

           return atMostK(k) - atMostK(k - 1)

Code Snippet 15: Subarrays with K Different Integers (992)

Pattern Extraction

Core Insight: exactly(K) = atMost(K) - atMost(K-1). The “at most K distinct” problem has a clean sliding window solution; the “exactly K” problem doesn’t. The subtraction trick converts the latter to two instances of the former. Pattern Name: At-Most-K Subtraction Trick Canonical Section: Sliding Window > At-Most-K Pattern Recognition Signals:

“Exactly K distinct” elements in a subarray/substring
Counting valid subarrays/substrings (not finding the longest)
The “at most K” version is solvable with a standard sliding window

Anti-Signals:

“At most K” directly – no subtraction needed, just one sliding window pass
“At least K” – different decomposition, may need a different approach
Non-contiguous (subsequences) – sliding window doesn’t apply

Decision Point: “Exactly K distinct” is almost always solved via the at-most subtraction trick. Recognise this immediately when you see “exactly K” in a counting context.

Pitfalls and Misconceptions

Trap: Trying to maintain exactly $K$ distinct values in the window directly. Why: When a character leaves and distinct count drops to $K-1$, you don’t know how far to expand right to restore it. The window doesn’t have a clean “violation triggers shrink” structure. Correction: Use atMost(K) - atMost(K-1) and implement atMost with a standard sliding window.
Trap: Counting subarrays incorrectly in the atMost helper. Why: For each right, the number of valid subarrays ending at right is right - left + 1 (all subarrays from any start in [left, right] to right). Correction: Accumulate right - left + 1 at each step of the right pointer.

Problem Mutations

What if you needed the longest subarray with exactly $K$ distinct integers? (stress-tests: count vs longest) Can still use the atMost(K) window to find the longest window with at most $K$ distinct, but ensuring exactly $K$ requires tracking distinct count within the window. Two-pointer directly with a distinct counter works.
What if $K$ were 1 (subarrays with exactly 1 distinct element)? (stress-tests: K value) Degenerates to counting maximal runs of identical elements. Each run of length $m$ contributes $m(m+1)/2$ subarrays.
What if elements could be removed and you needed to recompute? (stress-tests: static array) Sliding window doesn’t support arbitrary deletions. Would need a more complex data structure.

AI usage disclosure Claude Opus 4.6 · content enrichment

Standardised annotation dropdowns for Subarrays with K Different Integers generated via batch canonical enrichment pass. Review against personal solving experience and adjust.

TODO Longest Substring with At Most K Distinct Characters (340) (paid question)

TODO Circular or Wrapping Window ⭐️ #

Objective: Treat the array/string as circular, allowing wrap-around windows.

Problems #

TODO Maximum Sum Circular Subarray (918)

Monotonic-Deque Window (Optimized Min/Max/Medians) #

Objective: Maintain a monotonic data structure to support efficient queries like min, max, or median inside a window.

Problems #

Sliding Window Maximum (239)

Use a monotonic deque to keep track of the “current window” and left and right pointers. When shifting the window, flush out anything from the window based on idx. Then after inserting a new entry, if that is biggest, it will last k iterations, so we also flush out anything based on value (compared to the new max).

It’s the flushing here that allows us to maintain the monotonic property, which is what this canonical type is all about.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
    from collections import deque

    class Solution:
        def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
            # keeping indices here, this is a monotonically decreasing queue, so left to right is largest to smallest valued-indices
            dq = deque()
            res = []
            for idx, num in enumerate(nums):
                # remove those outside the window, it iterates "left to right"
                if dq and dq[0] <= (idx - k):
                    dq.popleft()
                # since num comes into the window,
                # if it's the max value, then the ones less than num are irrelevant, we remove them
                while dq and nums[dq[-1]] < num:
                    dq.pop()
                dq.append(idx)
                # at least it's the correct window size:
                if (idx >= k - 1):
                    res.append(nums[dq[0]])

            return res

Code Snippet 16: Sliding Window Maximum (239)

TODO HARD Shortest Subarray with Sum ≥ K (862)
TODO HARD Sliding Window Median (480)

Prefix-Sum Assisted Window (Hybrid) #

Objective: Combine sliding windows with prefix sums or cumulative frequency arrays for efficient subarray checks.

Problems #

Subarray Sum Equals K (560)

This is a subarray sum, which is a classic question for prefix-sum approaches and it also happens to be a range sum question.

This is somewhat like a compressed DP problem, yet it’s better described as a prefix sum / range sum solution.

Some key pointers:

negative numbered elements are also a thing, that’s why we’re only accumulating the curr_sum and seeing how many other complements could build up to this.
that’s why we only store the freq of partial sums within the prefix_count and the partials following the ordering that only the elements to the left of the current element being considered have helped to form that partial – so we’re just storing “how many times have I seen this partial sum before” within our aux.
each time we see the same partial sum, it represents a different starting point – a different continguous subarray.
SO prefix_count[complement] => how many valid starting points are there?

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
   class Solution:
       def subarraySum(self, nums, k):
           prefix_count = {0: 1}  # "Seen prefix sum 0 once (before array starts)"
           curr_sum = 0
           result = 0

           for num in nums:
               curr_sum += num  # Extend the prefix

               # The magic question:
               # "If I remove a prefix of sum (curr_sum - k),
               #  what's left will sum to k"
               complement = curr_sum - k

               # "How many prefixes of this sum have I seen?"
               # Each one represents a different subarray ending here
               if complement in prefix_count:
                   result += prefix_count[complement]

               # Record this prefix sum for future use
               prefix_count[curr_sum] = prefix_count.get(curr_sum, 0) + 1

           return result

Code Snippet 17: Subarray Sum Equals K (560)

Pattern Extraction

Core Insight: Prefix sum + hash map. If prefix[j] - prefix[i] = k, then subarray [i+1, j] sums to $k$. Count occurrences of prefix[j] - k in a running hash map of prefix sums. Pattern Name: Prefix Sum with Hash Map Complement Search Canonical Section: Sliding Window > Prefix Sum + Hash Map (not a sliding window) Recognition Signals:

“Count subarrays with sum equal to $k$”
Elements can be negative (rules out sliding window)
$O(n)$ expected
The complement search mirrors Two Sum

Anti-Signals:

All elements are non-negative – sliding window works and might be preferred
Need the actual subarrays, not just the count – hash map gives count, need backtracking for actual subarrays
Sum at most $k$ (inequality) – prefix sum + sorted structure, not hash map

Decision Point: Negative elements break the sliding window’s monotonicity. Prefix sum + hash map works regardless of sign. This is “Two Sum on prefix sums.”

Pitfalls and Misconceptions

Trap: Trying to use a sliding window when elements can be negative. Why: Sliding window relies on the invariant that extending the window increases the sum (or shrinking decreases it). Negative elements break this monotonicity. Correction: Use prefix sum + hash map. Not a sliding window problem.
Trap: Not initialising the hash map with {0: 1}. Why: A subarray from index 0 to $j$ with sum $k$ means prefix[j] = k, so we need prefix[j] - k = 0 to be in the map. Without the initialisation, these subarrays are missed. Correction: prefix_count = {0: 1} (or defaultdict(int) with prefix_count[0] = 1).

Problem Mutations

What if you needed the longest subarray with sum $k$ (not count)? (stress-tests: count vs length) Store the FIRST index where each prefix sum occurs. Longest subarray = max over j - first_index[prefix[j] - k]. Connects to LC 325.
What if all elements were non-negative? (stress-tests: sign constraint) Sliding window works: expand right to increase sum, shrink left to decrease. Simpler than prefix sum for this special case.
What if the target were a range $[lo, hi]$ instead of exact $k$? (stress-tests: exact vs range) Need a sorted structure (balanced BST) to count prefix sums in a range. $O(n \log n)$.

AI usage disclosure Claude Opus 4.6 · content enrichment

Standardised annotation dropdowns for Subarray Sum Equals K generated via batch canonical enrichment pass. Review against personal solving experience.

Multi-Dimensional Sliding Window (2D / Higher Dimensional) #

Objective: Windows defined in multiple dimensions, typically 2D arrays or matrices. Window sliding can occur row-wise and column-wise.

Problems #

Maximum Sum Rectangle in a 2D Matrix (compress rows + 1D sliding window / Kadane’s variant) TODO Hard Maximum Sum of Rectangle No larger than K (363)
Moving Average in a Matrix/Grid (sliding block)

Time-Interval / Stream Windows #

Objective: Window defined not by index but by time intervals (last T seconds/minutes). Widely used in streaming/event problems.

Problems #

TODO easy Moving Average from Data Stream (346) (paid) (time-based variant)
TODO Design Hit Counter (362) (paid)

Greedy Partition / Cover Windows #

Objective: Grow window until a covering property is satisfied, then “close off” and begin the next segment. Often used to partition sequences greedily.

Problems #

⭐️Partition Labels (763)

This problem fundamentally relies on greedy expansion and two-pointer/caterpillar technique. It can also be viewed as interval partitioning, where intervals are letter occurrences. The solution merges overlapping intervals greedily.

This is really a 2 pointer caterpillar type but we can make life easy by knowing when is the last idx when a particular character appears. This can help us determine when to segment (and how many within the segment).

simpler than it looks actually, the main thing is the “greedy” part which is we need to expand then consume like a caterpiller, how far to expand? until all within this window don’t have their last occurrence somewhere outside of the window. It’s like some sort of linear dependency culling thing going on.

Greedy framework:

Greedy Choice: At any point, expand the partition to include the last occurrence of the current character.
Feasibility Check: You can end a partition only when all letters inside it don’t appear beyond the partition end.
Optimal Substructure: The global optimum (max partitions) arises from correctly identifying all partition boundaries greedily without backtracking.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
   from typing import List

    class Solution:
        def partitionLabels(self, s: str) -> List[int]:
            # we can save time by doing the pre-calculations, this dictcomp will just keep getting updated and give us the last idx
            last_occurrence = {c: i for i, c in enumerate(s)}
            partitions = []

            # use two pointers, move like a caterpillar
            start = 0
            end = 0

            for i, c in enumerate(s):
                end = max(end, last_occurrence[c])
                if i == end: # no more to consider (this letter is covered), we can segment this off
                    size = i - start + 1
                    partitions.append(size)
                    start = i + 1

            return partitions

Code Snippet 18: Partition Labels (763)

Pattern Extraction

Core Insight: Find the last occurrence of each character. Greedily extend the current partition to include the last occurrence of every character in it. When the current index reaches the partition boundary, close the partition. Pattern Name: Greedy Interval Merging with Last-Occurrence Tracking Canonical Section: Sliding Window > Interval-Based Partitioning (also Greedy) Recognition Signals:

“Partition string into maximum parts such that each character appears in at most one part”
Greedy partitioning with reach/boundary extension
Precompute last occurrences

Anti-Signals:

Minimum partitions (not maximum) – different problem, likely DP
Characters can overlap between partitions – not a valid partition constraint

Decision Point: “Each character in at most one part” means each character’s range [first, last] defines a constraint. Merge overlapping ranges greedily. This is interval merging applied to character ranges.

Pitfalls and Misconceptions

Trap: Not precomputing last occurrences, instead scanning ahead each time. Why: Scanning ahead for each character’s last occurrence is $O(n^2)$. Precomputing is $O(n)$. Correction: One pass to build last = {c: i for i, c in enumerate(s)}, then one pass to partition.
Trap: Closing the partition too early – when the current character’s last occurrence is reached but other characters in the partition still have later occurrences. Why: The partition boundary must accommodate ALL characters in the partition, not just the current one. Correction: boundary = max(boundary, last[c]) for each character. Close partition only when i = boundary=.

Problem Mutations

What if you needed the minimum number of partitions with the same constraint? (stress-tests: max vs min) Minimum partitions = 1 (the whole string). The problem is interesting only as maximum partitions.
What if the constraint were that each character appears in at most $k$ parts? (stress-tests: at most 1) More complex. Need to track how many parts each character spans and allow up to $k$ splits. Likely DP.
What if the input were an array of integers instead of characters? (stress-tests: alphabet size) Same algorithm, but last is a hash map instead of a size-26 array. No structural change.

AI usage disclosure Claude Opus 4.6 · content enrichment

Standardised annotation dropdowns for Partition Labels generated via batch canonical enrichment pass. Review against personal solving experience.

Maximum Balanced Shipments (3638)

This is just greedy.This is just a greedy approach where as soon as we get something valid, we mark that as shipment. We’re just keeping track of the overall count and the per-window max_shipment

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
    class Solution:
        def maxBalancedShipments(self, weight: List[int]) -> int:
            """
            n parcels in a straight line, weights given

            balanced = if last parcel is less than max weight among all parcels in shipment

            parcels may be unshipped

            max possible balanced shipments

            do things greedily, as soon as i can dedicate a shipment, i ship it off
            we just do it as a sliding window of sorts then just contract all the way
            """
            # init things
            idx = 0
            shipment_max = weight[idx]
            idx += 1

            n = len(weight)
            count = 0

            while idx < n:
                if weight[idx] < shipment_max: # can dispatch
                    count += 1
                    # break if out of bounds
                    if not((idx + 1)  < n):
                        break
                    # set new shipment package as the max, double skip the idx
                    shipment_max = weight[idx + 1]
                    idx = idx + 2
                else:
                    shipment_max = max(shipment_max, weight[idx])
                    idx += 1

            return count

Code Snippet 19: Maximum Balanced Shipments (3638)

Pattern Extraction

Core Insight: Greedy partitioning using last-occurrence tracking – similar to Partition Labels (LC 763). Extend the current shipment’s boundary to include the last occurrence of every item type within it. Pattern Name: Greedy Interval Merging with Last-Occurrence Tracking Canonical Section: Sliding Window > Interval-Based Partitioning Recognition Signals:

“Maximum number of balanced partitions” where each partition must contain complete groups
Precompute last occurrences, greedily extend partition boundary

Anti-Signals:

Partitions don’t need to be “balanced” – simpler partitioning

Decision Point: Same pattern as Partition Labels. The “balanced” constraint maps to “each element type appears in at most one partition.”

Pitfalls and Misconceptions

Trap: Not precomputing last occurrences. Why: Without knowing where each element’s last occurrence is, you can’t determine the partition boundary. Correction: One pass to build last = {elem: i for i, elem in enumerate(arr)}.

Problem Mutations

What if elements could span multiple partitions (at most $k$)? (stress-tests: at most 1) More complex tracking. Need to count how many partitions each element spans.

AI usage disclosure Claude Opus 4.6 · content enrichment

Batch annotation for Maximum Balanced Shipments.

Minimum Number of People to Teach (1733)

This question is interesting because it’s like a greedy counting problem but if we don’t read the question properly and make premature assumptions, we might think it to be a graph coverage / connectivity problem.

In reality, this question is just about doing some specific preprocessing by relying on the observation that we may have problematic friendships where two people are friends but they may not have a common language they can speak between them. It’s only these problematic friendships we should be identifying and considering to teach languages to. Rest of it is just brute force.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
   from collections import defaultdict

    class Solution:
        def minimumTeachings(self, n, languages, friendships):
            uid_to_langs = {uid + 1: set(langs) for uid, langs in enumerate(languages)}
            problem_candidates = set()
            for u, v in friendships:
                if uid_to_langs[u].isdisjoint(uid_to_langs[v]):
                    problem_candidates.add(u)
                    problem_candidates.add(v)
            return min(
                sum(lang not in uid_to_langs[uid] for uid in problem_candidates)
                for lang in range(1, n + 1)
            )

Code Snippet 20: Minimum Number of People to Teach (1733)

Pattern Extraction

Core Insight: For each candidate language, count how many people need to learn it so that all friendships have a common language. The answer is the minimum across all candidate languages. Pattern Name: Brute-Force over Candidates with Constraint Checking Canonical Section: Sliding Window > Interval-Based Partitioning (or standalone) Recognition Signals:

“Minimum people to teach a language so all friends can communicate”
Small number of languages (constraint allows iterating over all)
For each candidate, count how many people in “broken” friendships don’t know it

Anti-Signals:

Large number of languages – brute force over candidates is too slow

Decision Point: The constraint ($\leq 500$ languages) makes brute force over all candidate languages feasible. For each language, check which friendships are “broken” and how many people need to learn it.

Pitfalls and Misconceptions

Trap: Teaching a language to ALL people who don’t know it, not just those in broken friendships. Why: Only people in friendships where neither speaks a common language need to learn. Teaching others is wasted. Correction: First identify broken friendships, then for each candidate language, count how many people in broken friendships don’t know it.

Problem Mutations

What if the number of languages were large ($10^5$)? (stress-tests: small language count) Can’t iterate over all languages. Need a smarter selection strategy.

AI usage disclosure Claude Opus 4.6 · content enrichment

Batch annotation for Minimum Number of People to Teach.

Smallest Subsequence Covering Constraints (variations on covering window problems)

Probabilistic / Approximate Windows (Advanced / Streaming) #

Objective: Apply statistical data sketches or approximate counters to maintain sliding window summaries efficiently in data streams.

Problems #

Count-Min Sketch over Sliding Window (streaming algorithms literature)
Bloom Filters with Time-Based Expiration (approximate membership in sliding window)

SOE #

Forgetting to shrink window when constraint is violated (leads to TLE or logic bugs)
When rejection Logic for the current window: either too aggressive or too lenient.
Wrong initialization or clearing of counts/trackers when window moves
Wrong pointer updates leading to infinite loop or incorrect answers
depending on implementation, if we’re doing a buffer filling approach, check if the remnants in the buffer have been processed (flush the buffer) before making conclusions
GOTCHAs in collections.Counter use. If a key’s value is decremented to <= 0, then the key will not automatically get removed from the dict.

Boundary Semantics #

Using wrong comparison operator for window validity: while right - left > k= vs while right - left + 1 > k depending on whether k is window size or max allowed count.
Processing the answer at the wrong point in the loop: updating the answer BEFORE shrinking (captures invalid windows) vs AFTER shrinking (misses valid ones). The correct placement depends on whether the problem asks for max or min.

Counter Tracking #

Decrementing a counter entry to 0 and then comparing with another Counter: the zero-valued key persists and breaks equality checks. Use del counter[key] when count reaches 0, or use +counter to strip non-positive entries.
Tracking “number of satisfied characters” incorrectly: incrementing the satisfied count when a character count REACHES the target, but forgetting to decrement satisfied when it DROPS BELOW the target during shrinking.

AI usage disclosure Claude Opus 4.6 · content enrichment

SOE entries synthesised from recurring sliding window mistakes. Review against personal experience.

Decision Flow #

Is the window fixed-size? → Use fixed window moving rightwards.
Is the window size variable based on constraints? → Expand and contract with two pointers/maps.
Is constraint based on counts or frequency? → Use dict/Counter to maintain sliding statistics.
Need to handle wrapping/circularity? → Consider index modulus or simulate circular extension.
need to handle unique characters and their counts? -> keep track of both the absolute counts as well as the counts for the distinct characters.

Styles, Tricks and Boilerplate #

Boilerplate #

Basic Boilerplate #

1
2
3
4
5
6
7
8
def sliding_window(nums, k):
    left = 0
    for right in range(len(nums)):
        # ... add nums[right] to current window ...
        while window_invalid_condition():
            # ... remove nums[left] from current window ...
            left += 1
        # ... process window if needed ...

Code Snippet 21: Basic Boilerplate

Fixed Window Boilerplate #

1
2
3
4
5
for i in range(len(nums)):
    # add nums[i]
    if i >= k:
        # remove nums[i - k]
    # window of size k: process as needed

Hash/Counter Window Boilerplate #

1
2
3
4
5
6
7
8
9
from collections import Counter
count = Counter()
left = 0
for right, x in enumerate(nums):
    count[x] += 1
    while needs_shrinking(count):
        count[nums[left]] -= 1
        left += 1
    # process stats via the counter here

Code Snippet 22: Hash/Counter Window Boilerplate

Python Recipes: #

we can pass in iterables to set and list construction. so we can directly do vowels = set("aeiou"). This works great for us.

Tricks #

accumulate ans as useful tuples sometimes it makes sense for us to keep tuples of relevant info for our answer. For example, in Minimum Window Substring (76), it makes sense for us to store the ans as (window_length, left, right) which is the best answer we’ve accumulated so far. It’s a minimisation problem, so it’s useful for us – the final answer we need to give is the substring itself so we can just splice it using the points (s[left:right + 1]) as well.

Kadane’s Algorithm for subarray sums/etc kadane-algorithm #

See Kadane’s Algorithm in the Greedy Algorithms topic for the full boilerplate and explanation.

TODO KIV #

[ ] Undone canonicals #

these are the canonicals that haven’t been done at all.

Circular window

TODO Maximum Sum Circular Subarray (918) KIV this brute-forced attempt

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
      class Solution:
          def maxSubarraySumCircular(self, nums: List[int]) -> int:
              """
              Non empty subarrays of nums which is circular
              Lengths from 1 to len(nums) but circular.

              We seek the max possible sum:
              """
              best_sum = -float('inf')
              n = len(nums)
              for window_size in range(1, n):
                  window = nums[:window_size] # starting idx = 0,
                  curr_sum = sum(window)
                  best_sum = max(curr_sum, best_sum)

                  for idx in range(n):
                      outgoing, incoming = idx, (idx + window_size)

                      # overlapping:
                      if incoming > outgoing and (outgoing - incoming) != window_size:
                          continue

                      curr_sum += (nums[incoming] - nums[outgoing])
                      best_sum = max(curr_sum, best_sum)

              return best_sum

Code Snippet 23: Maximum Sum Circular Subarray (918)

and this critique of it, including the modified kadane algo that solves this in linear time.

Maximum Sum Circular Subarray - Issues and Optimal Solution

The provided solution attempts a brute-force circular sliding window approach for the problem Maximum Sum Circular Subarray, but it contains multiple logical and implementation issues. Below are the problems and a thoroughly explained, corrected, and optimal solution based on Kadane’s algorithm adapted for circular arrays.

Issues in Your Code

Circular indexing logic flawed:
- The code slices nums[:window_size] for the initial window, but the iteration for idx in range(n) and usage of indices outgoing=idx and incoming=idx+window_size can go out of bounds.
- The overlapping condition if incoming > outgoing and (outgoing - incoming) ! window_size: continue= is incorrect and fails to handle wrap-around circular conditions.
- Does not correctly apply modulo for circular indexing.
Impractical brute force for all subarray sizes:
- The outer loop for all window_size from 1 to n is $O(n)$, with inner loops leading to $O(n^2)$ complexity, which will TLE for large inputs.
No special handling for the circular wrap-around sum:
- Simply sliding a window as if circular without careful modular arithmetic is error-prone.

Optimal Approach Explanation (Kadane’s Algorithm Modified for Circular Array)

Key insight: The maximum circular subarray sum is the maximum of:

Standard max subarray sum (no wrapping) — found with classic Kadane’s algorithm.
Circular max subarray sum — total sum of array minus minimum subarray sum (the subarray that when removed gives max wrapped sum).

Special case: If all numbers are negative, max subarray sum (Kadane) is the answer; because circular calculation would yield 0 or invalid sums.

Optimal Code (Python)

      from typing import List

      class Solution:
          def maxSubarraySumCircular(self, nums: List[int]) -> int:
              def kadane(arr):
                  # Standard Kadane to find max subarray sum
                  max_ending_here = max_so_far = arr
                  for x in arr[1:]:
                      max_ending_here = max(x, max_ending_here + x)
                      max_so_far = max(max_so_far, max_ending_here)
                  return max_so_far

              total_sum = sum(nums)
              max_kadane = kadane(nums)  # Max subarray sum (non-circular)

              # To find min subarray sum, invert signs and apply Kadane
              inverted_nums = [-x for x in nums]
              max_inverted_kadane = kadane(inverted_nums)
              min_subarray_sum = -max_inverted_kadane

              # If all numbers are negative, total_sum == min_subarray_sum
              if total_sum == min_subarray_sum:
                  return max_kadane  # Max subarray without wrap

              # Otherwise max circular sum is total_sum - min_subarray_sum
              max_circular = total_sum - min_subarray_sum

              return max(max_kadane, max_circular)

Why This Works

Kadane’s algorithm efficiently finds the max in linear time.
Finding the min subarray sum by inverting signs and reusing Kadane is clever and clean.
The difference total_sum - min_subarray_sum gives the max sum of the wrapped portion (subarray that goes end-to-start circularly).
Properly handles negative edge cases.

Complexity

Time: $O(n)$ Linear scan for Kadane and totals.
Space: $O(n)$ due to creating the inverted list (can be optimized to $O(1)$ by in-place inversion or running Kadane on the fly).

Summary

Your brute-force sliding windows for all sizes is inefficient and incorrect for circular indexing.
The Kadane + minimum subarray approach is the standard optimal method accepted in practice and competitive programming.
Highly recommended to adopt the above approach for correctness and performance.

If needed, help can be provided for optimizing or explaining Kadane variants, or adapting to edge cases.

[ ] Undone Questions within Canonicals #

expand-contract window
1. Longest Subarray with Sum at Most K (325) [paid question though]
dual/multiple windows
1. TODO Longest Substring with At Most K Distinct Characters (340) (paid question)
Monotonic-Deque Window
1. TODO HARD Shortest Subarray with Sum ≥ K (862)
2. TODO HARD Sliding Window Median (480)
Prefix-assisted window
1. TODO Shortest Subarray with Sum at Least K (862)
2. TODO Maximum Size Subarray Sum Equals K (325) (paid question)

Multi-Dimensional Sliding Window

see questions within this response:

Multi-Dimensional Sliding Window Questions

Here are more problems that fall under the canonical type Multi-Dimensional Sliding Window (2D / Higher Dimensional), including the classic example you mentioned, with brief notes on approach:

Multi-Dimensional Sliding Window Problems

Problem Name & Link	Notes / Approach Summary
Maximum Sum of Rectangle No Larger Than K (LC 363)	Fix row boundaries, compress columns to 1D array, use 1D max subarray sum ≤ k (prefix sums + balanced tree / binary search)
Maximum Sum Rectangle in 2D Matrix (Kadane variant)	Fix pairs of rows, sum columns between rows, run Kadane’s max subarray on compressed 1D array
Moving Average in a Matrix/Grid (Sliding Block)	Fixed-size sliding window (block) over 2D array, maintain sums with prefix sums or sliding window updates
Sliding Window Maximum in 2D (Grid version)	Apply 1D sliding window max on every row, then column-wise max on intermediate result
Number of Submatrices That Sum to Target (LC 1074)	Similar to max sum rectangle, fix row pairs, compress columns, use prefix sums + hashmap for count of sum equals target
Maximum Size Square Submatrix with All 1s (LC 221)	Sliding block with DP to check squares efficiently
Longest Repeating Character Replacement (2D variant)	Conceptually multi-dimensional sliding window for character counts in blocks
Sum of Submatrix Minimums (LC 1504)	Uses monotonic stacks over 2D windows with prefix sums for optimization
Max Consecutive Ones III (1D baseline, extendable)	Classic sliding window in 1D, generalizable to rows or columns in grids

Techniques Common in Multi-Dimensional Sliding Windows

Row compression + 1D sliding window or Kadane’s: Fix row boundaries, compress columns into a 1D array, solve reduced problem.
Prefix sums for fast window sum queries: Precompute sums for efficient sliding block sums.
Monotonic queue or deque extensions: For sliding maximum or minimum in 2D.
Two-pointer expansion + shrink patterns in multiple directions: Generalize the classic 1D two pointers.

References

The classic “Maximum Sum Sub-rectangle No Larger than K” (LC 363) is a canonical hard problem illustrating 2D sliding window + prefix sums + binary search techniques.
“Moving average over matrix” problems appear in many data streaming and image processing contexts (summed-area tables).
Many grid and 2D array problems implicitly require multi-dimensional sliding windows or window sums.

Would you like me to provide detailed canonical implementations for any of these problems or a more systematic taxonomy for multi-dimensional sliding windows?

Time interval / stream windows:
1. TODO easy Moving Average from Data Stream (346) (paid) (time-based variant)
2. TODO Design Hit Counter (362) (paid)