Are you looking for a step-by-step explanation of Leetcode's "2799. Count Complete Subarrays in an Array"? You’re at the right place! In this blog, we’ll go from a basic brute force solution to a highly efficient sliding window approach, and explain each concept in a simple way.
Problem Statement (Leetcode 2799)
You are given an array of positive integers. A subarray is a contiguous part of the array (meaning elements must be next to each other).
We define a "complete" subarray as one that contains all distinct elements that are present in the entire array.
Example 1:
Input: nums = [1, 3, 1, 2, 2]
Output: 4
Explanation:
The distinct elements in the whole array are {1, 2, 3}.
The subarrays that contain all of them are:
-
[1, 3, 1, 2]
-
[1, 3, 1, 2, 2]
-
[3, 1, 2]
-
[3, 1, 2, 2]
Total = 4 complete subarrays ✅
What is the goal of this problem ?
Count how many subarrays of the given array are complete, i.e., contain all distinct elements from the original array.
Approach 1: Brute Force (Try All Subarrays)
Let’s start with the most basic idea. What if we try every possible subarray and check if it contains all the distinct elements?
👨🏫 Steps:
-
Count the number of distinct elements in the full array.
-
Try all subarrays using two loops.
-
For each subarray, use a map to count its unique elements.
-
If the number of unique elements equals the total, it's a complete subarray.
🧾 C++ Code:
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;
}
};
⏱ Time Complexity: O(n^2)
Why? - Because for each index i, we're iterating from i to n.
📦 Space Complexity: O(n)
Because we store elements in a temporary map.
⚡ Drawback of Brute Force:
This solution works fine for small arrays, but it becomes slow when the input size increases, as it's doing too much work. Can we do better?
🚀 Approach 2: Sliding Window (Optimized)
Now let’s talk about the Sliding Window Technique, a powerful method that avoids repeating work.
- Instead of checking all subarrays, we’ll use a window that moves through the array and tracks how many distinct elements are inside.
- When our window has all the required distinct elements, every subarray starting from that point to the end of the window is valid.
👨🏫 Steps:
- Use a set to count the total number of unique elements.
- Use two pointers i and j to mark the sliding window.
- Use a map to track how many times each number appears in the current window.
- When the current window has all distinct elements:
- Every subarray from i to j is valid → add (n - j) to answer.
- Then move i forward to try smaller windows.
🧾 C++ Code:
class Solution
{
public:
int countCompleteSubarrays(vector<int> &nums)
{
int n = nums.size();
set<int> st(nums.begin(), nums.end());
int totalDistinct = st.size();
unordered_map<int, int> mp;
int i = 0, j = 0, count = 0;
while (j < n)
{
mp[nums[j]]++;
while (mp.size() == totalDistinct)
{
count += (n - j);
mp[nums[i]]--;
if (mp[nums[i]] == 0)
mp.erase(nums[i]);
i++;
}
j++;
}
return count;
}
};
⏱ Time Complexity: O(n)
Efficient because we process each element at most twice.
📦 Space Complexity: O(n)
We use a map to store frequency of elements in the current window.
🧒 Easy 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.
This Leetcode problem is a perfect example of how you can go from a naive solution to an optimized one using sliding window.
- Always understand the problem deeply before optimizing.
- Learn to spot patterns like “number of distinct elements” → good candidate for sliding window.
- Practice both approaches for stronger coding interviews!
Keywords :
Count complete subarrays Leetcode
Leetcode 2799 solution explained
Sliding window vs brute force
C++ complete subarrays count
Easy explanation for subarrays
Leetcode for beginners
How to solve array problems efficiently
