Count Complete Subarrays in an Array

Problem

A subarray is "complete" if it contains every distinct element of the whole array at least once. Count the number of complete subarrays.

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

Python Solution

def count_complete_subarrays(nums):
    total_distinct = len(set(nums))
    left = 0
    counts = {}
    result = 0
    for right, num in enumerate(nums):
        counts[num] = counts.get(num, 0) + 1
        while len(counts) == total_distinct:
            result += len(nums) - right
            counts[nums[left]] -= 1
            if counts[nums[left]] == 0:
                del counts[nums[left]]
            left += 1
    return result

C++ Solution

int countCompleteSubarrays(vector<int>& nums) {
    unordered_set<int> distinctSet(nums.begin(), nums.end());
    int totalDistinct = distinctSet.size();
    int left = 0, result = 0;
    unordered_map<int, int> counts;
    for (int right = 0; right < nums.size(); right++) {
        counts[nums[right]]++;
        while (counts.size() == totalDistinct) {
            result += nums.size() - right;
            counts[nums[left]]--;
            if (counts[nums[left]] == 0) counts.erase(nums[left]);
            left++;
        }
    }
    return result;
}

Java Solution

class Solution {
    public int countCompleteSubarrays(int[] nums) {
        Set<Integer> distinctSet = new HashSet<>();
        for (int n : nums) distinctSet.add(n);
        int totalDistinct = distinctSet.size();
        int left = 0, result = 0;
        Map<Integer, Integer> counts = new HashMap<>();
        for (int right = 0; right < nums.length; right++) {
            counts.merge(nums[right], 1, Integer::sum);
            while (counts.size() == totalDistinct) {
                result += nums.length - right;
                int leftNum = nums[left];
                counts.merge(leftNum, -1, Integer::sum);
                if (counts.get(leftNum) == 0) counts.remove(leftNum);
                left++;
            }
        }
        return result;
    }
}

Complexity

Time: O(n) — the left pointer only moves forward across the whole pass. Space: O(d) — where d is the number of distinct elements in the array. Once a window contains all distinct values, every larger window ending at the same right pointer is also complete, which is why nums.size() - right can be added directly.