Count Complete Subarrays in an Array

Medium
798.

Count Complete Subarrays in an Array

Count Complete Subarrays in an Array is a medium coding problem on arrays, hash table and sliding window, asked in Amazon, Microsoft and Freshworks interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var countCompleteSubarrays = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Count Complete Subarrays in an Array — Problem & Solution

Count Complete Subarrays in an Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Count Complete Subarrays in an Array is a medium coding problem on arrays, hash table and sliding window, asked in Amazon, Microsoft and Freshworks interviews.

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

Hints for Count Complete Subarrays in an Array

  1. Hint 1

    First find how many distinct values the whole array has — that is the target.

  2. Hint 2

    Once a window reaches the target, extending it to the right keeps it complete.

  3. Hint 3

    So for each minimal complete window starting at l, all n - r extensions count.

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

  1. Count the distinct values of the whole array as all.
  2. Grow the window on the right, keeping a tally and a distinct count.
  3. 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

Java

public static int countCompleteSubarrays(int[] nums) {
    int n = nums.length;
    Set<Integer> distinctAll = new HashSet<>();
    for (int x : nums) distinctAll.add(x);
    int all = distinctAll.size();
    Map<Integer, Integer> cnt = new HashMap<>();
    int l = 0, distinct = 0, res = 0;
    for (int r = 0; r < n; r++) {
        int v = nums[r];
        int have = cnt.getOrDefault(v, 0) + 1;
        cnt.put(v, have);
        if (have == 1) distinct++;
        while (distinct == all) {
            res += n - r;
            int u = nums[l];
            int left = cnt.get(u) - 1;
            cnt.put(u, left);
            if (left == 0) distinct--;
            l++;
        }
    }
    return res;
}

C++

int countCompleteSubarrays(vector<int>& nums) {
    int n = (int) nums.size();
    unordered_set<int> distinctAll(nums.begin(), nums.end());
    int all = (int) distinctAll.size();
    unordered_map<int, int> cnt;
    int l = 0, distinct = 0, res = 0;
    for (int r = 0; r < n; r++) {
        if (++cnt[nums[r]] == 1) distinct++;
        while (distinct == all) {
            res += n - r;
            if (--cnt[nums[l]] == 0) distinct--;
            l++;
        }
    }
    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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets