2799. Count Complete Subarrays in an Array


Problem Description

In this problem, you are provided with an array called nums, which contains positive integers. Your task is to count what's known as "complete" subarrays within this array. A subarray is considered "complete" if it contains exactly the same distinct elements as are present in the entire array. To clarify, a subarray is a contiguous sequence of elements within the array. The main goal is to find the number of such unique complete subarrays.

Intuition

The intuition behind solving this problem lies in recognizing that a complete subarray must end at some point where all distinct elements in nums are included up to that point. The idea is to move through the array with a sliding window, tracking the frequency of elements in the current window using a counter.

Once a window contains all distinct elements (i.e., the length of the counter is equal to the total number of distinct elements in nums), we can say each subarray starting from the current beginning of the window (i) to the current end of the window (j) is a complete subarray. This is because the end, j, includes all unique elements, so any subarray from i to j will also include these elements.

Additionally, we know that for a fixed endpoint j, if a window is complete, extending that window to the right will also result in complete subarrays (as they'll also contain all distinct elements). Therefore, the number of complete subarrays ending at j can be determined by counting all possible starting points from the current start of the window i to j, which will be n - j (where n is the length of nums).

As we slide the window to the right incrementally, once a window no longer remains complete (an element's count drops to 0), we exit the inner loop, and proceed with expanding the end of the window (j) again to find a new complete subarray. By moving the start of the window (i) appropriately and using this approach, we ensure that we consider all complete subarrays exactly once.

Learn more about Sliding Window patterns.

Solution Approach

The solution follows a two-pointer technique, commonly used for problems involving contiguous subarrays or sequences. Here's a step-by-step explanation of how the algorithm is implemented:

  1. First, we need to determine the total number of distinct elements in the entire array nums. We use a set to find distinct elements and store the count in the variable cnt.

    1cnt = len(set(nums))
  2. A counter d from the collections module is used to keep track of the frequency of elements within the current window as we scan through the array.

    1d = Counter()
  3. Two pointers are used: i for the start of the window and j for the end of the window. The variable ans is used to store the total number of complete subarrays found so far, and n represents the length of the array nums.

    1ans, n = 0, len(nums)
    2i = 0
  4. The algorithm iterates over the elements of nums using a for loop, with j acting as the window's end.

    1for j, x in enumerate(nums):
  5. Inside the loop, the counter d is updated with the current element x.

    1d[x] += 1
  6. A while loop is used to check whether the current window is complete (i.e., the length of d equals cnt). If it is complete, we add n - j to ans, because all subarrays starting from i to j are complete subarrays.

    1while len(d) == cnt:
    2    ans += n - j
  7. To move the window forward, we decrease the count of the element at the start of the window and, if its count reaches zero, remove it from the counter.

    1d[nums[i]] -= 1
    2if d[nums[i]] == 0:
    3    d.pop(nums[i])
  8. After updating the counter, we increment i to shrink the window from the left.

    1i += 1

By using the two-pointer technique with the counter, we can efficiently check for complete subarrays and count them. The algorithm guarantees that no complete subarrays are missed and none are counted more than once, ensuring the correct result.

Finally, the value of ans reflects the total count of complete subarrays within nums, which is what we are asked to return.

1return ans

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's illustrate the solution approach with a small example.

Consider the array nums = [1, 2, 1, 3, 2]. We want to find all "complete" subarrays where a "complete" subarray contains exactly the distinct elements present in the entire array nums. In this example, the distinct elements are {1, 2, 3}, so every complete subarray must contain each of these numbers at least once.

Step 1: Determine the number of distinct elements. For nums, this is cnt = 3 ({1, 2, 3}).

Step 2: Initialize the counter d and other variables ans = 0, n = 5, and i = 0.

Step 3 & 4: Start iterating over the elements with two pointers i and j.

  • For j = 0, nums[j] = 1. Update d with this element d[1] = 1.
  • For j = 1, nums[j] = 2. Update d with this element d[2] = 1.
  • For j = 2, nums[j] = 1. Update d with this element d[1] = 2.
  • Up until now, len(d) != cnt, so no complete subarray here.

Step 5 & 6: Continue iterating.

  • For j = 3, nums[j] = 3. Update d with this element d[3] = 1.
  • Now len(d) == cnt, we have a complete window from i = 0 to j = 3. Each subarray starting from i to j is complete. Since n - j = 5 - 3 = 2, there are two subarrays [1, 2, 1, 3] and [2, 1, 3].

Step 7 & 8: To move the window:

  • while len(d) == cnt, we decrease the count of nums[i] which is nums[0] = 1. Since d[1] becomes 1 (not zero), we don't remove it.
  • Increment i to 1. The window is now from i = 1 to j = 3 and len(d) == cnt still holds, so we add n - j = 2 more subarrays [2, 1, 3], [1, 3].

Continue this process:

  • Move i to 2, d[nums[1]] which is d[2] is decremented, the count is now zero, and we remove 2 from d.
  • The window is no longer complete (len(d) != cnt), so break the while loop.

Step 4: Increment j to 4, and continue the process by filling up the counter again until we find new complete subarrays.

By continuously moving i and j and checking the completeness of the window, we can find all complete subarrays. In this example, the complete subarrays would be [1, 2, 1, 3], [2, 1, 3], [1, 3, 2], [3, 2].

The count ans is incremented each time we find a new complete subarray. After iterating through nums, we return the value of ans as the total count of complete subarrays.

Solution Implementation

1from collections import Counter
2
3class Solution:
4    def countCompleteSubarrays(self, nums):
5        # Count the number of unique elements in nums
6        unique_count = len(set(nums))
7        # Initialize a counter to keep track of the frequency of elements
8        elem_freq = Counter()
9        # Initialize the answer and get the length of the nums array
10        total_subarrays, length = 0, len(nums)
11        # Start pointer for the sliding window
12        start_index = 0
13      
14        # Iterate over nums with an end pointer for the sliding window
15        for end_index, value in enumerate(nums):
16            # Update the frequency count of the current element
17            elem_freq[value] += 1
18            # Shrink the window from the left if all unique elements are included
19            while len(elem_freq) == unique_count:
20                # Current number of complete subarrays is (length-end_index)
21                total_subarrays += length - end_index
22                # Decrease the freq count of the element at the start of the window
23                elem_freq[nums[start_index]] -= 1
24                # Remove the element from the counter if its count drops to zero
25                if elem_freq[nums[start_index]] == 0:
26                    elem_freq.pop(nums[start_index])
27                # Move the start pointer to the right
28                start_index += 1
29      
30        # Return the total number of complete subarrays
31        return total_subarrays
32
1class Solution {
2    public int countCompleteSubarrays(int[] nums) {
3        // A map to count the unique numbers in the array
4        Map<Integer, Integer> frequencyMap = new HashMap<>();
5      
6        // Initialize the map with the unique numbers in the array
7        for (int num : nums) {
8            frequencyMap.put(num, 1);
9        }
10      
11        // Store the size of the unique elements in the array
12        int uniqueCount = frequencyMap.size();
13        // Variable to hold the final result
14        int answer = 0;
15        // Length of the nums array
16        int arrayLength = nums.length;
17      
18        // Clear the map for reuse
19        frequencyMap.clear();
20      
21        // Sliding window approach
22        for (int left = 0, right = 0; right < arrayLength; ++right) {
23            // Add or update the count of the current element
24            frequencyMap.merge(nums[right], 1, Integer::sum);
25            // If the window contains all unique elements
26            while (frequencyMap.size() == uniqueCount) {
27                // Update the answer with the number of subarrays ending with nums[right]
28                answer += arrayLength - right;
29                // Move the left pointer, decrementing the frequency of the left-most element
30                if (frequencyMap.merge(nums[left], -1, Integer::sum) == 0) {
31                    // If the count goes to zero, remove the element from the map
32                    frequencyMap.remove(nums[left]);
33                }
34                ++left;
35            }
36        }
37      
38        // Return the total count of complete subarrays
39        return answer;
40    }
41}
42
1#include <vector>
2#include <unordered_map>
3using namespace std;
4
5class Solution {
6public:
7    // Method to count the number of complete subarrays
8    int countCompleteSubarrays(vector<int>& nums) {
9        // Create a map to store the unique elements and their counts
10        unordered_map<int, int> countsMap;
11      
12        // Initial loop to count the unique elements in the array
13        for (int num : nums) {
14            countsMap[num] = 1;
15        }
16      
17        // Store the size of the map, which is the count of unique elements
18        int uniqueCount = countsMap.size();
19      
20        // Clear the map to reuse it for counting in subarrays
21        countsMap.clear();
22      
23        // Variable to store the answer which is the number of complete subarrays
24        int completeSubarrays = 0;
25      
26        // Size of the input array
27        int arraySize = nums.size();
28      
29        // Two-pointer approach to find all complete subarrays
30        for (int start = 0, end = 0; end < arraySize; ++end) {
31            // Increase the count of the current end element in the map
32            countsMap[nums[end]]++;
33          
34            // When the map size equals the count of unique elements, we found a complete subarray
35            while (countsMap.size() == uniqueCount) {
36                // Add the number of complete subarrays that can be made with this start point
37                completeSubarrays += arraySize - end;
38              
39                // Reduce the count of the start element and erase it from the map if its count becomes zero
40                if (--countsMap[nums[start]] == 0) {
41                    countsMap.erase(nums[start]);
42                }
43              
44                // Move the start pointer forward
45                ++start;
46            }
47        }
48      
49        // Return the total count of complete subarrays
50        return completeSubarrays;
51    }
52};
53
1function countCompleteSubarrays(nums: number[]): number {
2    // Create a map to store the frequency of each unique number in the array
3    const frequencyMap: Map<number, number> = new Map();
4
5    // Populate the frequency map with the initial count of each number
6    for (const num of nums) {
7        frequencyMap.set(num, (frequencyMap.get(num) ?? 0) + 1);
8    }
9
10    // Count the number of unique elements in the input array
11    const uniqueElementCount = frequencyMap.size;
12  
13    // Clear the frequency map for reuse
14    frequencyMap.clear();
15  
16    const totalNums = nums.length; // Total number of elements in nums
17    let totalCompleteSubarrays = 0; // Initialize complete subarrays counter
18    let start = 0; // Initialize start pointer for subarrays
19  
20    // Iterate over the array using 'end' as the end pointer for subarrays
21    for (let end = 0; end < totalNums; ++end) {
22        // Increment the count for the current element in the frequency map
23        frequencyMap.set(nums[end], (frequencyMap.get(nums[end]) ?? 0) + 1);
24      
25        // While the current subarray contains all unique elements,
26        // keep updating the total count of complete subarrays and adjust the start pointer.
27        while (frequencyMap.size === uniqueElementCount) {
28            // Add the total possible subarrays from the current subarray to the result
29            totalCompleteSubarrays += totalNums - end;
30            // Decrement the count of the number at the start pointer
31            frequencyMap.set(nums[start], frequencyMap.get(nums[start])! - 1);
32            // If the start number count hits zero, remove it from the map
33            if (frequencyMap.get(nums[start]) === 0) {
34                frequencyMap.delete(nums[start]);
35            }
36            // Move the start pointer to the right
37            ++start;
38        }
39    }
40  
41    // Return the total count of complete subarrays
42    return totalCompleteSubarrays;
43}
44

Time and Space Complexity

The provided Python code calculates the number of complete subarrays in the input list nums. A complete subarray is defined such that all elements of the nums list are included in the subarray at least once. Here is the complexity analysis of the code:

Time Complexity:

The time complexity of the code is O(n), where n is the number of elements in the input list nums. Although the code contains a nested loop, the inner loop with variable i does not start from the beginning for each iteration of the outer loop with variable j. Instead, i picks up where it left off in the previous iteration. Each element is processed once by both i and j, hence the complexity is linear.

Space Complexity:

The space complexity is O(n) as well. The primary data structure contributing to space complexity is the Counter object d, which in the worst case contains as many unique keys as there are unique elements in nums. Additionally, the set of nums, which is created at the beginning of the method, also contributes to the space complexity if all elements are unique. However, since both structures depend on the number of unique elements in nums, and there can't be more unique elements than n, the space complexity remains O(n).

Learn more about how to find time and space complexity quickly using problem constraints.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Which of the following shows the order of node visit in a Breadth-first Search?


Recommended Readings

Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.