Course4all
Join us on telegram
Home/dsa/Sliding Window/Count Complete Subarrays in an Array

Count Complete Subarrays in an Array

Master this topic with zero to advance depth.

Count Complete Subarrays in an Array

A subarray is complete if the number of distinct elements in it is equal to the number of distinct elements in the entire array.

Visual Representation

nums = [1, 3, 1, 2, 2], Total Distinct: 3 [1, 3, 1, 2] (Distinct: 3, VALID!) [3, 1, 2] (Distinct: 3, VALID!) [1, 2, 2] (Distinct: 2, INVALID)
Medium

Examples

Input: nums = [1,3,1,2,2]
Output: 4
Approach 1

Level I: Brute Force

Intuition

Find the total number of distinct elements in the array first. Then, check every subarray and count how many are complete.

⏱ O(N^2)💾 O(N)
java
public class Solution {
    public int countCompleteSubarrays(int[] nums) {
        Set<Integer> total = new HashSet<>();
        for (int x : nums) total.add(x);
        int k = total.size(), res = 0;
        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() == k) res++;
            }
        }
        return res;
    }
}
Approach 2

Level III: Optimal (Sliding Window)

Intuition

Thought Process

This is equivalent to finding subarrays with at least k distinct elements. We can use the 'at least' pattern or the 'total - (at most k-1)' pattern.

Calculation

Total Subarrays - Subarrays with at most (K-1) distinct elements.

⏱ O(N)💾 O(N)
java
public class Solution {
    public int countCompleteSubarrays(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int x : nums) set.add(x);
        int k = set.size();
        return atMost(nums, k) - atMost(nums, k - 1);
    }
    
    private int atMost(int[] nums, int k) {
        if (k == 0) return 0;
        Map<Integer, Integer> counts = new HashMap<>();
        int left = 0, res = 0;
        for (int right = 0; right < nums.length; right++) {
            counts.put(nums[right], counts.getOrDefault(nums[right], 0) + 1);
            while (counts.size() > k) {
                int out = nums[left++];
                counts.put(out, counts.get(out) - 1);
                if (counts.get(out) == 0) counts.remove(out);
            }
            res += right - left + 1;
        }
        return res;
    }
}
← Previous QuestionLongest Substring with At Most K Distinct Characters
Next Question →Linked List Cycle