Subarrays With K Different Integers · Interview Problem

Back to problems

Leetcode

Medium

Arrays

Hash Maps

Google

Subarrays With K Different Integers

Count how many contiguous subarrays contain exactly $k$ distinct integers.

Acceptance 100%

Start Practice

Problem Statement

Given an integer array nums and an integer k, count the number of contiguous subarrays whose set of values contains exactly k distinct integers.

A subarray is a contiguous slice of the array. You need to return the total number of such subarrays.

Input Format

An integer array nums
An integer k

Output Format

Return one integer: the number of subarrays with exactly k distinct integers.

Constraints

$1 \le nums.length$
$1 \le k \le nums.length$
Values in nums are integers
The intended solution should be better than enumerating all subarrays directly

Examples

Sample cases returned by the problem API.

Example 1

Input

nums = [1,2,1,2,3], k = 2

Output

Explanation

The valid subarrays are [1,2], [1,2,1], [1,2,1,2], [2,1], [2,1,2], [1,2], and [2,3].

Example 2

Input

nums = [1,2,1,3,4], k = 3

Output

Explanation

The valid subarrays are [1,2,1,3], [2,1,3], and [1,3,4].

Premium problem context

Unlock deeper context for this problem

Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.

Guided hints

Editorial and discussion links

Concept map and variants

Track your progress