What is the brute force approach and complexity for Subarrays With At Most K Distinct Integers?

For each start, extend right with a set until it exceeds k distinct values with time complexity O(N²) and space complexity O(K).

What is the optimal approach and complexity for Subarrays With At Most K Distinct Integers?

Keep the longest valid window ending at right; it holds right − left + 1 valid subarrays with optimal time complexity O(N) and space complexity O(K).

How do you identify the pattern for Subarrays With At Most K Distinct Integers?

Look for key signals in the prompt: "count subarrays" indicates The answer is a count, not a length. Each step will add a number to a running total instead of taking a max.; "at most k distinct" indicates Monotonic rule: a shorter subarray never has more distinct values. Shrinking always helps, so a sliding window works.; "distinct integers" indicates We need to know how many different values are in the window → count map, and its size is the distinct count..

Subarrays With At Most K Distinct Integers

Medium·GeeksforGeeksBasic Anchor

GeeksforGeeks

Jump:

30-Second Mental ModelVariable Sliding Window + Count Map, counting right − left + 1 per right end

Complexity:O(N²)→O(N)

Key Insight

Move right across the array. For each right, keep left at the smallest start that still gives at most k distinct values. Then every start from left to right works, so exactly right − left + 1 valid subarrays end at right. Add that number and move on.

Core Validity Invariant

The window [left..right] is valid when it contains at most k distinct values, that is freq.size() ≤ k.

Problem

You are given an array of integers arr and a number k.

Count how many contiguous subarrays contain at most k different values. A value that appears several times inside a subarray still counts as one distinct value.

Implement int countAtMostK(vector<int>& arr, int k) inside class Solution. It returns the count as an int.

Input

An integer array arr of length n, and an integer k.

Output

The number of subarrays arr[i..j] (with i ≤ j) that have at most k distinct values.

Example 1

Input: arr = [1, 2, 2, 3], k = 2

Output: 9

There are 10 subarrays in total. Only [1, 2, 2, 3] has 3 distinct values. The other 9 have at most 2.

Example 2

Input: arr = [1, 1, 1], k = 1

Output: 6

Every subarray contains only the value 1, so all 6 subarrays count.

Example 3

Input: arr = [1, 2, 1, 1, 3, 3, 4, 2, 1], k = 2

Output: 24

Counting the valid subarrays ending at each index gives 1 + 2 + 3 + 4 + 3 + 4 + 3 + 2 + 2 = 24.

Constraints

• 1 ≤ n ≤ 2·10^4
• 1 ≤ k ≤ 2·10^4
• 1 ≤ arr[i] ≤ 10^9
• The answer is at most n(n+1)/2 ≈ 2·10^8, which fits in an int.

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
How many subarrays does an array of length n have? Can I afford to look at each one?
2.
If a subarray has at most k distinct values, what about a shorter subarray inside it?
3.
If a subarray already has more than k distinct values, can making it longer ever fix that?
4.
Instead of counting subarrays by where they start, could I count them by where they end?
5.
For a fixed right end, which starts give a valid subarray? Do they form one continuous block?

Brute force approach

Idea

Fix a start. Extend the end one step at a time and keep the values seen in a set. While the set has at most k values, count the subarray. As soon as it has k + 1, stop: longer subarrays from this start are also bad.

Thinking process

1
A subarray is fixed by its start and its end, so the simplest plan is to try them all.
2
Recomputing the distinct count for each pair from scratch would be O(n³). Instead, grow the end from the start and add one value to a set each step.
3
Once the set has more than k values, adding more elements cannot remove any of them, so break out early.
4
Add 1 for every (start, end) pair that stayed valid.

Visual

Every start builds a new set from scratch. Orange cells were already scanned from the previous start.

Brute force restartsarr = [1, 2, 1, 3, 4, 3, 3], k = 2step 1/7

arr

▲start

Start 0: 3 valid subarrays

[1][1, 2][1, 2, 1]

Work

elements scanned so far: 4
count: 3

arr[3] = 3 makes 3 distinct → stop

From start 0, grow to the right with a fresh set. Stop at index 3, because adding 3 makes 3 distinct values. Add 3.

Code & Implementation

brute.cpp

class Solution {
public:
    int countAtMostK(vector<int>& arr, int k) {
        int n = arr.size();
        int count = 0;

        // Try every start. Grow the subarray to the right one element at a time.
        for (int start = 0; start < n; start++) {
            unordered_set<int> seen;
            for (int end = start; end < n; end++) {
                seen.insert(arr[end]);
                // Adding more elements can never remove a distinct value,
                // so once we pass k, every longer subarray from this start fails too.
                if ((int)seen.size() > k) break;
                count++;   // arr[start..end] has at most k distinct values
            }
        }
        return count;
    }
};

import java.util.HashSet;
import java.util.Set;

class Solution {
    public int countAtMostK(int[] arr, int k) {
        int n = arr.length;
        int count = 0;

        // Try every start. Grow the subarray to the right one element at a time.
        for (int start = 0; start < n; start++) {
            Set<Integer> seen = new HashSet<>();
            for (int end = start; end < n; end++) {
                seen.add(arr[end]);
                // Adding more elements can never remove a distinct value,
                // so once we pass k, every longer subarray from this start fails too.
                if (seen.size() > k) break;
                count++;   // arr[start..end] has at most k distinct values
            }
        }
        return count;
    }
}

class Solution:
    def countAtMostK(self, arr: list[int], k: int) -> int:
        n = len(arr)
        count = 0

        # Try every start. Grow the subarray to the right one element at a time.
        for start in range(n):
            seen = set()
            for end in range(start, n):
                seen.add(arr[end])
                if len(seen) > k:
                    break
                count += 1

        return count

export function countAtMostK(arr: number[], k: number): number {
    const n = arr.length;
    let count = 0;

    // Try every start. Grow the subarray to the right one element at a time.
    for (let start = 0; start < n; start++) {
        const seen = new Set<number>();
        for (let end = start; end < n; end++) {
            seen.add(arr[end]);
            if (seen.size > k) break;
            count++;
        }
    }
    return count;
}

Complexity

Time O(N²)Space O(K)

In the worst case (for example all values equal, or k ≥ n), the inner loop never breaks early, so we look at all n(n+1)/2 ≈ 2·10^8 subarrays one by one. The set holds at most k + 1 values.

Optimized approach

Idea

Start from brute force

Brute force starts over at every start index. It builds a new set and walks right until it finds too many values.

Find the repeated work

Starting from start + 1, brute force walks over almost the same elements it just walked over from start. It also adds 1 for each subarray separately, even though the valid subarrays ending at one index always form one continuous block of starts.

Define the state — what variables do I need?

freq: Count map: for each value inside the window [left..right], how many times it appears. freq.size() is the number of distinct values.
left: The smallest start index that gives a valid subarray ending at right.
right: The current right end. We count all valid subarrays that end here.
count: Total number of valid subarrays found so far (all right ends up to the current one).

Define validity

The window [left..right] is valid when it contains at most k distinct values, that is freq.size() ≤ k.

Define the transitions — when does each pointer move, and why is it safe?

Every step: right moves forward

freq[arr[right]]++

The new element joins the window. This can only keep or increase the number of distinct values.

While freq.size() > k

freq[arr[left]]--; erase it if it hits 0; left++

Any window that starts at the current left and ends at right or later has too many values, so this left is useless from now on. Dropping it is safe. We stop as soon as the window is valid again, so left is the smallest valid start.

After the window is valid

count += right − left + 1

All starts from left to right give valid subarrays ending at right (shorter subarrays have fewer or equal distinct values).

What does the current window add to the answer?

At each right, the window adds right − left + 1: the subarrays [left..right], [left+1..right], …, [right..right]. Each one is valid, and none of them was counted before, because each subarray is only counted at its own right end.

Code & Implementation

optimal.cpp

class Solution {
public:
    int countAtMostK(vector<int>& arr, int k) {
        unordered_map<int, int> freq;   // value -> how many times it is in the window
        int left = 0;
        int count = 0;   // at most n(n+1)/2 = 2*10^8 for n = 2*10^4, fits in int

        for (int right = 0; right < (int)arr.size(); right++) {
            freq[arr[right]]++;                     // arr[right] enters

            // Too many distinct values: shrink from the left until it is fine again.
            while ((int)freq.size() > k) {
                if (--freq[arr[left]] == 0) freq.erase(arr[left]);
                left++;
            }

            // Every start from left to right gives a valid subarray ending at right.
            count += right - left + 1;
        }
        return count;
    }
};

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int countAtMostK(int[] arr, int k) {
        Map<Integer, Integer> freq = new HashMap<>();   // value -> count in window
        int left = 0;
        int count = 0;

        for (int right = 0; right < arr.length; right++) {
            freq.put(arr[right], freq.getOrDefault(arr[right], 0) + 1);

            // Too many distinct values: shrink from the left until it is fine again.
            while (freq.size() > k) {
                int leftVal = arr[left];
                int c = freq.get(leftVal);
                if (c == 1) freq.remove(leftVal);
                else freq.put(leftVal, c - 1);
                left++;
            }

            // Every start from left to right gives a valid subarray ending at right.
            count += right - left + 1;
        }
        return count;
    }
}

from collections import defaultdict

class Solution:
    def countAtMostK(self, arr: list[int], k: int) -> int:
        freq: dict[int, int] = defaultdict(int)
        left = 0
        count = 0

        for right in range(len(arr)):
            freq[arr[right]] += 1

            # Too many distinct values: shrink from the left.
            while len(freq) > k:
                val = arr[left]
                freq[val] -= 1
                if freq[val] == 0:
                    del freq[val]
                left += 1

            # Every start from left to right gives a valid subarray ending at right.
            count += right - left + 1

        return count

export function countAtMostK(arr: number[], k: number): number {
    const freq = new Map<number, number>();
    let left = 0;
    let count = 0;

    for (let right = 0; right < arr.length; right++) {
        const val = arr[right];
        freq.set(val, (freq.get(val) || 0) + 1);

        // Too many distinct values: shrink from the left until it is fine again.
        while (freq.size > k) {
            const leftVal = arr[left];
            const c = freq.get(leftVal)!;
            if (c === 1) freq.delete(leftVal);
            else freq.set(leftVal, c - 1);
            left++;
        }

        // Every start from left to right gives a valid subarray ending at right.
        count += right - left + 1;
    }
    return count;
}

Complexity

Time O(N)Space O(K)

right moves n times and left moves at most n times in total, so the loop body runs O(n) times. Each map update is O(1) on average. The map has at most k + 1 keys.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	For each start, extend right with a set until it exceeds k distinct values	O(N²)	O(K)
Optimal	Keep the longest valid window ending at right; it holds right − left + 1 valid subarrays	O(N)	O(K)

Why does this belong to this pattern?

Clues in the problem statement

“count subarrays”The answer is a count, not a length. Each step will add a number to a running total instead of taking a max.
“at most k distinct”Monotonic rule: a shorter subarray never has more distinct values. Shrinking always helps, so a sliding window works.
“distinct integers”We need to know how many different values are in the window → count map, and its size is the distinct count.

Count subarrays+"at most" rule that shrinking always fixes+count map for distinct values→Variable Sliding Window + Count Map, counting right − left + 1 per right end

This is the anchor for the whole At Most K sub-pattern. The window logic is exactly Fruit Into Baskets / Longest Substring with K Distinct. The only change is the last line: instead of best = max(best, right − left + 1), we do count += right − left + 1. Later questions in this sub-pattern swap the rule (product, all three letters, max appears k times, sum × length), but keep this counting idea. It is also the building block for Exactly K: exactly(k) = atMost(k) − atMost(k − 1).

Don't make this mistake

Adding 1 instead of the window length

✗ count += 1; // or count++

✓ count += right - left + 1;

The window [left..right] is not one subarray to count — it holds right − left + 1 valid subarrays that all end at right. Adding 1 only counts the longest one.

Not erasing a value when its count reaches 0

✗ freq[arr[left]]--; left++;

✓ if (--freq[arr[left]] == 0) freq.erase(arr[left]); left++;

freq.size() counts keys, even keys with value 0. If you leave zero entries in the map, the distinct count stays too high and the window shrinks too much.

Using if instead of while to shrink

✗ if (freq.size() > k) { /* remove arr[left] */ left++; }

✓ while (freq.size() > k) { /* remove arr[left] */ left++; }

Removing one element may not remove a distinct value (another copy may still be inside). You may need to move left several times before the window is valid again.

Confusing this with Exactly K

"At most k distinct" is monotonic, so one window answers it. "Exactly k distinct" is not: a window with exactly k values can lose that property when it shrinks. Don't try to count exactly-k with one window — compute atMost(k) − atMost(k − 1) using this function twice.

Counting at the wrong moment

Add right − left + 1 only after the while loop has made the window valid. If you add before shrinking, you count starts that are actually invalid.

Want to implement this?

Write it yourself on GeeksforGeeks, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Sliding Window translate into production architectures and low-level memory mechanics.

LLD Machine Coding

Sliding Window Rate Limiter

Implementing token bucket and sliding log request throttlers in real backend services.

Explore Track

C++ Internals

Stack vs Heap, Placement new & Layout

Cache line locality when traversing contiguous windows in memory.

Explore Track

Subarray Product Less Than K