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 Sliding Window Question Types #

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 #

Sliding Window Maximum (239) 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

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

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

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]

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

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

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

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

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.

 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

Minimum Window Substring (76)

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.

 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]

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
   # M1: optimal, uses unique chars counter (required, formed)
    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

   # M2: suboptimal but easier first-pass attempt
   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

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

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

Find All Anagrams in a String (438)

Fixed sliding window that has a local character count that will be compared with all the target character counts. The easy way is to use collections.Counter, if necessary to implement from scratch, track required, encountered distinct characters and keep a counter.

 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

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
21
22
23
24
25
26
27
28
29
30
31
   # M1: maintains a fixed set for the sliding window
   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

   # M2: just uses a last seen map
   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

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)

inorder to count subarrays with exactly k distinct elements, exactly_k = atMostK(nums, k) - atMostK(nums, k - 1)

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)

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

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.

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

   class Solution:
       def subarraySum(self, nums: List[int], k: int) -> int:
           n = len(nums)
           # number of already seen prefix counts -- remember it's a historical
           prefix_count = defaultdict(int)
           prefix_count[0] = 1 # the first idx is 0 trivially and we have seen it once
           curr_sum = 0

           res = 0

           for num in nums:
               curr_sum += num
               if (complement:=curr_sum - k) in prefix_count:
                   res += prefix_count[complement]
               prefix_count[curr_sum] += 1

           return res

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) :completed: 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

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

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)
            )

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.

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, Recipes, Boilerplate #

Boilerplates #

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 ...

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

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.

Formalised Algos #

Here are some formalised algos related to sliding windows

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

Kadane’s Algorithm is a dynamic programming technique and is the gold standard for maximum subarray sum problems.

A subarray is continguous region of an array. We wish to find out the max subarray based on some scoring system.

We keep a global max_so_far and a local one, max_ending_here. This is because for each element we encounter, we have 2 choices:

A: continue extending the current subarray
B: start a new subarray

how to make the choice? suppose the scoring was a positive score.

If choice A makes the running sum negative then its effect is worse than if it was a 0. So we should pick choice B at that point.

This gives us the following style, Kadane’s Algorithm:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def max_subarray_sum(nums):
    max_so_far = float('-inf')
    max_ending_here = 0

    for num in nums:
        max_ending_here += num
        max_so_far = max(max_so_far, max_ending_here)
        if max_ending_here < 0:
            max_ending_here = 0

    return max_so_far

TODO KIV pending matters #

[ ] 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

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

      The provided solution attempts a brute-force circular sliding window approach for the problem [Maximum Sum Circular Subarray](https://leetcode.com/problems/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
      1. **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.

      2. **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.

      3. **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)

      ```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[0]
                  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.

      [1](https://algo.monster/liteproblems/918)
      [2](https://favtutor.com/blogs/maximum-circular-subarray-sum)
      [3](https://docs.vultr.com/problem-set/maximum-sum-circular-subarray)
      [4](https://www.geeksforgeeks.org/dsa/maximum-contiguous-circular-sum/)
      [5](https://leetcode.com/problems/maximum-sum-circular-subarray/)
      [6](https://takeuforward.org/data-structure/kadanes-algorithm-maximum-subarray-sum-in-an-array/)
      [7](https://www.jointaro.com/interviews/questions/maximum-sum-circular-subarray/?company=amazon)
      [8](https://www.youtube.com/watch?v=fxT9KjakYPM)
      [9](https://neetcode.io/courses/advanced-algorithms)

[ ] 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-Dimenaional Sliding Window

see questions within this response:

     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                                         |
     |-----------------------------------------------------------|-----------------------------------------------------------------|
     | **1. 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) |
     | **2. 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 |
     | **3. 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 |
     | **4. Sliding Window Maximum in 2D (Grid version)**         | Apply 1D sliding window max on every row, then column-wise max on intermediate result |
     | **5. 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 |
     | **6. Maximum Size Square Submatrix with All 1s (LC 221)**  | Sliding block with DP to check squares efficiently |
     | **7. Longest Repeating Character Replacement (2D variant)**| Conceptually multi-dimensional sliding window for character counts in blocks |
     | **8. Sum of Submatrix Minimums (LC 1504)**                 | Uses monotonic stacks over 2D windows with prefix sums for optimization |
     | **9. 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?

     [1](https://www.reddit.com/r/leetcode/comments/15a7ezt/sliding_window_technique/)
     [2](https://blog.reachsumit.com/posts/2020/10/leetcode-sliding-window/)
     [3](https://www.youtube.com/watch?v=y2d0VHdvfdc)
     [4](https://leetcode.com/discuss/interview-question/3722472/mastering-sliding-window-technique-a-comprehensive-guide)
     [5](https://leetcode.com/problem-list/sliding-window/)
     [6](https://leetcode.com/problems/sliding-window-maximum/)
     [7](https://leetcode.com/discuss/study-guide/3630462/Top-20-Sliding-Window-Problems-for-beginners)
     [8](https://www.youtube.com/watch?v=Mf9C6vDxhzk)

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