LeetCode 2799: Count Complete Subarrays in an Array

The problem "Count Complete Subarrays in an Array" (LeetCode 2799) requires us to count how many subarrays contain all distinct elements present in the original array. A subarray is a contiguous part of the array.

Problem Statement

Given an array of positive integers nums, return the number of complete subarrays. A subarray is complete if it contains all the distinct elements present in the entire array.

Constraints

• 1 ≤ nums.length ≤ 100
• 1 ≤ nums[i] ≤ 2000

Problem Link

View on LeetCode ↗

Example 1

Input: nums = [1, 3, 1, 2, 2]
Output: 4
Explanation: 
The distinct elements in the whole array are {1, 2, 3}.
The complete subarrays are:
[1, 3, 1, 2]
[1, 3, 1, 2, 2]
[3, 1, 2]
[3, 1, 2, 2]

Approach 1: Brute Force (Check All Subarrays)

The brute force approach checks every possible subarray to see if it contains all distinct elements from the original array.

Algorithm Steps

1. Count the distinct elements in the entire array
2. Initialize a counter for complete subarrays
3. Iterate through all possible starting indices
4. For each starting index, iterate through all possible ending indices
5. For each subarray, count the distinct elements
6. If the count matches the total distinct elements, increment our counter
7. Return the total count

Complexity Analysis

Implementation

class Solution {
public:
    int countCompleteSubarrays(vector<int>& nums) {
        int count = 0;
        unordered_map<int, int> mp;
        for (int num : nums) {
            mp[num]++;
        }
        int totalDistinct = mp.size();

        for (int i = 0; i < nums.size(); i++) {
            unordered_map<int, int> temp;
            for (int j = i; j < nums.size(); j++) {
                temp[nums[j]]++;
                if (temp.size() == totalDistinct)
                    count++;
            }
        }
        return count;
    }
};
                

class Solution {
    public int countCompleteSubarrays(int[] nums) {
        int count = 0;
        Set<Integer> distinct = new HashSet<>();
        for (int num : nums) {
            distinct.add(num);
        }
        int totalDistinct = distinct.size();

        for (int i = 0; i < nums.length; i++) {
            Set<Integer> current = new HashSet<>();
            for (int j = i; j < nums.length; j++) {
                current.add(nums[j]);
                if (current.size() == totalDistinct) {
                    count++;
                }
            }
        }
        return count;
    }
}
                

class Solution:
    def countCompleteSubarrays(self, nums: List[int]) -> int:
        count = 0
        total_distinct = len(set(nums))
        
        for i in range(len(nums)):
            current = set()
            for j in range(i, len(nums)):
                current.add(nums[j])
                if len(current) == total_distinct:
                    count += 1
                    
        return count
                

Approach 2: Sliding Window (Optimized)

The sliding window approach efficiently counts complete subarrays by maintaining a window that contains all distinct elements and calculating valid subarrays from that window.

Algorithm Steps

1. Count the distinct elements in the entire array
2. Initialize two pointers (left and right) to represent the window
3. Use a hash map to track elements in the current window
4. Expand the window by moving the right pointer
5. When the window contains all distinct elements:
   • All subarrays ending at right pointer from current left are valid
   • Add these to the count
   • Move left pointer to try smaller windows
6. Continue until all elements are processed

Complexity Analysis

Implementation

class Solution {
public:
    int countCompleteSubarrays(vector<int>& nums) {
        int n = nums.size();
        unordered_set<int> distinct(nums.begin(), nums.end());
        int totalDistinct = distinct.size();

        unordered_map<int, int> window;
        int left = 0, count = 0;

        for (int right = 0; right < n; right++) {
            window[nums[right]]++;

            while (window.size() == totalDistinct) {
                count += n - right;
                window[nums[left]]--;
                if (window[nums[left]] == 0) {
                    window.erase(nums[left]);
                }
                left++;
            }
        }

        return count;
    }
};
                

class Solution {
    public int countCompleteSubarrays(int[] nums) {
        int n = nums.length;
        Set<Integer> distinct = new HashSet<>();
        for (int num : nums) distinct.add(num);
        int totalDistinct = distinct.size();

        Map<Integer, Integer> window = new HashMap<>();
        int left = 0, count = 0;

        for (int right = 0; right < n; right++) {
            window.put(nums[right], window.getOrDefault(nums[right], 0) + 1);

            while (window.size() == totalDistinct) {
                count += n - right;
                window.put(nums[left], window.get(nums[left]) - 1);
                if (window.get(nums[left]) == 0) {
                    window.remove(nums[left]);
                }
                left++;
            }
        }

        return count;
    }
}
                

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

        for right in range(n):
            window[nums[right]] = window.get(nums[right], 0) + 1

            while len(window) == total_distinct:
                count += n - right
                window[nums[left]] -= 1
                if window[nums[left]] == 0:
                    del window[nums[left]]
                left += 1

        return count
                

Real-Life Analogy

Imagine you're collecting Pokémon cards. Your goal is to find all sets of continuous cards (subarrays) that include all types of Pokémon you have.

• Brute Force: You check every possible pack manually to see if it has all Pokémon types.
• Sliding Window: You keep adding cards to your hand until you have all Pokémon, then slide your hand forward to explore smaller possible complete sets.

Comparison of Approaches

Frequently Asked Questions