LeetCode: Subarrays with K Different Integers

Subarrays with K Different Integers

Similar Problems:

• CheatSheet: Leetcode For Code Interview
• CheatSheet: Common Code Problems & Follow-ups
• Tag: #slidingwindow, #atmostkdistinct

Given an array A of positive integers, call a (contiguous, not necessarily distinct) subarray of A 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 A.

Example 1:

Input: A = [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: A = [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].

Note:

1. 1 <= A.length <= 20000
2. 1 <= A[i] <= A.length
3. 1 <= K <= A.length

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

• Solution:

// https://code.dennyzhang.com/subarrays-with-k-different-integers
// Basic Ideas: slidingwindow
//
//    At most K - At most K-1 distinct
//
// Complexity: Time O(n*k), Space O(k)
func atmostKDistinct(A []int, K int) int {
    m := map[int]int{}
    res := 0
    // A[i...j]
    i:=0
    for j, v := range A {
        // move right
        m[v]++
        if m[v] == 1 {
            K--
        }
        // move left
        for K<0 {
            v2 := A[i]
            i++
            m[v2]--
            if m[v2] == 0 {
                K++
            }
        }
        // A[i...j], with j fixed
        res += j-i+1
    }
    return res
}

func subarraysWithKDistinct(A []int, K int) int {
    return atmostKDistinct(A, K) - atmostKDistinct(A, K-1)
}