Problem

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.

Examples

Example 1:

1
2
3

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:

1
2
3

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

Solution

Method 1 - Using sliding window

We need to count the number of complete subarrays in the array nums.

  1. A subarray is complete if the count of distinct elements in it equals the count of distinct elements in the entire array nums.
  2. To solve this problem, the sliding window technique with hashing can be used efficiently. The sliding window allows us to dynamically validate subarrays while avoiding unnecessary computations.

Approach

  1. Compute the number of distinct elements in the array nums using a set. Let’s call this value total_distinct.
  2. Use a sliding window strategy to traverse possible subarrays. Maintain a hash map (or dictionary) to keep track of the frequency of elements within the window.
  3. For each valid subarray (with total_distinct elements), increment the count of complete subarrays.
  4. Iterate over all possible subarray starting points using the above technique.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution {

    public int countCompleteSubarrays(int[] nums) {
        Set<Integer> distinctSet = new HashSet<>();
        for (int num : nums) {
            distinctSet.add(num);
        }
        int totalDistinct = distinctSet.size();
        Map<Integer, Integer> freqMap = new HashMap<>();
        int ans = 0, left = 0;

        for (int right = 0; right < nums.length; right++) {
            // Add current element to the frequency map
            freqMap.put(nums[right], freqMap.getOrDefault(nums[right], 0) + 1);

            // Check for complete subarrays for the current window
            while (freqMap.size() == totalDistinct) {
                ans += nums.length - right; // Count all extensions to the right
                freqMap.put(nums[left], freqMap.get(nums[left]) - 1);
                if (freqMap.get(nums[left]) == 0) {
                    freqMap.remove(nums[left]);
                }
                left++;
            }
        }

        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
    def countCompleteSubarrays(self, nums: List[int]) -> int:
        total_distinct = len(set(nums))  # Calculate total distinct numbers in the array
        freq_map = {}
        ans = 0
        left = 0

        for right in range(len(nums)):
            # Add current element to the frequency map
            freq_map[nums[right]] = freq_map.get(nums[right], 0) + 1
            
            # Check for complete subarrays for current window
            while len(freq_map) == total_distinct:
                ans += len(nums) - right  # Count all extensions to the right
                freq_map[nums[left]] -= 1
                if freq_map[nums[left]] == 0:
                    del freq_map[nums[left]]
                left += 1
        
        return ans

Complexity

  • ⏰ Time complexity: O(n). The computation of distinct elements in the array takes O(n) using a set.
    • The sliding window approach also traverses the array once, yielding O(n) overall.
  • 🧺 Space complexity: O(n). The hash map/dictionary can hold up to n elements in the worst case (if all elements are unique).