Scribd
Upload
5 views2 pages

Leetcode Problem 992

The document discusses an approach to solve the problem of finding subarrays with exactly K distinct integers using a sliding window technique. It introduces a helper function that calculates the number of subarrays with at most K distinct elements and explains the process of expanding and shrinking the window while tracking distinct elements. The final solution is derived by subtracting the count of subarrays with at most K-1 distinct elements from those with at most K distinct elements.

Uploaded by

kamalaramaraju
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
5 views2 pages

Leetcode Problem 992

The document discusses an approach to solve the problem of finding subarrays with exactly K distinct integers using a sliding window technique. It introduces a helper function that calculates the number of subarrays with at most K distinct elements and explains the process of expanding and shrinking the window while tracking distinct elements. The final solution is derived by subtracting the count of subarrays with at most K-1 distinct elements from those with at most K distinct elements.

Uploaded by

kamalaramaraju
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Revision Notes: Subarrays with K Different

Integers (LeetCode 992)

Core Idea
Trying to find exactly K distinct elements directly with a sliding window is extremely
difficult because shrinking the window doesn’t always decrease the number of distinct
elements smoothly. Instead, finding the number of subarrays with at most K distinct
elements is perfectly suited for a sliding window. We apply our master pattern:
Exactly(K) = AtMost(K) − AtMost(K − 1)

Approach
• We create a helper function atMost(nums, k) using a Sliding Window.

• Tracking Frequency: We use a frequency array (or Hash Map) to track the ele-
ments inside the window. Because the problem specifies nums[i] ≤ [Link],
a flat array is much faster than an unordered map. We also keep an integer
distinct elements to track the “size” of our map.

• Expand: As R moves right, we increment the frequency of nums[R]. If its fre-


quency goes from 0 to 1, we increment distinct elements.

• Shrink & The Deletion Trap: If distinct elements > k, our window is in-
valid. We shrink from the left by decrementing the frequency of nums[L]. Crucial
Trap: If the frequency of nums[L] hits 0, it is functionally erased from our map,
and we MUST decrement distinct elements.

• The Math: Once valid, we add (R - L + 1) to our total count.

The Optimized O(N ) Code (C++)


# include < vector >

using namespace std ;

// Helper function to find number of subarrays with AT MOST k distinct


integers
int atMost ( vector < int >& nums , int k ) {
if ( k < 0) return 0; // Edge case protection

// Instead of a slow unordered_map , we use a frequency array


// since nums [ i ] is guaranteed to be <= nums . size ()
vector < int > count ( nums . size () + 1 , 0) ;

1
int left = 0;
int d istinc t_elem ents = 0; // Acts as our " map . size () "
int total_subarrays = 0;

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


// 1. Expand the window
if ( count [ nums [ right ]] == 0) {
dis tinct_ elemen ts ++;
}
count [ nums [ right ]]++;

// 2. Shrink window while it ’s invalid ( > k distinct elements )


while ( disti nct_el ements > k ) {
count [ nums [ left ]] - -;

// THE TRAP : If frequency hits 0 , it is " erased " from our


window
if ( count [ nums [ left ]] == 0) {
distinct_elements - -;
}
left ++;
}

// 3. Count valid subarrays ending at ’ right ’


total_subarrays += ( right - left + 1) ;
}

return total_subarrays ;
}

int s u b a r r a y s W i t h K D i s t i n c t ( vector < int >& nums , int k ) {


// Exactly ( K ) = AtMost ( K ) - AtMost ( K - 1)
return atMost ( nums , k ) - atMost ( nums , k - 1) ;
}

You might also like