2799. Count Complete Subarrays in an Array

You are given an array nums consisting of positive integers.

We call a subarray of an array complete if the following condition is satisfied:

• The number of distinct elements in the subarray is equal to the number of distinct elements in the whole array.

Return the number of complete subarrays.

A subarray is a contiguous non-empty part of an array.

Example 1:

Input: nums = [1,3,1,2,2]
Output: 4
Explanation: The complete subarrays are the following: [1,3,1,2], [1,3,1,2,2], [3,1,2] and [3,1,2,2].

Example 2:

Input: nums = [5,5,5,5]
Output: 10
Explanation: The array consists only of the integer 5, so any subarray is complete. The number of subarrays that we can choose is 10.

Constraints:

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

Approach 01:

#include <vector>
#include <unordered_set>
using namespace std;

class Solution {
public:
    int countCompleteSubarrays(vector<int>& nums) {
        // Maximum possible value in nums
        constexpr int kMaxValue = 2000;  
        // Total number of distinct elements in the entire array
        int totalDistinctCount = unordered_set<int>(nums.begin(), nums.end()).size();
        
        int completeCount = 0;
        int windowDistinct = 0;
        vector<int> frequency(kMaxValue + 1, 0);
        int left = 0;
        
        for (int right = 0; right < nums.size(); ++right) {
            int currentNum = nums[right];
            if (++frequency[currentNum] == 1)
                ++windowDistinct;  // new distinct enters window
            
            // Shrink window from left until it no longer contains all distinct
            while (windowDistinct == totalDistinctCount) {
                int leftNum = nums[left++];
                if (--frequency[leftNum] == 0)
                    --windowDistinct;
            }
            
            // All subarrays ending at right and starting before 'left' are complete
            completeCount += left;
        }
        
        return completeCount;
    }
};

from typing import List

class Solution:
    def countCompleteSubarrays(self, nums: List[int]) -> int:
        totalDistinctCount = len(set(nums))
        completeCount = 0
        windowDistinct = 0
        frequency = {}
        left = 0

        for current in nums:
            frequency[current] = frequency.get(current, 0) + 1
            if frequency[current] == 1:
                windowDistinct += 1  # new distinct enters window

            # Shrink window from left until missing a distinct
            while windowDistinct == totalDistinctCount:
                leftNum = nums[left]
                frequency[leftNum] -= 1
                left += 1
                if frequency[leftNum] == 0:
                    windowDistinct -= 1

            # All subarrays ending at current index and starting before 'left' are complete
            completeCount += left

        return completeCount

Time Complexity:

• Initial Distinct Count:

  Building an unordered_set of all elements takes \(O(n)\) time.

• Sliding Window:

  Both pointers left and right each move at most \(n\) steps → \(O(n)\).

• Total Time Complexity:

  \(O(n)\), where \(n\) is the length of nums.

Space Complexity:

• Frequency Array:

  Uses a fixed-size array of length \(kMaxValue+1\), which is constant → \(O(1)\).

• Auxiliary Structures:

  An unordered_set to count initial distinct elements of size at most \(n\) → \(O(n)\).

• Total Space Complexity:

  \(O(n)\).