Subarrays with K Different Integers - Practice Coding Problems

Subarrays with K Different Integers - Problem

Given an integer array nums and an integer k, return the number of good subarrays of nums.

A good array is an array where the number of different integers in that array is exactly k.

For example, [1,2,3,1,2] has 3 different integers: 1, 2, and 3.

A subarray is a contiguous part of an array.

Input & Output

Example 1 — Basic Case

$ Input: nums = [1,2,1,2,3], k = 2

› Output: 7

💡 Note: Subarrays with exactly 2 distinct integers: [1,2], [2,1], [1,2], [2,1,2], [1,2,3], [2,3], [1,3]. Total count = 7.

Example 2 — Single Distinct

$ Input: nums = [1,2,1,3,4], k = 3

› Output: 3

💡 Note: Subarrays with exactly 3 distinct integers: [1,2,1,3], [2,1,3], [1,3,4]. Total count = 3.

Example 3 — All Same Elements

$ Input: nums = [1,1,1,1], k = 1

› Output: 10

💡 Note: All subarrays have exactly 1 distinct integer. With n=4, total subarrays = n*(n+1)/2 = 4*5/2 = 10.

Constraints

1 ≤ nums.length ≤ 2 × 10⁴
1 ≤ nums[i], k ≤ nums.length

Visualization

Tap to expand

Understanding the Visualization

Input

Array [1,2,1,2,3] with k=2

Process

Find all subarrays with exactly 2 distinct integers

Output

Count = 7 subarrays

Key Takeaway

🎯 Key Insight: Transform 'exactly k' into the difference between 'at most k' and 'at most k-1'

Asked in

G Google 15 f Facebook 12 a Amazon 8

The key insight is transforming 'exactly k distinct' into 'at most k distinct' - 'at most k-1 distinct'. Best approach uses sliding window with frequency counting. Time: O(n), Space: O(k)

Common Approaches

Approach	Time	Space	Notes
✓ Sliding Window (At Most K Technique)	O(n)	O(k)	Convert 'exactly k' to 'at most k' - 'at most k-1'
Brute Force	O(n³)	O(n)	Check all subarrays and count distinct integers in each

Sliding Window (At Most K Technique) — Algorithm Steps

Create helper function to count subarrays with at most k distinct integers
Use sliding window with frequency map to track distinct count
Return atMostK(k) - atMostK(k-1)

Visualization

Tap to expand

Step-by-Step Walkthrough

Expand Window

Add elements while distinct count ≤ k

Shrink Window

Remove elements when distinct count > k

Count Subarrays

Add (right - left + 1) to total count

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int key;
    int count;
} FreqEntry;

int atMostK(int* nums, int numsSize, int k) {
    if (k == 0) return 0;
    
    int count = 0;
    int left = 0;
    FreqEntry freq[1001];
    int freqSize = 0;
    
    for (int i = 0; i < 1001; i++) {
        freq[i].key = -1;
        freq[i].count = 0;
    }
    
    for (int right = 0; right < numsSize; right++) {
        int found = 0;
        for (int i = 0; i < freqSize; i++) {
            if (freq[i].key == nums[right]) {
                freq[i].count++;
                found = 1;
                break;
            }
        }
        if (!found) {
            freq[freqSize].key = nums[right];
            freq[freqSize].count = 1;
            freqSize++;
        }
        
        while (freqSize > k) {
            for (int i = 0; i < freqSize; i++) {
                if (freq[i].key == nums[left]) {
                    freq[i].count--;
                    if (freq[i].count == 0) {
                        for (int j = i; j < freqSize - 1; j++) {
                            freq[j] = freq[j + 1];
                        }
                        freqSize--;
                    }
                    break;
                }
            }
            left++;
        }
        
        count += right - left + 1;
    }
    
    return count;
}

int solution(int* nums, int numsSize, int k) {
    return atMostK(nums, numsSize, k) - atMostK(nums, numsSize, k - 1);
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line, "[],\n");
    while (token != NULL) {
        if (strlen(token) > 0) {
            nums[numsSize++] = atoi(token);
        }
        token = strtok(NULL, "[],\n");
    }
    
    int k;
    scanf("%d", &k);
    
    int result = solution(nums, numsSize, k);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Two passes through array, each element visited at most twice by sliding window

✓ Linear Growth

Space Complexity

O(k)

Hash map stores at most k distinct elements

✓ Linear Space

89.0K Views

Medium Frequency

~25 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Sliding Window (At Most K Technique) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler