Intuition behind calculating values for 'atmost K' and 'atmost K-1' to get the answer for 'equals K'

user_8600195 0
Viewed 150

I am trying to solve an algorithm problem:

Given an array nums of positive integers, call a (contiguous, not necessarily distinct) subarray of nums "good" if the number of different integers in that subarray is exactly k. For example, [1,2,3,1,2] has 3 different integers: 1, 2, and 3. Return the number of good subarrays of nums.

Looking at the solution here, I was able to come up with the following sliding window approach:

class Solution {
public:
    int helper(vector<int>& nums, int B) {
        unordered_map<int, int> m;

        int start=0, end=0, count=0;
        while(end<nums.size()) {
            m[nums[end]]++;
            while(m.size()>B) {
                m[nums[start]]--;
                if(m[nums[start]]<=0) m.erase(nums[start]);
                start++;
            }
            count+=(end-start+1);
            end++;
        }
        return count;
    }
    
    int subarraysWithKDistinct(vector<int>& nums, int k) {
        return helper(nums, k)-helper(nums, k-1);
    }
};

I understand how the helper() function works, but not the intuition behind calculating number of subarrays with atmost k and k-1 distinct integers and subtracting them (i.e., behind helper(nums, k)-helper(nums, k-1)) to get the number of subarrays with exactly equal to k distinct integers.

What understanding am I missing?

sub-array sliding-window algorithm c++
1 Answers

I understand how the helper() function works, but not the intuition behind calculating number of subarrays with atmost k and k-1 distinct integers and subtracting them (i.e., behind helper(nums, k)-helper(nums, k-1)) to get the number of subarrays with exactly equal to k distinct integers.

Well, suppose you have a room with a bunch of children in it. It turns out that there are 12 children who are five years old or under, and 8 children who are four years old or under.

Now presumably you agree that each one of the "children four years old or under" is also one of the "children five years old or under," right?

So suppose we take the 12 children five years old or younger, and remove from them the 8 children four years old or younger. Of course, 12 - 8 = 4 children remain.

Now, how old is each of these children?

user_24624370
Related