Subarrays With At Most K Distinct Integers

JavaView on GFG

Time: O(n)

Space: O(k)

Intuition

Count subarrays with at most k distinct integers. Sliding window.

Algorithm

1Sliding window: expand right. When distinct > k: shrink left. Count = right - left + 1 for each right.

Common Pitfalls

•Same as LC 992 helper. O(n). For exactly k: atMost(k) - atMost(k-1).

Subarrays With At Most K Distinct Integers.java

Java

// Approach: Sliding window. Shrink left when distinct count > k; count is right - left + 1 for each right.
// Time: O(n) Space: O(k)
import java.util.*;

class Solution {
    public int countAtMostK(int arr[], int k) {
        int n = arr.length;
        int left = 0, right = 0;
        int count = 0;
        HashMap<Integer, Integer> freq = new HashMap<>();

        for (right = 0; right < n; right++) {
            // Add current element to frequency map
            freq.put(arr[right], freq.getOrDefault(arr[right], 0) + 1);

            // Shrink the window if more than k distinct elements
            while (freq.size() > k) {
                freq.put(arr[left], freq.get(arr[left]) - 1);
                if (freq.get(arr[left]) == 0)
                    freq.remove(arr[left]);

                left++;
            }

            // Add number of subarrays ending at right with at most k distinct
            count += (right - left + 1);
        }

        return count;
    }
}

Was this solution helpful?