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:
-
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 variablecnt
.1cnt = len(set(nums))
-
A counter
d
from thecollections
module is used to keep track of the frequency of elements within the current window as we scan through the array.1d = Counter()
-
Two pointers are used:
i
for the start of the window andj
for the end of the window. The variableans
is used to store the total number of complete subarrays found so far, andn
represents the length of the arraynums
.1ans, n = 0, len(nums) 2i = 0
-
The algorithm iterates over the elements of
nums
using a for loop, withj
acting as the window's end.1for j, x in enumerate(nums):
-
Inside the loop, the counter
d
is updated with the current elementx
.1d[x] += 1
-
A while loop is used to check whether the current window is complete (i.e., the length of
d
equalscnt
). If it is complete, we addn - j
toans
, because all subarrays starting fromi
toj
are complete subarrays.1while len(d) == cnt: 2 ans += n - j
-
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])
-
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 EvaluatorExample 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
. Updated
with this elementd[1] = 1
. - For
j = 1
,nums[j] = 2
. Updated
with this elementd[2] = 1
. - For
j = 2
,nums[j] = 1
. Updated
with this elementd[1] = 2
. - Up until now,
len(d) != cnt
, so no complete subarray here.
Step 5 & 6: Continue iterating.
- For
j = 3
,nums[j] = 3
. Updated
with this elementd[3] = 1
. - Now
len(d) == cnt
, we have a complete window fromi = 0
toj = 3
. Each subarray starting fromi
toj
is complete. Sincen - 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 ofnums[i]
which isnums[0] = 1
. Sinced[1]
becomes1
(not zero), we don't remove it.- Increment
i
to1
. The window is now fromi = 1
toj = 3
andlen(d) == cnt
still holds, so we addn - j = 2
more subarrays[2, 1, 3]
,[1, 3]
.
Continue this process:
- Move
i
to2
,d[nums[1]]
which isd[2]
is decremented, the count is now zero, and we remove2
fromd
. - The window is no longer complete (
len(d) != cnt
), so break thewhile
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.
Which of the following shows the order of node visit in a Breadth-first Search?
Recommended Readings
https algomonster s3 us east 2 amazonaws com cover_photos stack svg Sliding Window Maximum Monotonic Stack We have an array and a sliding window defined by a start index and an end index The sliding window moves from left of the array to right There are always k elements in
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
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.