Count Complete Subarrays in an Array — Medium Problem & Solution

A subarray is complete when the number of distinct values in it equals the number of distinct values in the whole array.

Difficulty: Medium
Topics: Arrays, Hash Table, Sliding Window
Asked at: Amazon, Microsoft, Freshworks
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A subarray is complete when the number of distinct values in it equals the number of distinct values in the whole array.

Return the number of complete subarrays of nums.

Example 1

Input: nums = [1,3,1,2,2]
Output: 4
Explanation: The whole array has 3 distinct values; four subarrays match it.

Example 2

Input: nums = [5,5,5,5]
Output: 10
Explanation: One distinct value, so every subarray is complete.

Example 3

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

Constraints

1 <= nums.length <= 1000
1 <= nums[i] <= 2000

How to solve Count Complete Subarrays in an Array

For each left edge, find the shortest complete window; every longer window with the same left edge is also complete. Sliding both edges collects all of them in one pass.

Approach

Count the distinct values of the whole array as all.
Grow the window on the right, keeping a tally and a distinct count.
While the window is complete, add n - r (every right extension), then drop the left element and advance l.

Why it works

Adding elements can only raise the distinct count, and it can never exceed all, so once a window hits all every extension does too — hence the n - r. Shrinking from the left inside that loop enumerates each left edge exactly once with its minimal complete window.

Complexity

Time — O(n)
Space — O(n)

Pitfalls

Adding n - r outside the shrink loop counts only one left edge per right edge.
The distinct count of the window is compared with the whole array's, not with a fixed k.
An array of one repeated value makes every subarray complete — n(n+1)/2 of them.

Reference solution

Python

from typing import List

def countCompleteSubarrays(nums: List[int]) -> int:
    n = len(nums)
    all_distinct = len(set(nums))
    cnt = {}
    l = 0
    distinct = 0
    res = 0
    for r in range(n):
        v = nums[r]
        cnt[v] = cnt.get(v, 0) + 1
        if cnt[v] == 1:
            distinct += 1
        while distinct == all_distinct:
            res += n - r
            cnt[nums[l]] -= 1
            if cnt[nums[l]] == 0:
                distinct -= 1
            l += 1
    return res

JavaScript

var countCompleteSubarrays = function(nums) {
    var n = nums.length;
    var seen = {}, all = 0, i;
    for (i = 0; i < n; i++) {
        if (!seen[nums[i]]) { seen[nums[i]] = true; all++; }
    }
    var cnt = {};
    var l = 0, distinct = 0, res = 0;
    for (var r = 0; r < n; r++) {
        var v = nums[r];
        cnt[v] = (cnt[v] || 0) + 1;
        if (cnt[v] === 1) distinct++;
        while (distinct === all) {
            res += n - r;
            cnt[nums[l]]--;
            if (cnt[nums[l]] === 0) distinct--;
            l++;
        }
    }
    return res;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue