Problem Informations

• Problem Index: 2799
• Problem Link: Count Complete Subarrays in an Array
• Topics: Array, Hash Table, Sliding Window

Problem Description

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 \leq \text{nums.length} \leq 1000$
• $1 \leq \text{nums}[i] \leq 2000$

Intuition

To solve this problem, the main idea is to identify subarrays within the given array nums such that each subarray contains all distinct elements present in the entire array. The key observation is that we need to track how many distinct elements exist in a given window of the subarray. This can be efficiently achieved by using the sliding window technique combined with a data structure that allows quick updates and queries of distinct element counts, such as a map or set.

Approach

The solution employs a sliding window approach with two pointers to achieve the desired results. Here’s how the approach works:

1. Initialization:

   • Compute the total number of distinct elements in the entire array using a set, which automatically filters out duplicate elements.
   • Initialize two pointers, left and right, which represent the bounds of the current sliding window. Start both pointers at the beginning of the array.
   • Use an integer variable currentDistinct to track the number of distinct elements within the current window.
   • Use a map count to keep track of the occurrences of each element within the window.

2. Sliding Window Expansion:

   • Incrementally move the right pointer to expand the window by adding the current element at nums[right] into the window.
   • If this element is introduced into the window for the first time (i.e., its count in the map was previously zero), increment currentDistinct.

3. Sliding Window Contraction:

   • Shift the left pointer to shrink the window if there are duplicate elements; specifically, if the count of the element at nums[left] is greater than one, decrement its count and move the left pointer forward.

4. Counting Complete Subarrays:

   • After adjusting the window so that currentDistinct matches the total number of distinct elements, calculate the number of possible subarrays. This is given by the current position of the left pointer plus one, because any smaller subarray starting from left to right will also be complete.
   • Add this count to the answer.

5. Iterate Until Completion:

   • Continue expanding the window by moving the right pointer until it traverses the entire array.

6. Result:

   • The accumulated answer after the loop finishes gives the total number of complete subarrays.

By following these steps, each possible subarray that meets the criteria is counted efficiently, ensuring that the algorithm remains within acceptable time complexity limits, given the constraints of the problem.

Code

C++

class Solution {
public:
    int countCompleteSubarrays(vector<int>& nums) {
        // Initialize a set with all distinct elements from the array
        set<int> distinctSet(nums.begin(), nums.end());

        // Initialize pointers and variables for the sliding window technique
        int left = 0, right = 0, answer = 0;
        int len = nums.size();
        int totalDistinct = distinctSet.size();
        int currentDistinct = 0;
        
        // Map to keep track of the count of elements in the current window
        map<int, int> count;

        // Iterate through the array with 'right' indicating the end of the window
        for (; right < len; right++) {
            // Increase the count of the current element
            // If this element is seen for the first time, increase the distinct count
            if (++count[nums[right]] == 1) {
                currentDistinct++;
            }

            // Increment 'left' to reduce window size if an element occurs more than once
            while (count[nums[left]] > 1) {
                count[nums[left++]]--;
            }

            // If the number of distinct elements in the window equals the total number of distinct elements
            // Add to answer the count of subarrays that can be formed with the current window 
            if (totalDistinct == currentDistinct) {
                answer += left + 1;
            }
        }
        
        return answer;
    }
};

Python

class Solution:
    def countCompleteSubarrays(self, nums):
        # Initialize a set with all distinct elements from the array
        distinctSet = set(nums)

        # Initialize pointers and variables for the sliding window technique
        left = 0
        right = 0
        answer = 0
        length = len(nums)
        totalDistinct = len(distinctSet)
        currentDistinct = 0
        
        # Dictionary to keep track of the count of elements in the current window
        count = {}

        # Iterate through the array with 'right' indicating the end of the window
        while right < length:
            # Increase the count of the current element
            # If this element is seen for the first time, increase the distinct count
            if nums[right] in count:
                count[nums[right]] += 1
            else:
                count[nums[right]] = 1
            
            if count[nums[right]] == 1:
                currentDistinct += 1

            # Increment 'left' to reduce window size if an element occurs more than once
            while count[nums[left]] > 1:
                count[nums[left]] -= 1
                left += 1

            # If the number of distinct elements in the window equals the total number of distinct elements
            # Add to answer the count of subarrays that can be formed with the current window 
            if totalDistinct == currentDistinct:
                answer += left + 1
            
            right += 1
        
        return answer

Complexity

• Time complexity: The time complexity of the solution is $O(n)$, where $n$ is the length of the input array nums. This is because the algorithm makes a single pass through the array with the help of the sliding window technique using two pointers, left and right. Each element is processed at most twice, once when the right pointer includes it in the window and, potentially, once more when the left pointer excludes it from the window.

• Space complexity: The space complexity of the solution is $O(n)$ in the worst case, primarily due to the count map, which may need to store each element of the input array individually if all elements are distinct. Additionally, a set is used to store distinct elements from the array initially, which also can contain each element of the array once if all elements are unique. Thus, the collective space usage is related linearly to the size of the input.