HardCoding

Subarrays with K Different Integers

Asked at

HashedIn

Microsoft

NetApp

ServiceNow

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

You are given an integer array **nums **and an integer k. Return the number of good subarrays of nums.

A good subarray is defined as a contiguous subarray of **nums **that contains exactly k distinct integers. A subarray is a contiguous part of the array.

Input: nums = [1, 2, 1, 2, 3], k = 2 Output: 7 **Explanation: **The 7 subarrays with exactly 2 different integers are: [1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2]

Input: nums = [1, 2, 1, 3, 4], k = 3 Output: 3 Explanation: The 3 subarrays with exactly 3 different integers are: [1,2,1,3], [2,1,3], [1,3,4]

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

1 <= nums.length <= 2 * 104 1 <= nums[i], k <= nums.length

cpp

class Solution {
public:
    int subarraysWithKDistinct(vector<int>& nums, int k) {
        // Your code goes here
    }
};

java

class Solution {
    public int subarraysWithKDistinct(int[] nums, int k) {
        // Your code goes here
    }
}

python

class Solution:
    def subarraysWithKDistinct(self, nums, k):
        # Your code goes here

javascript

class Solution {
    subarraysWithKDistinct(nums, k) {
        // Your code goes here
    }
}

csharp

class Solution {
    public int SubarraysWithKDistinct(int[] nums, int k) {
        // Your code goes here
    }
}

func subarraysWithKDistinct(nums []int, k int) int {
    // Your code goes here
}

Solve on LeetCode →

Stuck? Show a way to structure it+

01Define atMost(K) as the number of subarrays containing at most K distinct values.
02Compute atMost with a frequency map and a shrinking left boundary.
03Return atMost(k) minus atMost(k - 1).
04Make the helper return zero for a negative distinct-count limit.

Reference answer

Counting exactly k distinct values directly is awkward, but exactly(k) = atMost(k) - atMost(k - 1). To compute atMost(limit), expand a right pointer and add the new value to a frequency map. While the map has more than limit keys, remove values from the left, erasing a key when its count reaches zero. After restoring validity, every subarray ending at right and starting anywhere from left through right is valid, contributing right - left + 1. Sum that contribution for every right endpoint. Run the helper for k and k - 1 and subtract. Each helper is O(n) time because both pointers move forward, with O(number of distinct values) space. The helper should return zero for a negative limit, which cleanly handles k = 0.

Then expect these follow-ups

Why does a valid window contribute right - left + 1 subarrays?
Tests: counting proof
Where else can exactly(K) = atMost(K) - atMost(K-1) be used?
Tests: pattern transfer

Hiring now

ServiceNow has 794 open roles right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Senior Software Engineer, Search Infrastructure - Moveworks
Mountain View, CALIFORNIA, United States
Staff Software Engineer, AI Native Engineering, Integrations
Hyderabad, India
Software Engineer
Santa Clara, CALIFORNIA, United States

Or practice this question first

Next question