#2799

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Count Complete Subarrays in an Array

Count Complete Subarrays in an Array requires scanning the array while tracking elements to detect subarrays with all distinct values efficiently.

array hash table sliding window

Problem Statement

Given an array nums of positive integers, a subarray is defined as complete if it contains all distinct numbers present in nums. Your task is to determine how many such subarrays exist in the given array.

Return an integer representing the total number of complete subarrays. Subarrays are contiguous sections of the array, and each should include all distinct elements from the original array exactly once to be considered complete.

Examples

Example 1

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

Output: 4

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

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

Solution Approach

Identify Distinct Elements

First, scan the array once to determine the total number of distinct elements, k. Use a hash set or dictionary to track unique values efficiently.

Sliding Window with Hash Map

Maintain a window with two pointers and a hash map to count elements inside the current window. Expand the right pointer until all k distinct elements are present, then incrementally move the left pointer to count all valid subarrays ending at the right index.

Count Complete Subarrays

For each right pointer position where the window contains all k distinct elements, add the number of subarrays starting from the left pointer. Adjust counts in the hash map as the window slides to avoid double counting.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(n)

Time complexity is O(n) because each element is added and removed from the hash map at most once. Space complexity is O(n) due to storing counts of elements in the hash map for window tracking.

What Interviewers Usually Probe

Tracking distinct elements suggests using a hash map or set.
Sliding window optimization is expected for contiguous subarray counting.
Careful handling of duplicate values inside the window is critical.

Common Pitfalls or Variants

Common pitfalls

Failing to adjust the left pointer correctly can lead to overcounting subarrays.
Ignoring that the window must contain exactly all distinct elements causes wrong results.
Not updating the hash map counts properly when sliding the window.

Follow-up variants

Count subarrays with at most k distinct elements instead of exactly k.
Find the longest complete subarray instead of counting them.
Compute the number of subarrays missing exactly one distinct element.

FAQ

What does a complete subarray mean in this problem?

A complete subarray contains all distinct elements present in the original array.

How does the sliding window help in counting complete subarrays?

It allows expanding and contracting subarrays efficiently while tracking distinct elements, avoiding brute-force enumeration.

Can duplicates appear inside a complete subarray?

Yes, duplicates can exist, but the subarray must include at least one of each distinct element from the original array.

What is the time complexity for counting complete subarrays?

Using the sliding window and hash map approach, it is O(n) since each element is processed at most twice.

Does GhostInterview show the pattern used for this problem?

Yes, it highlights array scanning plus hash lookup with sliding window as the exact pattern for solving complete subarrays.

terminal

Solution

Solution 1: Hash Table + Enumeration

First, we use a hash table to count the number of distinct elements in the array, denoted as $cnt$.

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def countCompleteSubarrays(self, nums: List[int]) -> int:
        cnt = len(set(nums))
        ans, n = 0, len(nums)
        for i in range(n):
            s = set()
            for x in nums[i:]:
                s.add(x)
                if len(s) == cnt:
                    ans += 1
        return ans

Solution 2: 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$.

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def countCompleteSubarrays(self, nums: List[int]) -> int:
        cnt = len(set(nums))
        ans, n = 0, len(nums)
        for i in range(n):
            s = set()
            for x in nums[i:]:
                s.add(x)
                if len(s) == cnt:
                    ans += 1
        return ans

Continue Practicing

#2781 length of the longest valid substring #2831 find the longest equal subarray #2841 maximum sum of almost unique subarray