Watch 10 video solutions for Count Complete Subarrays in an Array, a medium level problem involving Array, Hash Table, Sliding Window. This walkthrough by codestorywithMIK has 8,640 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |