Skip to main content
Talentd

Count Complete Subarrays in an Array - Solution & Explanation

MediumArrayHash TableSliding Window22 min readAsked at: Amazon, Meta, Google +1
Practice this problem

Problem Statement

You are given an array nums consisting of positive integers.

We call a subarray of an array complete if the following condition is satisfied:

  • 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 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 <= 1000
  • 1 <= nums[i] <= 2000

Approach Overview

Problem 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 1: Sliding Window with HashMap

This approach uses a sliding window technique in combination with a HashMap (or dictionary) to keep track of the distinct elements within the window.

  1. First, count the number of distinct elements in the whole array.
  2. Use two pointers, start and end, to define the window's range, and a HashMap to track the frequency of elements within this window.
  3. Expand the window by moving the end pointer and update the map to add the frequency of the element. Keep track of the number of distinct elements using a counter.
  4. If the window contains the same number of distinct elements as the entire array, try shrinking the window from the left by moving the start pointer, updating the map, and counting the subarrays formed.
  5. Repeat until the end pointer reaches the end of the array.

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.

Code

PythonJavaC++CC#JavaScript

Python

Java

C++

C

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Hash Table + Enumeration

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.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Approach 3: Hash Table + Two Pointers

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.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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.
Space Complexity: O(d), where d is the number of distinct elements, needed for the HashMap to store frequencies.

Hash Table + Enumeration—
Hash Table + Two Pointers—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force with SetO(n²)O(k)Good for understanding the definition of complete subarrays or when constraints are very small
Sliding Window with HashMapO(n)O(k)Optimal approach for large arrays and typical interview scenarios

Video Solution

Count Complete Subarrays in an Array | Khandani Template | Dry Run | Leetcode 2799 |codestorywithMIK • codestorywithMIK • 9,079 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Count Complete Subarrays in an Array easy or hard?
The problem is rated Medium on LeetCode. The difficulty comes from recognizing the sliding window counting trick where one valid window represents multiple subarrays. Once that insight is clear, the implementation is straightforward.
Count Complete Subarrays in an Array Python/Java solution
Most implementations use a sliding window with a dictionary or HashMap to store counts. Python typically uses collections.Counter or defaultdict, while Java uses HashMap<Integer, Integer>. Both maintain frequencies while moving two pointers through the array in O(n) time.
How to solve Count Complete Subarrays in an Array in O(n)?
Compute the number of unique values in the array, then use two pointers and a hash map to maintain element frequencies inside the window. Expand the right pointer until the window contains all distinct elements. At that point, add n - right to the answer because every larger window is also valid, then move the left pointer to continue scanning.
What is the best approach for Count Complete Subarrays in an Array?
The optimal approach uses a sliding window with a hash map. First compute the number of distinct elements in the entire array. Then expand a window with two pointers while tracking element frequencies. When the window contains all distinct elements, count all valid extensions and shrink the window. This runs in O(n) time and O(k) space.
Is Count Complete Subarrays in an Array asked at Google/Amazon/Meta?
Sliding window counting problems like this frequently appear in interviews at companies such as Amazon, Google, and Meta. Variations often involve counting subarrays with exactly K distinct elements or all unique elements, which rely on similar two‑pointer techniques.
What data structure is used in Count Complete Subarrays in an Array?
The main data structure is a hash table (or hash map) used to store frequencies of elements inside the sliding window. A set is also used initially to determine the total number of distinct elements in the array.
What is the time complexity of Count Complete Subarrays in an Array?
The optimal sliding window solution runs in O(n) time because each element is added to and removed from the window at most once. Space complexity is O(k), where k is the number of distinct elements stored in the frequency map.

Ready to solve this problem?

Practice Count Complete Subarrays in an Array with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Substring Without Repeating Characters

Next

Subarrays with K Different Integers