You are given an array nums consisting of positive integers.
We call a subarray of an array complete if the following condition is satisfied:
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 <= 10001 <= nums[i] <= 2000Problem Overview: You are given an integer array and need to count subarrays that contain every distinct value present in the entire array. A subarray is considered complete if it includes all unique elements that appear anywhere in the array.
Approach 1: Brute Force with Set (O(n²) time, O(k) space)
First compute k, the number of distinct elements in the array using a set. Then iterate over every starting index and extend the subarray to the right while tracking elements in another set. Each time the set size becomes k, the current subarray is complete. Continue expanding to count additional valid subarrays. This approach is simple and demonstrates the definition of a complete subarray clearly, but it checks too many ranges and becomes slow for large inputs.
Approach 2: Sliding Window with HashMap (O(n) time, O(k) space)
Start by computing the total number of distinct elements k. Then use a sliding window with two pointers and a frequency map. Expand the right pointer and store counts in a hash table. Once the window contains all k distinct values, every extension of this window to the right also remains complete. That means you can add n - right subarrays to the answer immediately. Then shrink the window from the left, updating frequencies until the window is no longer complete, and continue scanning. Each element enters and leaves the window at most once, which keeps the algorithm linear.
The key insight is recognizing that once a window contains all required distinct values, any larger window starting at the same left boundary is also valid. This allows counting multiple subarrays in constant time instead of checking each one individually.
Recommended for interviews: Interviewers expect the Sliding Window with HashMap approach. The brute force method shows you understand the definition of a complete subarray, but the optimized two-pointer strategy demonstrates mastery of array traversal and window-based counting patterns, which are common in medium-level interview problems.
This approach uses a sliding window technique in combination with a HashMap (or dictionary) to keep track of the distinct elements within the window.
The solution uses a sliding window technique to efficiently count complete subarrays. It maintains a dictionary to hold the frequency of each element in the current window and counts the complete subarrays dynamically by shrinking the window from the left when a complete subarray is found.
Time Complexity: O(n), where n is the length of the array, because we are processing each element at most twice.
Space Complexity: O(d), where d is the number of distinct elements, needed for the HashMap to store frequencies.
First, we use a hash table to count the number of distinct elements in the array, denoted as cnt.
Next, we enumerate the left endpoint index i of the subarray and maintain a set s to store the elements in the subarray. Each time we move the right endpoint index j to the right, we add nums[j] to the set s and check whether the size of the set s equals cnt. If it equals cnt, it means the current subarray is a complete subarray, and we increment the answer by 1.
After the enumeration ends, we return the answer.
Time complexity: O(n^2), Space complexity: O(n), where n is the length of the array.
Similar to Solution 1, we can use a hash table to count the number of distinct elements in the array, denoted as cnt.
Next, we use two pointers to maintain a sliding window, where the right endpoint index is j and the left endpoint index is i.
Each time we fix the left endpoint index i, we move the right endpoint index j to the right. When the number of distinct elements in the sliding window equals cnt, it means that all subarrays from the left endpoint index i to the right endpoint index j and beyond are complete subarrays. We then increment the answer by n - j, where n is the length of the array. Afterward, we move the left endpoint index i one step to the right and repeat the process.
Time complexity: O(n), Space complexity: O(n), where n is the length of the array.
| Approach | Complexity |
|---|---|
| Sliding Window with HashMap | Time Complexity: O(n), where n is the length of the array, because we are processing each element at most twice. |
| Hash Table + Enumeration | — |
| Hash Table + Two Pointers | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force with Set | O(n²) | O(k) | Good for understanding the definition of complete subarrays or when constraints are very small |
| Sliding Window with HashMap | O(n) | O(k) | Optimal approach for large arrays and typical interview scenarios |
Count Complete Subarrays in an Array | Khandani Template | Dry Run | Leetcode 2799 |codestorywithMIK • codestorywithMIK • 8,640 views views
Watch 9 more video solutions →Practice Count Complete Subarrays in an Array with our built-in code editor and test cases.
Practice on FleetCode