[Medium] 2799. Count Complete Subarrays in an Array

You are given an integer array nums.

We call a subarray complete if:

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 part of an array.

Examples

Example 1:

Input: nums = [1,3,1,2,2]
Output: 4
Explanation: The complete subarrays are the following:
- [1,3,1,2,2] at position 0 to 4
- [1,3,1,2] at position 0 to 3  
- [3,1,2,2] at position 1 to 4
- [1,2,2] at position 2 to 4

Example 2:

Input: nums = [5,5,5,5]
Output: 10
Explanation: The complete subarrays are the following:
- [5,5,5,5] at position 0 to 3
- [5,5,5] at position 0 to 2
- [5,5] at position 0 to 1
- [5] at position 0 to 0
- [5,5,5] at position 1 to 3
- [5,5] at position 1 to 2
- [5] at position 1 to 1
- [5,5] at position 2 to 3
- [5] at position 2 to 2
- [5] at position 3 to 3

Constraints

1 <= nums.length <= 1000
1 <= nums[i] <= 2000

Clarification Questions

Before diving into the solution, here are 5 important clarifications and assumptions to discuss during an interview:

Complete subarray definition: What is a “complete subarray”? (Assumption: Subarray that contains all distinct elements present in the original array)
Subarray requirement: Does subarray need to be contiguous? (Assumption: Yes - subarray is contiguous by definition)
Distinct elements: How do we determine distinct elements? (Assumption: Count unique values in original array - complete subarray must contain all of them)
Return value: What should we return? (Assumption: Count of complete subarrays - integer)
Empty subarray: Can an empty subarray be complete? (Assumption: No - need at least one element to contain distinct values)

Interview Deduction Process (20 minutes)

Step 1: Brute-Force Approach (5 minutes)

Initial Thought: “I need to count complete subarrays. Let me check all possible subarrays.”

Naive Solution: Check all possible subarrays, for each check if it contains all distinct values from original array, count valid ones.

Complexity: O(n² × m) time where m is distinct count, O(m) space

Issues:

O(n² × m) time - inefficient
Repeats checking for overlapping subarrays
Doesn’t leverage sliding window
Can be optimized

Step 2: Semi-Optimized Approach (7 minutes)

Insight: “I can use sliding window. Expand window until it’s complete, then count valid subarrays.”

Improved Solution: Use sliding window. Expand right pointer until window contains all distinct values. Then all subarrays ending at right pointer and starting from left to some point are valid.

Complexity: O(n) time, O(m) space

Improvements:

Sliding window avoids redundant checks
O(n) time is much better
Handles all cases correctly
Can optimize counting

Step 3: Optimized Solution (8 minutes)

Final Optimization: “Sliding window approach is optimal. Track distinct count and count valid subarrays efficiently.”

Best Solution: Sliding window with hash map tracking distinct values. When window is complete, count all valid starting positions. Shrink window when needed.

Complexity: O(n) time, O(m) space

Key Realizations:

Sliding window is perfect for subarray problems
O(n) time is optimal - single pass
Hash map tracks distinct values efficiently
Count valid subarrays when window is complete

Solution: Optimized Sliding Window

Time Complexity: O(n)
Space Complexity: O(n)

Use two pointers with sliding window technique to efficiently count complete subarrays.

class Solution {
public:
    int countCompleteSubarrays(vector<int>& nums) {
        int cnt = 0;
        unordered_set<int> distinct(nums.begin(), nums.end());
        int distinct_cnt = distinct.size();
        unordered_map<int, int> freq;
        
        for(int left = 0, right = 0; right < (int) nums.size(); right++) {
            freq[nums[right]]++;
            while(freq.size() == distinct_cnt) {
                cnt += nums.size() - right;
                freq[nums[left]]--;
                if(freq[nums[left]] == 0) {
                    freq.erase(nums[left]);
                }
                left++;
            }
        }
        return cnt;
    }
};

How the Algorithm Works

Key Insight: Optimized Sliding Window

Use two pointers to maintain a window that contains all distinct elements. When the window is complete, count all subarrays that extend from the current position to the end.

Steps:

Count total distinct elements in the array
Expand right pointer to include new elements
When window is complete, count all valid subarrays and shrink from left
Continue until all subarrays are processed

Step-by-Step Example: `nums = [1,3,1,2,2]`

Step	Left	Right	Window	Freq Map	Complete?	Action
1	0	0	[1]	{1:1}	No	Expand right
2	0	1	[1,3]	{1:1,3:1}	No	Expand right
3	0	2	[1,3,1]	{1:2,3:1}	No	Expand right
4	0	3	[1,3,1,2]	{1:2,3:1,2:1}	Yes	Count: 5-3=2, shrink left
5	1	3	[3,1,2]	{3:1,1:1,2:1}	Yes	Count: 5-3=2, shrink left
6	2	3	[1,2]	{1:1,2:1}	No	Expand right
7	2	4	[1,2,2]	{1:1,2:2}	No	End

Total distinct elements: 3 (1, 3, 2)
Complete subarrays: 4 (2 + 2)

Visual Representation

nums = [1, 3, 1, 2, 2]
       0  1  2  3  4

Complete subarrays:
[1,3,1,2]     (indices 0-3) ✓
[1,3,1,2,2]   (indices 0-4) ✓  
[3,1,2]       (indices 1-3) ✓
[3,1,2,2]     (indices 1-4) ✓

Total: 4 complete subarrays

Algorithm Breakdown

1. Initialize Variables

unordered_set<int> distinct(nums.begin(), nums.end());
int distinct_cnt = distinct.size();
unordered_map<int, int> freq;

Purpose: Track total distinct elements and current window frequencies.

2. Two Pointers Sliding Window

for(int left = 0, right = 0; right < (int) nums.size(); right++) {
    freq[nums[right]]++;
    while(freq.size() == distinct_cnt) {
        cnt += nums.size() - right;
        freq[nums[left]]--;
        if(freq[nums[left]] == 0) {
            freq.erase(nums[left]);
        }
        left++;
    }
}

Process:

Expand right: Add new element to window
Check completeness: When all distinct elements are present
Count subarrays: All subarrays from current position to end are complete
Shrink left: Remove elements until window is no longer complete

Key Insight: `cnt += nums.size() - right;`

This line is the core optimization of the algorithm. When the window [left, right] contains all distinct elements, all subarrays that start at left and end at or after right are complete.

Mathematical Explanation:

Current window: [left, right] (complete)
Remaining positions: right+1, right+2, ..., nums.size()-1
Number of complete subarrays: nums.size() - right

Example: nums = [1,3,1,2,2], right = 3

Current window: [1,3,1,2] (indices 0-3) ✓ Complete
Remaining positions: 4 (index 4)
Complete subarrays: [1,3,1,2] and [1,3,1,2,2] = 2 subarrays
Calculation: 5 - 3 = 2 ✓

Why this works:

If [left, right] is complete, then [left, right+1], [left, right+2], …, [left, nums.size()-1] are also complete
We don’t need to check each one individually
This optimization reduces time complexity from O(n²) to O(n)

Visual Example: `cnt += nums.size() - right;`

Scenario: nums = [1,3,1,2,2], left = 0, right = 3

Array:     [1, 3, 1, 2, 2]
Indices:    0  1  2  3  4
            ↑           ↑
          left        right

Current window: [1,3,1,2] (indices 0-3) ✓ Complete

All complete subarrays starting at left=0:

[1,3,1,2] (indices 0-3) ✓
[1,3,1,2,2] (indices 0-4) ✓

Calculation: nums.size() - right = 5 - 3 = 2 ✓

Why extending right doesn’t break completeness:

Adding more elements to a complete subarray keeps it complete
We already have all distinct elements: {1, 3, 2}
Adding duplicates (like the second ‘2’) doesn’t change distinct count

Alternative Approaches

Approach 1: Nested Loops (Original)

class Solution {
public:
    int countCompleteSubarrays(vector<int>& nums) {
        int cnt = 0;
        unordered_set<int> distinct(nums.begin(), nums.end());
        int total_unique = distinct.size();

        for (int left = 0; left < nums.size(); ++left) {
            unordered_map<int, int> window_counts;
            for (int right = left; right < nums.size(); ++right) {
                window_counts[nums[right]]++;
                if (window_counts.size() == total_unique) {
                    cnt++;
                }
            }
        }

        return cnt;
    }
};

Time Complexity: O(n²)
Space Complexity: O(n)

Approach 2: Brute Force with Set

class Solution {
public:
    int countCompleteSubarrays(vector<int>& nums) {
        int n = nums.size();
        unordered_set<int> distinct(nums.begin(), nums.end());
        int total_unique = distinct.size();
        int cnt = 0;

        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                unordered_set<int> subarray_elements;
                for (int k = i; k <= j; k++) {
                    subarray_elements.insert(nums[k]);
                }
                if (subarray_elements.size() == total_unique) {
                    cnt++;
                }
            }
        }

        return cnt;
    }
};

Time Complexity: O(n³)
Space Complexity: O(n)

Complexity Analysis

Approach	Time Complexity	Space Complexity
Optimized Sliding Window	O(n)	O(n)
Nested Loops	O(n²)	O(n)
Brute Force	O(n³)	O(n)

Edge Cases

Single element: nums = [1] → 1
All same elements: nums = [5,5,5,5] → 10
All distinct elements: nums = [1,2,3,4] → 1
Two distinct elements: nums = [1,2,1,2] → 3

Key Insights

Two Pointers: Use left and right pointers to maintain sliding window
Complete Window: When window contains all distinct elements, count all valid subarrays
Efficient Counting: cnt += nums.size() - right counts all subarrays from current position to end
Window Shrinking: Remove elements from left until window is no longer complete
Linear Time: Each element is processed at most twice (once by each pointer)

Common Mistakes

Wrong distinct count: Not counting total distinct elements correctly
Incomplete window check: Not checking if window has all distinct elements
Index bounds: Off-by-one errors in loop boundaries
Hash map updates: Not properly updating element counts

Detailed Example Walkthrough

Example: `nums = [1,3,1,2,2]`

Step 1: Count distinct elements

distinct = {1, 3, 2}
total_unique = 3

Step 2: Check all subarrays

Left = 0:
  Right = 0: [1] → {1} → size = 1 ≠ 3
  Right = 1: [1,3] → {1,3} → size = 2 ≠ 3  
  Right = 2: [1,3,1] → {1,3} → size = 2 ≠ 3
  Right = 3: [1,3,1,2] → {1,3,2} → size = 3 = 3 ✓
  Right = 4: [1,3,1,2,2] → {1,3,2} → size = 3 = 3 ✓

Left = 1:
  Right = 1: [3] → {3} → size = 1 ≠ 3
  Right = 2: [3,1] → {3,1} → size = 2 ≠ 3
  Right = 3: [3,1,2] → {3,1,2} → size = 3 = 3 ✓
  Right = 4: [3,1,2,2] → {3,1,2} → size = 3 = 3 ✓

Left = 2:
  Right = 2: [1] → {1} → size = 1 ≠ 3
  Right = 3: [1,2] → {1,2} → size = 2 ≠ 3
  Right = 4: [1,2,2] → {1,2} → size = 2 ≠ 3

Left = 3:
  Right = 3: [2] → {2} → size = 1 ≠ 3
  Right = 4: [2,2] → {2} → size = 1 ≠ 3

Left = 4:
  Right = 4: [2] → {2} → size = 1 ≠ 3

Total complete subarrays: 4

Optimization Opportunities

1. Early Termination

if (window_counts.size() == total_unique) {
    cnt += (nums.size() - right);  // All remaining subarrays are complete
    break;
}

2. Set Instead of Map

unordered_set<int> window_elements;
// Only track presence, not frequency

3. Two Pointers Optimization

// Use two pointers to find minimum window with all elements
// Then count all subarrays containing this window

Why This Solution is Optimal

Linear Time Complexity: O(n) is optimal for this problem
Two Pointers Technique: Each element visited at most twice
Efficient Counting: Counts all valid subarrays in one operation
Optimal Space: O(n) space for frequency tracking
Clear Logic: Easy to understand and implement

Robina Li

[Medium] 2799. Count Complete Subarrays in an Array

[Medium] 2799. Count Complete Subarrays in an Array

Examples

Constraints

Clarification Questions

Interview Deduction Process (20 minutes)

Step 1: Brute-Force Approach (5 minutes)

Step 2: Semi-Optimized Approach (7 minutes)

Step 3: Optimized Solution (8 minutes)

Solution: Optimized Sliding Window

How the Algorithm Works

Key Insight: Optimized Sliding Window

Step-by-Step Example: `nums = [1,3,1,2,2]`

Visual Representation

Algorithm Breakdown

1. Initialize Variables

2. Two Pointers Sliding Window

Key Insight: `cnt += nums.size() - right;`

Visual Example: `cnt += nums.size() - right;`

Alternative Approaches

Approach 1: Nested Loops (Original)

Approach 2: Brute Force with Set

Complexity Analysis

Edge Cases

Key Insights

Common Mistakes

Detailed Example Walkthrough

Example: `nums = [1,3,1,2,2]`

Optimization Opportunities

1. Early Termination

2. Set Instead of Map

3. Two Pointers Optimization

Why This Solution is Optimal

Related Posts

Recent Posts

[Medium] 2799. Count Complete Subarrays in an Array

Examples

Constraints

Clarification Questions

Interview Deduction Process (20 minutes)

Step 1: Brute-Force Approach (5 minutes)

Step 2: Semi-Optimized Approach (7 minutes)

Step 3: Optimized Solution (8 minutes)

Solution: Optimized Sliding Window

How the Algorithm Works

Key Insight: Optimized Sliding Window

Step-by-Step Example: nums = [1,3,1,2,2]

Visual Representation

Algorithm Breakdown

1. Initialize Variables

2. Two Pointers Sliding Window

Key Insight: cnt += nums.size() - right;

Visual Example: cnt += nums.size() - right;

Alternative Approaches

Approach 1: Nested Loops (Original)

Approach 2: Brute Force with Set

Complexity Analysis

Edge Cases

Key Insights

Common Mistakes

Detailed Example Walkthrough

Example: nums = [1,3,1,2,2]

Optimization Opportunities

1. Early Termination

2. Set Instead of Map

3. Two Pointers Optimization

Related Problems

Why This Solution is Optimal

Related Posts

Recent Posts

Step-by-Step Example: `nums = [1,3,1,2,2]`

Key Insight: `cnt += nums.size() - right;`

Visual Example: `cnt += nums.size() - right;`

Example: `nums = [1,3,1,2,2]`