992. Subarrays with K Different Integers - Explanation

Description

You are 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].

Example 3:

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

Output: 4

Explanation: Subarrays formed with exactly 1 different integers:

Constraints:

1 <= nums.length <= 20,000
1 <= nums[i], k <= nums.length

1. Brute Force

class Solution:
    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:
        n, res = len(nums), 0

        for i in range(n):
            seen = set()
            for j in range(i, n):
                seen.add(nums[j])
                if len(seen) > k:
                    break

                if len(seen) == k:
                    res += 1

        return res

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n)$

2. Sliding Window

class Solution:
    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:

        def atMostK(k):
            count = defaultdict(int)
            res = l = 0

            for r in range(len(nums)):
                count[nums[r]] += 1
                if count[nums[r]] == 1:
                    k -= 1

                while k < 0:
                    count[nums[l]] -= 1
                    if count[nums[l]] == 0:
                        k += 1
                    l += 1

                res += (r - l + 1)

            return res

        return atMostK(k) - atMostK(k - 1)

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

3. Sliding Window (One Pass) - I

class Solution:
    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:
        count = defaultdict(int)
        res = 0
        l_far = 0
        l_near = 0

        for r in range(len(nums)):
            count[nums[r]] += 1

            while len(count) > k:
                count[nums[l_near]] -= 1
                if count[nums[l_near]] == 0:
                    count.pop(nums[l_near])
                l_near += 1
                l_far = l_near

            while count[nums[l_near]] > 1:
                count[nums[l_near]] -= 1
                l_near += 1

            if len(count) == k:
                res += l_near - l_far + 1

        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

4. Sliding Window (One Pass) - II

class Solution:
    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:
        n = len(nums)
        count = [0] * (n + 1)
        res = l = cnt = 0

        for r in range(n):
            count[nums[r]] += 1
            if count[nums[r]] == 1:
                k -= 1

            if k < 0:
                count[nums[l]] -= 1
                l += 1
                k += 1
                cnt = 0

            if k == 0:
                while count[nums[l]] > 1:
                    count[nums[l]] -= 1
                    l += 1
                    cnt += 1

                res += (cnt + 1)

        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$