DSA sheet · Arrays · Sliding window pattern (counting)

Subarrays with K Different Integers

This is a hard problem, and the reason it's hard is one small word: exactly. A sliding window is very good at counting windows with at most K different numbers, but it can't directly count windows with exactly K. The teacher first writes the two-loop brute force, shows that it's too slow, then builds the "at most K" window, and finally turns "at most" into "exactly" with one subtraction:

exactly(K) = atMost(K) − atMost(K − 1)

If you understand why this subtraction works on this page, many other "exactly K" counting problems (binary subarrays with sum K, nice subarrays with K odd numbers…) become the same 10 lines.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · Sliding window from scratch (what this page needs)
• Part A · Brute force: two loops + a frequency map
• Part B · Sliding window that counts "at most K different"
• Part C · Exactly K = atMost(K) − atMost(K − 1)
• Part D · Revision page

Part 0 · Before starting

Subarray = a continuous piece

A subarray is a piece of the array taken without gaps: you pick a start index and an end index and take everything in between. For [1, 2, 1] the subarrays are [1], [2], [1], [1,2], [2,1], [1,2,1]. But [1, 1] (skipping the 2) is not a subarray. (For strings the same idea is called a substring.)

An array of size n has n·(n+1)/2 subarrays. For n = 5 that's 15; for n = 2·10⁴ it's about 2·10⁸.

The brute force and why it repeats work

The obvious way to look at every subarray is two loops: i = start, j = end. That's O(n²) windows. The waste: when i moves by one step, the inner loop walks again over almost the same elements it just walked over. A sliding window avoids this by keeping what it already knows about the current piece and only adding one item on the right or removing one item on the left.

The window [left..right]

• Two indexes: left (start) and right (end). The window is everything from left to right, both included. Its length is right − left + 1.
• Expanding: move right one step and add nums[right] to whatever we're tracking (a sum, a count, a map).
• Shrinking: remove nums[left] from what we're tracking, then move left one step.
• Both pointers only ever move forward. That's why the total work is about 2n, not n².

Fixed vs variable windows

Three kinds of questions a variable window answers

• Longest valid window: after shrinking, the window is valid → best = max(best, right − left + 1).
• Shortest valid window: while the window is valid, record its length, then shrink to try for shorter.
• Count of valid windows (this page): after shrinking, count += right − left + 1. Part B explains exactly why.

Why a sliding window needs a "monotonic" condition

Shrinking only makes sense if the rule behaves nicely: if a window is valid, every smaller window inside it is valid too, and if it's invalid, every bigger window around it is invalid too. "At most K different numbers" has this property: taking items away can never add a new different number. So once the window has too many, the only fix is to shrink.

"Exactly K different" does not have it. [1,2] has exactly 2, but its piece [2] has only 1. That's why we can't count "exactly" directly and need the subtraction trick of Part C. (The same problem shows up in sum problems with negative numbers: adding an item can make the sum smaller, so "too big → shrink" stops being true.)

Frequency map (dict / Counter)

To know "how many different numbers are in my window", we keep a dictionary freq: key = a number, value = how many times it appears in the window right now.

• Number of different values = len(freq), the number of keys.
• Add x: freq[x] = freq.get(x, 0) + 1. The get(x, 0) gives 0 when x isn't a key yet. (Java's getOrDefault, which the teacher uses, is the same thing.)
• Remove x: freq[x] -= 1, and if it drops to 0, delete the key (del freq[x]), otherwise len(freq) would still count it.
• Python also has collections.Counter, a dict that returns 0 for missing keys. A plain dict is enough here.

Which optimisation pattern? (the teacher's 4-pattern check)

Every time a brute force is too slow, the teacher runs through four array patterns she taught at the start of the playlist:

Here: we care about whole subarrays (everything in between) → sliding window. Values are ≥ 1 (no negatives, no sums anyway) → Kadane and prefix sums don't fit, and two pointers alone isn't enough. So: sliding window.

Part A · Brute force: two loops + a frequency map

LeetCode 992 · Hard

1The question in simple words

You get an integer array nums and a number k. A subarray is good if the number of different values inside it is exactly k. Return how many good subarrays there are.

The teacher reads example 1 by size. Starting at index 0:

• [1,2] (size 2): different values {1, 2} → 2 ✓
• [1,2,1] (size 3): still {1, 2} → 2 ✓
• [1,2,1,2] (size 4): still {1, 2} → 2 ✓
• [1,2,1,2,3] (size 5): {1, 2, 3} → 3 ✗, more than k is not allowed.

Doing this from every start gives all 7 good subarrays:

Example 2 on LeetCode: nums = [1,2,1,3,4], k = 3 → 3: [1,2,1,3], [2,1,3], [1,3,4].

2What the constraints tell us

• 1 ≤ nums.length ≤ 2·10⁴. So n² = 4·10⁸. The teacher's rule: beyond about 10⁸ simple steps you risk TLE (Time Limit Exceeded). 4·10⁸ is past that → the brute force is only a starting point. We need something close to O(n).
• 1 ≤ nums[i] ≤ n: no negative numbers, so Kadane is ruled out (see Part 0).
• 1 ≤ k ≤ n: k is at least 1, so later k − 1 is at least 0. Keep this in mind for Part C.

3Intuition

Put your left finger i on a start index. Move your right finger j to the right, one item at a time, and keep a little notebook (the frequency map) of which values you've seen and how often. After each new item, look at how many different values the notebook has:

• exactly k → this subarray is good, count it;
• more than k → stop moving j; nothing further right can fix it;
• fewer than k → not good yet, keep going.

4Building the logic, the way the teacher does

5Approach steps

1. count = 0.
2. For each start i: make an empty map.
3. For each end j from i: add nums[j] to the map.
4. If the map has exactly k keys → count += 1. Else if it has more than k → break.
5. Return count.

6Code (Python)

class Solution:
    def subarraysWithKDistinct(self, nums, k):
        n = len(nums)
        count = 0
        for i in range(n):                          # every start
            freq = {}                               # fresh map for this start
            for j in range(i, n):                   # every end, from i
                freq[nums[j]] = freq.get(nums[j], 0) + 1
                if len(freq) == k:                  # exactly k different
                    count += 1
                elif len(freq) > k:                 # too many: longer is worse
                    break
        return count

7Code line by line

8Dry run for i = 0 (the teacher's walk-through)

Then i = 1 starts over with an empty map: [2], [2,1] ✓, [2,1,2] ✓, [2,1,2,3] → break (count 5). i = 2: [1], [1,2] ✓, then 3 → break (count 6). i = 3: [2], [2,3] ✓ (count 7). i = 4: [3] only. Answer 7 ✓.

Look at the yellow cells: the inner loop walks over the same items again for every new i. This repeated work is exactly what the sliding window removes.

9Complexity & remember

• Time O(n²): the outer loop runs n times, and for each start the inner loop can run up to n times (worst case: few different values, so it never breaks early). With n = 2·10⁴ that's up to 4·10⁸ steps → TLE risk, and slow even when it passes. An interviewer will ask for better.
• Space O(n): the map can hold up to n keys (actually at most k + 1 keys here, because we break at k + 1).

Part B · Sliding window that counts "at most K different"

1The question (a slightly different one)

Before solving "exactly k", we solve an easier question: how many subarrays have at most k different values? "At most k" means k or fewer (≤ k). A sliding window answers this directly, and Part C turns it into "exactly k".

2What the constraints tell us

Same as Part A: n up to 2·10⁴, so we want O(n). Values are positive, and the "at most k different" rule is monotonic (Part 0): removing items never adds a different value. So "too many → shrink from the left" is always the right move.

3Intuition

In the brute force, when i moves, we threw away everything we knew about [2, 1, 2] and counted it again. The sliding window says: don't recount. Add one item on the right; if that breaks the rule, remove items from the left until it's fine again.

The teacher splits it into two phases:

• Expand phase: right moves forward every step and adds nums[right] to the map, as long as the rule holds.
• Shrink phase: when the map has more than k keys, left removes nums[left] and moves forward, until the map has ≤ k keys again.

A sliding window is naturally an "at most" tool: after shrinking, the window has ≤ k different values, which includes both "fewer than k" and "exactly k". That's why this part counts too many for our real question, and Part C fixes it.

4Building the logic

Why count += right − left + 1?

After shrinking, [left..right] is the longest valid window that ends at right. Every shorter window that also ends at right sits inside it, so it's valid too (monotonic rule). How many windows end at right and start somewhere in left..right? One per start → right − left + 1, which is just the window's length.

The teacher's picture uses [1, 2, 1, 3, 4]. Say the window is [1, 2, 1, 3] (indexes 0..3). The subarrays that end exactly at index 3 are:

And the subarrays ending at index 0, 1 and 2 were already counted at those earlier steps (1, then 2, then 3 of them). So adding the window length at every step counts every valid subarray exactly once, grouped by where it ends.

5Approach steps

1. left = 0, count = 0, empty map.
2. For right from 0 to n − 1: add nums[right] to the map (expand).
3. While the map has more than k keys: decrease nums[left]'s count, delete it if it's 0, left += 1 (shrink).
4. count += right − left + 1.
5. Return count.

6Code (Python)

class Solution:
    def atMost(self, nums, k):
        left = 0
        count = 0
        freq = {}
        for right in range(len(nums)):
            # expand: take nums[right] into the window
            freq[nums[right]] = freq.get(nums[right], 0) + 1
            # shrink: too many different values -> drop from the left
            while len(freq) > k:
                freq[nums[left]] -= 1
                if freq[nums[left]] == 0:
                    del freq[nums[left]]        # gone from the window
                left += 1
            # every window ending at right and starting in left..right is valid
            count += right - left + 1
        return count

7Code line by line

8Dry run: atMost(2) on [1, 2, 1, 2, 3]

The function returns 12, but the expected answer is 7. That's not a bug: these 12 subarrays have at most 2 different values, so they include the 5 single-item subarrays that have only 1. Part C removes them.

9Complexity & remember

• Time O(n): there's a while inside the for, but left only moves forward and never comes back. Over the whole run, right touches each index once and left touches each index at most once (worst case: all values different). Total about 2n steps → O(2n) = O(n).
• Space O(n): the map, in the worst case when all values are different. (At most k + 1 keys at any moment, so O(k).)

Part C · Exactly K = atMost(K) − atMost(K − 1)

1The question in simple words

Back to the real question: count the subarrays with exactly k different values. We have a fast tool that counts "k or fewer". We need to throw away the ones with "fewer than k".

2What the constraints tell us

k ≥ 1, so k − 1 ≥ 0. atMost(0) works: every new item makes the map size 1 > 0, the loop removes it straight away, the window becomes empty, and we add right − (right+1) + 1 = 0. So atMost(0) = 0, which is right (no subarray has 0 different values).

3Intuition

Sort every subarray into buckets by how many different values it has: bucket 1, bucket 2, bucket 3…

• atMost(k) = bucket 1 + bucket 2 + … + bucket k.
• atMost(k − 1) = bucket 1 + … + bucket k−1.
• Subtract: everything cancels except bucket k, which is exactly what we want.

It's like asking "how many students are aged exactly 15?" = "how many are 15 or younger" − "how many are 14 or younger".

4Building it with the actual subarrays (k = 2)

All 12 subarrays counted by atMost(2) on [1,2,1,2,3], grouped by the index they end at (this is exactly how count += right − left + 1 adds them):

The red ones have only 1 different value. Those are exactly what atMost(1) counts. Its run on the same array: each new item differs from the one before, so the window always shrinks back to just the new item and adds 1 each time → 1 + 1 + 1 + 1 + 1 = 5: [1], [2], [1], [2], [3].

12 − 5 = 7 ✓, the 7 black ones: [1,2], [2,1], [1,2,1], [1,2], [2,1,2], [1,2,1,2], [2,3]. The same 7 as the table in Part A.

A second check: [1, 2, 1, 3, 4], k = 3 (LeetCode example 2)

13 − 10 = 3 ✓ ([1,2,1,3], [2,1,3], [1,3,4]).

5Approach steps

1. Write the helper atMost(nums, k) from Part B. (The teacher makes it a separate private function in Java.)
2. Call it twice: once with k, once with k − 1.
3. Return the difference.

6Code (Python)

class Solution:
    def subarraysWithKDistinct(self, nums, k):
        if k <= 0:                              # constraints say k >= 1; safety guard
            return 0
        return self.atMost(nums, k) - self.atMost(nums, k - 1)

    def atMost(self, nums, k):
        left = 0
        count = 0
        freq = {}
        for right in range(len(nums)):
            freq[nums[right]] = freq.get(nums[right], 0) + 1     # expand
            while len(freq) > k:                                 # use k, not 2!
                freq[nums[left]] -= 1                            # shrink
                if freq[nums[left]] == 0:
                    del freq[nums[left]]
                left += 1
            count += right - left + 1
        return count

7Code line by line

8Dry run summary

1. subarraysWithKDistinct([1,2,1,2,3], 2) calls atMost(…, 2) → 12 (Part B table).
2. Then atMost(…, 1): right 0 → [1] +1; right 1 → [1,2] too many → drop 1 → [2] +1; right 2 → drop 2 → [1] +1; right 3 → drop 1 → [2] +1; right 4 → drop 2 → [3] +1 → 5.
3. 12 − 5 = 7 ✓.

9Complexity & remember

• Time O(n): one atMost call is about 2n steps (right and left each pass once). We call it twice → about 4n. The teacher says O(4n) to be precise; it's still linear. On LeetCode it ran among the fastest solutions.
• Space O(n): the map, worst case when all values are different (more exactly O(k)). The second call reuses nothing from the first, but they don't run at the same time, so the space doesn't add up.

Part D · Revision page

s = Solution()
print(s.subarraysWithKDistinct([1, 2, 1, 2, 3], 2))   # 7
print(s.subarraysWithKDistinct([1, 2, 1, 3, 4], 3))   # 3
print(s.atMost([1, 2, 1, 2, 3], 2))                   # 12
print(s.atMost([1, 2, 1, 2, 3], 1))                   # 5
print(s.subarraysWithKDistinct([5, 5, 5], 1))         # 6 (every subarray)
print(s.subarraysWithKDistinct([1, 2, 3], 4))         # 0 (never 4 different)

Based on this video: Subarrays with K Different Integers | Sliding Window