Efficiently Count Complete Subarrays

Count Complete Subarrays — Match Distinct Count in Subarrays

Problem Statement

You’re given an array of positive integers nums.

A complete subarray is defined as a subarray that contains all the distinct elements present in the entire array.

Your task is to count the number of complete subarrays in nums.

Explanation:

The total number of distinct elements in the array is 3: {1, 2, 3}.

Now, let’s find all subarrays that also contain all 3:

  • [1,3,1,2]

  • [1,3,1,2,2]

  • [3,1,2]

  • [3,1,2,2]

So, there are 4 complete subarrays.

Best Technique – Sliding Window + At-Most K Trick

This problem might seem like just a subarray count, but it tests your ability to:

  • Recognize a fixed-size condition inside variable-sized subarrays

  • Use a hash map or frequency counter for distinct element tracking

  • Leverage the at-most-k sliding window pattern

Let’s explore multiple ways to solve this—from brute force to optimal—and see what each one teaches us.

Different Approaches:

Approach 1: Brute Force with Set Tracking

Try every possible subarray, use a Set to count how many distinct elements it contains. If it matches the total count in the full array—count it.


public static int countCompleteSubarrays(int[] nums) {
    int totalDistinct = countDistinct(nums);
    int n = nums.length;
    int result = 0;

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

private static int countDistinct(int[] nums) {
    Set<Integer> set = new HashSet<>();
    for (int num : nums) set.add(num);
    return set.size();
}

Approach 2: HashMap for Frequency Counting (Improved Brute Force)

Use a HashMap to reduce redundancy and speed up lookups. You still check every subarray, but with frequency tracking, allowing for early cut-offs.

public static int countCompleteSubarraysHashMap(int[] nums) {
    int totalDistinct = countDistinct(nums);
    int result = 0;

    for (int i = 0; i < nums.length; i++) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int j = i; j < nums.length; j++) {
            freq.put(nums[j], freq.getOrDefault(nums[j], 0) + 1);
            if (freq.size() == totalDistinct) {
                result++;
            }
        }
    }

    return result;
}

Approach 3: Optimized using At-Most-K Sliding Window

exactlyK = atMost(K) - atMost(K - 1)

We count subarrays with exactly the required number of distinct elements.

public static int countCompleteSubarraysOptimized(int[] nums) {
    int totalDistinct = countDistinct(nums);
    return atMost(nums, totalDistinct) - atMost(nums, totalDistinct - 1);
}

private static int atMost(int[] nums, int k) {
    Map<Integer, Integer> freq = new HashMap<>();
    int left = 0, result = 0;

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

        while (freq.size() > k) {
            freq.put(nums[left], freq.get(nums[left]) - 1);
            if (freq.get(nums[left]) == 0) freq.remove(nums[left]);
            left++;
        }

        result += right - left + 1;
    }

    return result;
}

⚠️ Common Pitfalls

  • Not using a sliding window properly when calculating atMost(k)

  • Forgetting to count from index i to j in subarrays

  • Trying to use Set to count exact matches without optimizing

  • Not recognizing that subtracting atMost(k-1) from atMost(k) gives exact count

📊 Time and Space Complexity

ApproachTime Complexity      Space Complexity
Brute Force      O(n²)           O(n)
HashMap Traversal      O(n²)           O(n)
Optimized Sliding Window      O(n)           O(n)

🌍 Real-World Applications

  • Analyzing user activity in web applications (e.g., checking if all types of actions are performed in a time window)

  • Data completeness in scientific computing (ensuring that all conditions or data points are included in a dataset)

  • Classification tasks where every distinct element needs to be accounted for.


I hope you found this article insightful! Keep exploring, keep learning, and don’t forget to check back daily for more exciting problem breakdowns. If you know someone who would benefit from this, share it with them and help them grow too! That’s it for today—see you in the next post!

                                                                                                                                         Signing off!! 

                                                                                                Master DSA One Problem at a Time :)

Comments

Post a Comment

Popular posts from this blog

Trailing Zeros in Factorial – How Many and Why?

Trailing Zeros – Counting Zeros in Factorial Factorial-related problems are a fundamental part of Data Structures and Algorithms (DSA). One such classic problem involves counting the number of trailing zeros in N! . In this article, we will explore different approaches to solving this problem, optimize our solution, and examine its real-world applications. Optimal Data Structure for Solving the Problem For this problem, no additional data structures are required. Since factorials grow exponentially, storing the actual factorial value is impractical. Instead, we leverage mathematical properties and division operations to efficiently determine the number of trailing zeros. This approach ensures an optimal solution in terms of both time and space complexity. Approach – From Brute Force to an Optimized Solution Brute Force Approach – Compute and Count A naive approach involves computing the factorial of N and counting the number of trailing zeros. However, this method is highly ineff...
Read more

Divisible Drama — Who’s In, Who’s Out?

 Divisible Drama — Who’s In, Who’s Out? Problem Statement You’re given two positive integers n and m . num1 = sum of all numbers from 1 to n not divisible by m num2 = sum of all numbers from 1 to n divisible by m Your mission, should you choose to accept it: Return num1 - num2 Example Input: n = 10 , m = 3 Output: 19 Breakdown: Not divisible by 3 → [ 1 , 2 , 4 , 5 , 7 , 8 , 10 ] → num1 = 37 Divisible by 3 → [ 3 , 6 , 9 ] → num2 = 18 Answer = 37 - 18 = 19 Best Data Structure for Solving the Problem This one’s a math.  Why overthink it when Gauss already gave us the formula for sum of 1 to n? Different Approaches (from Brute Force to Optimized) Approach 1: Brute Force (aka List & Sum Vibes) Loop from 1 to n , split the nums based on whether they’re divisible by m , and sum them up. class Solution { public int differenceOfSums ( int n, int m) { int num1 = 0 , num2 = 0 ; for ( int i = 1 ; i <= n; i++)...
Read more

Zero Array After Queries

Zero Array After Queries You are given an integer array nums and a list of queries, where each query is a pair [li, ri] representing a range. Each query allows you to decrement any subset of elements in the range [li, ri] by 1. Your task is to determine if it is possible to make every element in nums equal to zero after applying all queries in order . Example Input: nums = [ 1 , 0 , 1 ] queries = [[0, 2]] Output: true Explanation: We can select indices 0 and 2 and decrement both by 1 to obtain [0, 0, 0] . Best Data Structure for the Job We are working with multiple range updates and need to evaluate coverage over indices. The best choice here is the difference array combined with a prefix sum . It allows efficient range additions and helps track how many times each index is affected by the queries. Different Approaches Approach 1: Brute Force This naive method iterates over every index for every query and performs the decrement operations directly. class Solution {...
Read more