LeetCode 2799 - Count Complete Subarrays in an Array

The problem asks us to count the number of complete subarrays in a given array nums. A subarray is complete if it contains all distinct elements that exist in the entire array.

leetcodemediumarrayhash-tablesliding-window

LeetCode Problem 2799

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Sliding Window

Solution

Problem Understanding

The problem asks us to count the number of complete subarrays in a given array nums. A subarray is complete if it contains all distinct elements that exist in the entire array. In other words, if the total number of distinct elements in nums is k, then a complete subarray must also have exactly k distinct elements.

The input nums is an array of positive integers, and the output is a single integer representing how many contiguous subarrays satisfy this completeness condition. The constraints indicate that nums can be as long as 1000 elements, with each value in the range 1 to 2000. This means a naive O(n^3) brute-force approach could barely be acceptable, but we should strive for a better solution.

Important edge cases include arrays where all elements are the same, arrays where every element is unique, or arrays with repeated but uneven distributions of elements. These edge cases can easily break naive sliding window implementations if not handled carefully.

Approaches

Brute Force

The brute-force solution iterates over all possible subarrays. For each subarray, it calculates the number of distinct elements and compares it with the total distinct count of the array. If they match, the subarray is counted as complete. This approach is correct but inefficient because generating all subarrays is O(n^2) and checking distinct elements for each subarray can take O(n), leading to O(n^3) time complexity.

Optimal Approach

The key observation is that once we know the total number of distinct elements in nums, we can use a sliding window to efficiently count subarrays containing all distinct elements. By maintaining a window with a hash map of element counts, we can expand the window to the right until all distinct elements are included. For each valid window, all subarrays starting at the left index and ending anywhere in the current window or beyond are complete. This reduces unnecessary recomputation and brings the time complexity down to O(n^2) or better for practical input sizes.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^3) O(n) Check every subarray for distinct elements
Sliding Window O(n^2) O(n) Expand window and track element counts to count valid subarrays efficiently

Algorithm Walkthrough

  1. Compute the total number of distinct elements in the array, total_distinct.
  2. Initialize a variable count to track the number of complete subarrays.
  3. Iterate over the starting index i of the subarray from 0 to n-1.
  4. For each starting index, initialize a local hash map window_count and a variable distinct_in_window.
  5. Expand the subarray by iterating with ending index j from i to n-1:
  • Add nums[j] to the window_count.
  • If nums[j] is newly added (count was 0), increment distinct_in_window.
  • If distinct_in_window equals total_distinct, all subarrays starting at i and ending at j or later are complete. Increment count by 1.
  1. Continue until all starting indices have been processed.
  2. Return count.

Why it works: The sliding window ensures that every subarray is checked starting from each left boundary, and we only count subarrays that have exactly the total distinct elements. The hash map guarantees that duplicates are handled correctly without recounting the same element.

Python Solution

from typing import List
from collections import defaultdict

class Solution:
    def countCompleteSubarrays(self, nums: List[int]) -> int:
        total_distinct = len(set(nums))
        n = len(nums)
        count = 0

        for i in range(n):
            window_count = defaultdict(int)
            distinct_in_window = 0

            for j in range(i, n):
                if window_count[nums[j]] == 0:
                    distinct_in_window += 1
                window_count[nums[j]] += 1

                if distinct_in_window == total_distinct:
                    count += 1

        return count

This implementation uses a nested loop to traverse all possible starting and ending indices. The inner loop maintains a hash map of counts of elements in the current window. When the number of distinct elements equals the total distinct elements of the array, the subarray is complete, and count is incremented.

Go Solution

func countCompleteSubarrays(nums []int) int {
    totalDistinct := make(map[int]struct{})
    for _, num := range nums {
        totalDistinct[num] = struct{}{}
    }
    distinctCount := len(totalDistinct)

    n := len(nums)
    count := 0

    for i := 0; i < n; i++ {
        windowCount := make(map[int]int)
        distinctInWindow := 0

        for j := i; j < n; j++ {
            if windowCount[nums[j]] == 0 {
                distinctInWindow++
            }
            windowCount[nums[j]]++

            if distinctInWindow == distinctCount {
                count++
            }
        }
    }

    return count
}

In Go, we use a map[int]int to store the count of elements in the window and a map[int]struct{} to compute the total distinct elements. The logic is identical to the Python solution, with minor syntactic differences for map initialization.

Worked Examples

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

i j window distinct_in_window count
0 0 [1] 1 0
0 1 [1,3] 2 0
0 2 [1,3,1] 2 0
0 3 [1,3,1,2] 3 1
0 4 [1,3,1,2,2] 3 2
1 1 [3] 1 2
1 2 [3,1] 2 2
1 3 [3,1,2] 3 3
1 4 [3,1,2,2] 3 4
2 ... ... ... ...

Final answer: 4

Example 2: nums = [5,5,5,5]

Every subarray contains only 5. There are n*(n+1)/2 = 4*5/2 = 10 subarrays. Final answer: 10.

Complexity Analysis

Measure Complexity Explanation
Time O(n^2) We iterate over all subarray start and end indices. The inner hash map operations are O(1) per element.
Space O(n) We store counts of elements in the current window using a hash map. Maximum size is the number of distinct elements, at most n.

The O(n^2) time is acceptable given n ≤ 1000.

Test Cases

# Provided examples
assert Solution().countCompleteSubarrays([1,3,1,2,2]) == 4  # mixed duplicates
assert Solution().countCompleteSubarrays([5,5,5,5]) == 10    # all same element

# Additional test cases
assert Solution().countCompleteSubarrays([1]) == 1           # single element
assert Solution().countCompleteSubarrays([1,2,3,4]) == 1     # all unique elements
assert Solution().countCompleteSubarrays([1,2,1,2,1]) == 4  # repeated pattern
assert Solution().countCompleteSubarrays([1,1,2,2,3,3]) == 4 # multiple duplicates
Test Why
[1,3,1,2,2] Example with mixed duplicates
[5,5,5,5] All elements same, every subarray is complete
[1] Single-element array, simplest case
[1,2,3,4] All elements unique, only the full array is complete
[1,2,1,2,1] Repeating pattern, tests sliding window correctness
[1,1,2,2,3,3] Multiple duplicates, tests handling of distinct counts

Edge Cases

The first edge case is an array with all identical elements. This could cause a naive implementation to undercount because every subarray is technically complete. Our algorithm handles this correctly by checking distinct count matches, which is 1 in this case.

The second edge case is an array where every element is unique. Only the full array is complete, and subarrays shorter than the full array will not satisfy the distinct count condition. The algorithm ensures it counts only when the distinct elements equal total_distinct.

The third edge case is arrays with repeating patterns, such as [1,2,1,2,1]. A careless implementation might reset the window too early or miscount distinct elements when duplicates occur. Using a hash map to track counts prevents double counting and correctly handles these