Count Complete Subarrays in an Array

Count Complete Subarrays in an Array

What is this problem about?

The Count Complete Subarrays in an Array coding problem defines a "complete" subarray as one that contains all the distinct elements present in the original array. You are given an array nums, and you need to count how many such complete subarrays exist.

Why is this asked in interviews?

Companies like Meta, Amazon, and Google use the Sliding Window interview pattern for this problem. It’s a "Medium" difficulty task that tests whether you can optimize a subarray counting problem from O(N^2) to O(N). It evaluates your ability to maintain a dynamic frequency count of distinct elements within a sliding window.

Algorithmic pattern used

This is a Sliding Window / Two Pointers problem.

1. Find the total number of distinct elements in the entire array (using a Set). Let this be K.
2. Use two pointers, left and right, to maintain a window.
3. Expand right until the window contains K distinct elements.
4. Once the window is "complete", every subarray starting at left and ending at any index from right to n-1 is also complete.
5. Add n - right to the total count, then increment left and repeat.

Example explanation

nums = [1, 3, 1, 2, 2]. Distinct elements = {1, 2, 3} (K=3).

1. right moves to index 3: [1, 3, 1, 2]. This contains all 3 distinct elements.
2. Since [1, 3, 1, 2] is complete, [1, 3, 1, 2, 2] is also complete. Count += 2.
3. Move left to index 1: [3, 1, 2]. Still has 3 distinct elements.
4. Count += 2 (Subarrays [3, 1, 2] and [3, 1, 2, 2]).
5. Move left to index 2: [1, 2, 2]. Only 2 distinct elements. Move right...

Common mistakes candidates make

• Re-counting Distincts: Calculating the number of distinct elements in the window from scratch in every step, making it O(N^2). Use a Hash Map to track frequencies in O(1).
• Off-by-one: Incorrectly calculating how many subarrays are formed once a complete window is found.
• Wrong Target: Using the length of the array instead of the number of distinct elements as the target K.

Interview preparation tip

"At least K distinct elements" problems are almost always solvable with a sliding window. The key insight is that if a window [L, R] is valid, then [L, R+1], [L, R+2]... are also valid.