Count Complete Subarrays in an Array

medium array sliding window hash table

Problem

You are given an array nums of positive integers. A subarray (a contiguous, non-empty part of the array) is called complete if it contains exactly as many distinct values as the whole array does. Return the number of complete subarrays.

Inputnums = [1,3,1,2,2]

Output4

The whole array has 3 distinct values {1,2,3}. The complete subarrays are [1,3,1,2], [1,3,1,2,2], [3,1,2] and [3,1,2,2].

nums (comma-separated positive integers)

def countCompleteSubarrays(nums):
    total = len(set(nums))          # distinct values in whole array
    count = 0
    left = 0
    freq = {}                       # value -> count inside window
    for right in range(len(nums)):
        freq[nums[right]] = freq.get(nums[right], 0) + 1
        # shrink while [left, right] still holds all distinct values
        while len(freq) == total:
            freq[nums[left]] -= 1
            if freq[nums[left]] == 0:
                del freq[nums[left]]
            left += 1
        # starts 0..left-1 each complete the subarray ending at right
        count += left
    return count

function countCompleteSubarrays(nums) {
  const total = new Set(nums).size;       // distinct values in whole array
  let count = 0, left = 0;
  const freq = new Map();                 // value -> count inside window
  for (let right = 0; right < nums.length; right++) {
    freq.set(nums[right], (freq.get(nums[right]) || 0) + 1);
    // shrink while [left, right] still holds all distinct values
    while (freq.size === total) {
      const v = nums[left];
      freq.set(v, freq.get(v) - 1);
      if (freq.get(v) === 0) freq.delete(v);
      left++;
    }
    // starts 0..left-1 each complete the subarray ending at right
    count += left;
  }
  return count;
}

int countCompleteSubarrays(int[] nums) {
    Set<Integer> whole = new HashSet<>();
    for (int v : nums) whole.add(v);
    int total = whole.size();               // distinct values in whole array
    long count = 0;
    int left = 0;
    Map<Integer, Integer> freq = new HashMap<>();
    for (int right = 0; right < nums.length; right++) {
        freq.merge(nums[right], 1, Integer::sum);
        // shrink while [left, right] still holds all distinct values
        while (freq.size() == total) {
            int v = nums[left];
            if (freq.merge(v, -1, Integer::sum) == 0) freq.remove(v);
            left++;
        }
        // starts 0..left-1 each complete the subarray ending at right
        count += left;
    }
    return (int) count;
}

int countCompleteSubarrays(vector<int>& nums) {
    int total = unordered_set<int>(nums.begin(), nums.end()).size();
    long long count = 0;
    int left = 0;
    unordered_map<int,int> freq;             // value -> count inside window
    for (int right = 0; right < (int)nums.size(); right++) {
        freq[nums[right]]++;
        // shrink while [left, right] still holds all distinct values
        while ((int)freq.size() == total) {
            int v = nums[left];
            if (--freq[v] == 0) freq.erase(v);
            left++;
        }
        // starts 0..left-1 each complete the subarray ending at right
        count += left;
    }
    return (int) count;
}

Explanation

First count total, the number of distinct values in the entire array. A subarray is complete exactly when it contains all total distinct values — it can never contain more.

The key observation: if a subarray [i, right] is complete, then every shorter-start subarray [i', right] with i' ≤ i is also complete, because shrinking from the right keeps every value that was present. So for each fixed right end we only need the largest start index that still leaves the window complete.

We slide a window with a frequency map freq. For each right we add nums[right], then advance left as long as the window still has all total distinct values. The moment the window drops below total distinct, the previous left positions 0 … left-1 were each a valid start that kept the window complete — so we add left to the answer.

Because left only ever moves forward, every element enters and leaves the window at most once, giving a single linear pass.

Example: nums = [1,3,1,2,2], total = 3. The running count accumulates 0, 0, 0, 2, 2 across the five right ends, summing to 4 complete subarrays.

Time: O(n) Space: O(n)