Subarrays With K Different Integers - LeetCode Daily Challenge

Problem Statement

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.

Example 1

Input: nums = [1,2,1,2,3], k = 2
Output: 7
Explanation: Subarrays formed with exactly 2 different integers: [1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2]

Example 2

Input: nums = [1,2,1,3,4], k = 3
Output: 3
Explanation: Subarrays formed with exactly 3 different integers: [1,2,1,3], [2,1,3], [1,3,4].

Try here before watching the video.

Prerequisite Video

Video Solution

Java Code

class Solution {
    public int subarraysWithKDistinct(int[] nums, int k) {
        Map<Integer, Integer> hashmap = new HashMap<>();
        int start = 0, subarrayCount = 0, prefixElement = 0;

        for(int end = 0; end < nums.length; end++) {
            int curr = nums[end];
            hashmap.put(curr, hashmap.getOrDefault(curr, 0) + 1);

            if(hashmap.size() == k + 1) {
                hashmap.remove(nums[start]);
                prefixElement = 0;
                start += 1;
            }

            while(hashmap.get(nums[start]) > 1) {
                hashmap.put(nums[start], hashmap.get(nums[start]) - 1);
                prefixElement += 1;
                start += 1;
            }

            if(hashmap.size() == k) {
                subarrayCount += (1 + prefixElement);
            }
        }

        return subarrayCount;
    }
}

C++ Code

class Solution {
public:
    int subarraysWithKDistinct(vector<int>& nums, int k) {
        unordered_map<int, int> hashmap;
        int start = 0, subarrayCount = 0, prefixElement = 0;

        for (int end = 0; end < nums.size(); end++) {
            int curr = nums[end];
            hashmap[curr]++;

            if (hashmap.size() == k + 1) {
                hashmap[nums[start]]--;
                if (hashmap[nums[start]] == 0) hashmap.erase(nums[start]);
                prefixElement = 0;
                start++;
            }

            while (hashmap[nums[start]] > 1) {
                hashmap[nums[start]]--;
                prefixElement++;
                start++;
            }

            if (hashmap.size() == k) {
                subarrayCount += (1 + prefixElement);
            }
        }

        return subarrayCount;
    }
};

Python Code

class Solution:
    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:
        hashmap = {}
        start = 0
        subarrayCount = 0
        prefixElement = 0

        for end in range(len(nums)):
            curr = nums[end]
            hashmap[curr] = hashmap.get(curr, 0) + 1

            if len(hashmap) == k + 1:
                hashmap[nums[start]] -= 1
                if hashmap[nums[start]] == 0:
                    del hashmap[nums[start]]
                prefixElement = 0
                start += 1

            while hashmap.get(nums[start], 0) > 1:
                hashmap[nums[start]] -= 1
                prefixElement += 1
                start += 1

            if len(hashmap) == k:
                subarrayCount += (1 + prefixElement)

        return subarrayCount

Javascript Code

var subarraysWithKDistinct = function(nums, k) {
    let hashmap = {};
    let start = 0;
    let subarrayCount = 0;
    let prefixElement = 0;

    for (let end = 0; end < nums.length; end++) {
        let curr = nums[end];
        hashmap[curr] = (hashmap[curr] || 0) + 1;

        if (Object.keys(hashmap).length === k + 1) {
            hashmap[nums[start]]--;
            if (hashmap[nums[start]] === 0) delete hashmap[nums[start]];
            prefixElement = 0;
            start++;
        }

        while ((hashmap[nums[start]] || 0) > 1) {
            hashmap[nums[start]]--;
            prefixElement++;
            start++;
        }

        if (Object.keys(hashmap).length === k) {
            subarrayCount += (1 + prefixElement);
        }
    }

    return subarrayCount;
};

Go Code

func subarraysWithKDistinct(nums []int, k int) int {
    hashmap := make(map[int]int)
    start := 0
    subarrayCount := 0
    prefixElement := 0

    for end := 0; end < len(nums); end++ {
        curr := nums[end]
        hashmap[curr]++

        if len(hashmap) == k+1 {
            hashmap[nums[start]]--
            if hashmap[nums[start]] == 0 {
                delete(hashmap, nums[start])
            }
            prefixElement = 0
            start++
        }

        for hashmap[nums[start]] > 1 {
            hashmap[nums[start]]--
            prefixElement++
            start++
        }

        if len(hashmap) == k {
            subarrayCount += (1 + prefixElement)
        }
    }

    return subarrayCount
}

Complexity Analysis

Time Complexity: O(N), where N is the number of elements in array nums. This is because we are iterating the entire array only once.
Space Complexity: O(N), we are taking N extra space.