Question

How to find the longest subarray with exactly k distinct numbers in C++

Answer 1

#include <unordered_map>
#include <iostream>
#include <vector>

using std::vector;

// Count distinct numbers in a window
inline int distinctCount(const std::unordered_map<int,int>& freq) {
    return freq.size();
}

// Find the longest subarray with exactly k distinct numbers
vector<int> longestWithKDistinct(const vector<int>& nums, int k) {
    std::unordered_map<int,int> freq;
    int left = 0;
    int bestL = 0, bestR = -1;

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

        // Shrink window if too many distinct numbers
        while (distinctCount(freq) > k) {
            int val = nums[left];
            if (--freq[val] == 0)
                freq.erase(val);
            left++;
        }

        // If exactly k distinct, update best window
        if (distinctCount(freq) == k) {
            if (right - left > bestR - bestL) {
                bestL = left;
                bestR = right;
            }
        }
    }

    if (bestR == -1) return {}; // no valid subarray
    return vector<int>(nums.begin() + bestL, nums.begin() + bestR + 1);
}

int main() {
    vector<int> nums = {1, 2, 1, 2, 3, 4, 2, 2};
    int k = 2;

    vector<int> result = longestWithKDistinct(nums, k);

    std::cout << "Longest subarray with exactly " << k << " distinct numbers:\n";
    for (int x : result) std::cout << x << " ";
}



/*
OUTPUT:

Longest subarray with exactly 2 distinct numbers:
1 2 1 2 

*/

 

70+ SQL courses for beginners and professionals