Subarrays With At Most K Distinct Integers

Problem Overview

Given an array of positive integers arr[] and an integer k, your task is to:

Count the number of subarrays that contain at most k distinct integers.

A subarray is a contiguous part of the array.

Example

Input

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

Output

Valid Subarrays

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

Key Idea: Sliding Window

A brute-force approach (checking all subarrays) takes O(n²) time, which is too slow.

Instead, we use:

Sliding Window
HashMap (Frequency Map)

Intuition

We maintain a window [left, right] such that:

It contains at most k distinct elements.
Expand right to include new elements.
If distinct elements exceed k, move left forward to shrink the window.

Key Observation

At each step:

The number of valid subarrays ending at index right is:

(right - left + 1)

Because all these subarrays are valid:

[right], [right-1, right], ..., [left, right]

Step-by-Step Dry Run

Input

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

Step	Window	Distinct	Count Added	Total
r=0	[1]	1	1	1
r=1	[1,2]	2	2	3
r=2	[1,2,2]	2	3	6
r=3	[2,2,3]	2	3	9

Final Answer = 9

Algorithm Steps

Initialize:
- left = 0
- count = 0
- map to store frequencies
Traverse using the right pointer:
- Add the element to the map.
- If distinct count becomes greater than k, shrink the window.
- Add (right - left + 1) to the result.

Java Implementation

import java.util.*;

class Solution {
    public int countAtMostK(int arr[], int k) {
        int left = 0, count = 0;
        Map<Integer, Integer> map = new HashMap<>();

        for (int right = 0; right < arr.length; right++) {
            // Add current element
            map.put(arr[right], map.getOrDefault(arr[right], 0) + 1);

            // Shrink window if distinct elements exceed k
            while (map.size() > k) {
                map.put(arr[left], map.get(arr[left]) - 1);
                if (map.get(arr[left]) == 0) {
                    map.remove(arr[left]);
                }
                left++;
            }

            // Count valid subarrays
            count += (right - left + 1);
        }

        return count;
    }
}

Complexity Analysis

Time Complexity: O(n)
- Each element is added and removed at most once.
Space Complexity: O(k)
- HashMap stores at most k distinct elements.

Bonus Concept: Exactly K Distinct

Sometimes problems ask:

Count subarrays with exactly K distinct elements.

Use this trick:

exactlyK = atMostK(k) - atMostK(k - 1)

Example 2

Input

arr = [1, 1, 1]
k = 1

Output

Explanation

All subarrays:

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

Summary

This problem can be solved efficiently using the Sliding Window technique with a HashMap to track the frequency of elements inside the current window. By maintaining a window with at most k distinct integers and counting valid subarrays at each step, we achieve an optimal O(n) time complexity solution instead of the slower brute-force approach.