Count Complete Subarrays in an Array — Problem & Solution
Count Complete Subarrays in an Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Count Complete Subarrays in an Array is a medium coding problem on arrays, hash table and sliding window, asked in Amazon, Microsoft and Freshworks interviews.
- Difficulty: Medium
- Topics: Arrays, Hash Table, Sliding Window
- Asked at: Amazon, Microsoft, Freshworks
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A subarray is complete when the number of distinct values in it equals the number of distinct values in the whole array.
Return the number of complete subarrays of nums.
Example 1
Input: nums = [1,3,1,2,2]
Output: 4
Explanation: The whole array has 3 distinct values; four subarrays match it.
Example 2
Input: nums = [5,5,5,5]
Output: 10
Explanation: One distinct value, so every subarray is complete.
Example 3
Input: nums = [1,2]
Output: 1
Constraints
1 <= nums.length <= 10001 <= nums[i] <= 2000
Hints for Count Complete Subarrays in an Array
Hint 1
First find how many distinct values the whole array has — that is the target.
Hint 2
Once a window reaches the target, extending it to the right keeps it complete.
Hint 3
So for each minimal complete window starting at
l, alln - rextensions count.
How to solve Count Complete Subarrays in an Array
For each left edge, find the shortest complete window; every longer window with the same left edge is also complete. Sliding both edges collects all of them in one pass.
Approach
- Count the distinct values of the whole array as
all. - Grow the window on the right, keeping a tally and a distinct count.
- While the window is complete, add
n - r(every right extension), then drop the left element and advancel.
Why it works
Adding elements can only raise the distinct count, and it can never exceed all, so once a window hits all every extension does too — hence the n - r. Shrinking from the left inside that loop enumerates each left edge exactly once with its minimal complete window.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- Adding
n - routside the shrink loop counts only one left edge per right edge. - The distinct count of the window is compared with the whole array's, not with a fixed
k. - An array of one repeated value makes every subarray complete —
n(n+1)/2of them.
Reference solution
Python
from typing import List
def countCompleteSubarrays(nums: List[int]) -> int:
n = len(nums)
all_distinct = len(set(nums))
cnt = {}
l = 0
distinct = 0
res = 0
for r in range(n):
v = nums[r]
cnt[v] = cnt.get(v, 0) + 1
if cnt[v] == 1:
distinct += 1
while distinct == all_distinct:
res += n - r
cnt[nums[l]] -= 1
if cnt[nums[l]] == 0:
distinct -= 1
l += 1
return resJava
public static int countCompleteSubarrays(int[] nums) {
int n = nums.length;
Set<Integer> distinctAll = new HashSet<>();
for (int x : nums) distinctAll.add(x);
int all = distinctAll.size();
Map<Integer, Integer> cnt = new HashMap<>();
int l = 0, distinct = 0, res = 0;
for (int r = 0; r < n; r++) {
int v = nums[r];
int have = cnt.getOrDefault(v, 0) + 1;
cnt.put(v, have);
if (have == 1) distinct++;
while (distinct == all) {
res += n - r;
int u = nums[l];
int left = cnt.get(u) - 1;
cnt.put(u, left);
if (left == 0) distinct--;
l++;
}
}
return res;
}C++
int countCompleteSubarrays(vector<int>& nums) {
int n = (int) nums.size();
unordered_set<int> distinctAll(nums.begin(), nums.end());
int all = (int) distinctAll.size();
unordered_map<int, int> cnt;
int l = 0, distinct = 0, res = 0;
for (int r = 0; r < n; r++) {
if (++cnt[nums[r]] == 1) distinct++;
while (distinct == all) {
res += n - r;
if (--cnt[nums[l]] == 0) distinct--;
l++;
}
}
return res;
}JavaScript
var countCompleteSubarrays = function(nums) {
var n = nums.length;
var seen = {}, all = 0, i;
for (i = 0; i < n; i++) {
if (!seen[nums[i]]) { seen[nums[i]] = true; all++; }
}
var cnt = {};
var l = 0, distinct = 0, res = 0;
for (var r = 0; r < n; r++) {
var v = nums[r];
cnt[v] = (cnt[v] || 0) + 1;
if (cnt[v] === 1) distinct++;
while (distinct === all) {
res += n - r;
cnt[nums[l]]--;
if (cnt[nums[l]] === 0) distinct--;
l++;
}
}
return res;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets