2799. Count Complete Subarrays in an Array - Solution

Q: 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.

Q: 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 . Both maintain frequencies while moving two pointers through the array in O(n) time.

The problem

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.

First, count the number of distinct elements in the whole array.
Use two pointers, start and end, to define the window's range, and a HashMap to track the frequency of elements within this window.
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.
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.
Repeat until the end pointer reaches the end of the array.

Python

def count_complete_subarrays(nums):
    n = len(nums)
    distinct_count = len(set(nums))
    start = 0
    end = 0
    current_map = {}
    current_distinct = 0
    complete_count = 0
    while end < n:
        if nums[end] not in current_map or current_map[nums[end]] == 0:
            current_distinct += 1
        current_map[nums[end]] = current_map.get(nums[end], 0) + 1
        while current_distinct >= distinct_count:
            complete_count += n - end
            current_map[nums[start]] -= 1
            if current_map[nums[start]] == 0:
                current_distinct -= 1
            start += 1
        end += 1
    return complete_count

# Example usage:
print(count_complete_subarrays([1,3,1,2,2]))  # Output: 4
print(count_complete_subarrays([5,5,5,5]))    # Output: 10

Java

import java.util.HashMap;
import java.util.HashSet;

public class CompleteSubarrays {
    public static int countCompleteSubarrays(int[] nums) {
        int n = nums.length;
        int start = 0, end = 0, totalComplete = 0;
        HashSet<Integer> distinctElements = new HashSet<>();
        for (int num : nums) {
            distinctElements.add(num);
        }
        int distinctCount = distinctElements.size();

        HashMap<Integer, Integer> map = new HashMap<>();
        int currentDistinct = 0;

        while (end < n) {
            if (!map.containsKey(nums[end]) || map.get(nums[end]) == 0) {
                currentDistinct++;
            }
            map.put(nums[end], map.getOrDefault(nums[end], 0) + 1);

            while (currentDistinct >= distinctCount) {
                totalComplete += n - end;
                map.put(nums[start], map.get(nums[start]) - 1);
                if (map.get(nums[start]) == 0) {
                    currentDistinct--;
                }
                start++;
            }
            end++;
        }
        return totalComplete;
    }

    public static void main(String[] args) {
        System.out.println(countCompleteSubarrays(new int[]{1, 3, 1, 2, 2})); // Output: 4
        System.out.println(countCompleteSubarrays(new int[]{5, 5, 5, 5})); // Output: 10
    }
}

C++

#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <iostream>

int countCompleteSubarrays(const std::vector<int>& nums) {
    int n = nums.size();
    std::unordered_set<int> distinct_nums(nums.begin(), nums.end());
    int distinct_count = distinct_nums.size();

    std::unordered_map<int, int> current_map;
    int start = 0, end = 0, current_distinct = 0, complete_count = 0;

    while (end < n) {
        if (current_map[nums[end]] == 0) {
            current_distinct++;
        }
        current_map[nums[end]]++;

        while (current_distinct >= distinct_count) {
            complete_count += (n - end);
            current_map[nums[start]]--;
            if (current_map[nums[start]] == 0) {
                current_distinct--;
            }
            start++;
        }
        end++;
    }

    return complete_count;
}

int main() {
    std::cout << countCompleteSubarrays({1, 3, 1, 2, 2}) << std::endl; // Output: 4
    std::cout << countCompleteSubarrays({5, 5, 5, 5}) << std::endl; // Output: 10
    return 0;
}

JavaScript

function countCompleteSubarrays(nums) {
    let n = nums.length;
    let distinctCount = new Set(nums).size;
    let map = new Map();
    let start = 0, end = 0, currentDistinct = 0, completeCount = 0;

    while (end < n) {
        if (!map.has(nums[end])) {
            map.set(nums[end], 0);
        }
        if (map.get(nums[end]) === 0) {
            currentDistinct++;
        }
        map.set(nums[end], map.get(nums[end]) + 1);

        while (currentDistinct >= distinctCount) {
            completeCount += n - end;
            map.set(nums[start], map.get(nums[start]) - 1);
            if (map.get(nums[start]) === 0) {
                currentDistinct--;
            }
            start++;
        }
        end++;
    }

    return completeCount;
}

console.log(countCompleteSubarrays([1, 3, 1, 2, 2])); // Output: 4
console.log(countCompleteSubarrays([5, 5, 5, 5])); // Output: 10;

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_NUM 2001

int countCompleteSubarrays(int* nums, int numSize) {
    int n = numSize;
    int distinct_count = 0;
    int element_count[MAX_NUM] = {0};
    for (int i = 0; i < n; i++) {
        if (element_count[nums[i]] == 0) distinct_count++;
        element_count[nums[i]]++;
    }
    memset(element_count, 0, sizeof(element_count));
    int start = 0, end = 0, current_distinct = 0, complete_count = 0;
    while (end < n) {
        if (element_count[nums[end]] == 0) current_distinct++;
        element_count[nums[end]]++;
        while (current_distinct >= distinct_count) {
            complete_count += (n - end);
            element_count[nums[start]]--;
            if (element_count[nums[start]] == 0) current_distinct--;
            start++;
        }
        end++;
    }
    return complete_count;
}

int main() {
    int nums1[] = {1, 3, 1, 2, 2};
    printf("%d\n", countCompleteSubarrays(nums1, 5)); // Output: 4
    int nums2[] = {5, 5, 5, 5};
    printf("%d\n", countCompleteSubarrays(nums2, 4)); // Output: 10
    return 0;
}

using System;
using System.Collections.Generic;

public class CompleteSubarrays {
    public static int CountCompleteSubarrays(int[] nums) {
        int n = nums.Length;
        var distinctSet = new HashSet<int>(nums);
        int distinctCount = distinctSet.Count;
        int start = 0, end = 0, currentDistinct = 0, completeCount = 0;
        var currentMap = new Dictionary<int, int>();

        while (end < n) {
            if (!currentMap.ContainsKey(nums[end]))
                currentMap[nums[end]] = 0;
            if (currentMap[nums[end]] == 0)
                currentDistinct++;
            currentMap[nums[end]]++;

            while (currentDistinct >= distinctCount) {
                completeCount += n - end;
                currentMap[nums[start]]--;
                if (currentMap[nums[start]] == 0)
                    currentDistinct--;
                start++;
            }
            end++;
        }
        return completeCount;
    }

    public static void Main() {
        Console.WriteLine(CountCompleteSubarrays(new int[] {1, 3, 1, 2, 2})); // Output: 4
        Console.WriteLine(CountCompleteSubarrays(new int[] {5, 5, 5, 5})); // Output: 10
    }
}

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.

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.

TypeScript

function countCompleteSubarrays(nums: number[]): number {
    const s: Set<number> = new Set(nums);
    const cnt = s.size;
    const n = nums.length;
    let ans = 0;
    for (let i = 0; i < n; ++i) {
        s.clear();
        for (let j = i; j < n; ++j) {
            s.add(nums[j]);
            if (s.size === cnt) {
                ++ans;
            }
        }
    }
    return ans;
}

func countCompleteSubarrays(nums []int) (ans int) {
	s := map[int]bool{}
	for _, x := range nums {
		s[x] = true
	}
	cnt := len(s)
	for i := range nums {
		s = map[int]bool{}
		for _, x := range nums[i:] {
			s[x] = true
			if len(s) == cnt {
				ans++
			}
		}
	}
	return
}

Rust

use std::collections::HashSet;

impl Solution {
    pub fn count_complete_subarrays(nums: Vec<i32>) -> i32 {
        let mut s = HashSet::new();
        for &x in &nums {
            s.insert(x);
        }
        let cnt = s.len();
        let n = nums.len();
        let mut ans = 0;

        for i in 0..n {
            s.clear();
            for j in i..n {
                s.insert(nums[j]);
                if s.len() == cnt {
                    ans += 1;
                }
            }
        }

        ans
    }
}

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.

TypeScript

function countCompleteSubarrays(nums: number[]): number {
    const d: Map<number, number> = new Map();
    for (const x of nums) {
        d.set(x, (d.get(x) ?? 0) + 1);
    }
    const cnt = d.size;
    d.clear();
    const n = nums.length;
    let ans = 0;
    let i = 0;
    for (let j = 0; j < n; ++j) {
        d.set(nums[j], (d.get(nums[j]) ?? 0) + 1);
        while (d.size === cnt) {
            ans += n - j;
            d.set(nums[i], d.get(nums[i])! - 1);
            if (d.get(nums[i]) === 0) {
                d.delete(nums[i]);
            }
            ++i;
        }
    }
    return ans;
}

func countCompleteSubarrays(nums []int) (ans int) {
	d := map[int]int{}
	for _, x := range nums {
		d[x] = 1
	}
	cnt := len(d)
	i, n := 0, len(nums)
	d = map[int]int{}
	for j, x := range nums {
		d[x]++
		for len(d) == cnt {
			ans += n - j
			d[nums[i]]--
			if d[nums[i]] == 0 {
				delete(d, nums[i])
			}
			i++
		}
	}
	return
}

Rust

use std::collections::HashMap;

impl Solution {
    pub fn count_complete_subarrays(nums: Vec<i32>) -> i32 {
        let mut d = HashMap::new();
        for &x in &nums {
            d.insert(x, 1);
        }
        let cnt = d.len();
        let mut ans = 0;
        let n = nums.len();
        d.clear();

        let (mut i, mut j) = (0, 0);
        while j < n {
            *d.entry(nums[j]).or_insert(0) += 1;
            while d.len() == cnt {
                ans += (n - j) as i32;
                let e = d.get_mut(&nums[i]).unwrap();
                *e -= 1;
                if *e == 0 {
                    d.remove(&nums[i]);
                }
                i += 1;
            }
            j += 1;
        }
        ans
    }
}

Try this approach in the editor

Complexity comparison

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. 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	–

Complexity analysis

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

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.

Count Complete Subarrays in an Array solution and explanation

The problem

Approach overview

Approach 1: Sliding Window with HashMap

Approach 2: Hash Table + Enumeration

Approach 3: Hash Table + Two Pointers

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Count Complete Subarrays in an Array solution and explanation

The problem

Approach overview

Approach 1: Sliding Window with HashMap

Approach 2: Hash Table + Enumeration

Approach 3: Hash Table + Two Pointers

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems