# Count Complete Subarrays in an Array
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/count-complete-subarrays-in-an-array)
Canonical: https://scaleengineer.com/dsa/problems/count-complete-subarrays-in-an-array
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window)
**Data structures:** Array, Hash Table
---
## Problem
You are given an array `nums` consisting of **positive** integers.

We call a subarray of an array **complete** if the following condition is satisfied:

* The number of **distinct** elements in the subarray is equal to the number of distinct elements in the whole array.

Return _the number of **complete** subarrays_.

A **subarray** is a contiguous non-empty part of an array.

**Example 1:**

**Input:** nums = [1,3,1,2,2]
**Output:** 4
**Explanation:** The complete subarrays are the following: [1,3,1,2], [1,3,1,2,2], [3,1,2] and [3,1,2,2].

**Example 2:**

**Input:** nums = [5,5,5,5]
**Output:** 10
**Explanation:** The array consists only of the integer 5, so any subarray is complete. The number of subarrays that we can choose is 10.

**Constraints:**

* `1 <= nums.length <= 1000`
* `1 <= nums[i] <= 2000`

# Approaches
## Brute Force with Triple Loop
The most straightforward approach is to generate every possible subarray and, for each one, check if it is 'complete'. A subarray is complete if its number of distinct elements equals the number of distinct elements in the entire original array.
**Time:** O(N^3), where N is the length of the array. The two outer loops iterate through all O(N^2) subarrays. For each subarray of length L, we iterate through it to count distinct elements, which takes O(L) time. In the worst case, L is O(N), leading to an overall complexity of O(N^3). · **Space:** O(N), where N is the length of the array. In the worst case, a subarray can contain N distinct elements, requiring a `HashSet` of size N. The set for the total distinct count also takes up to O(N) space.
**Pros:** Simple to understand and implement.
**Cons:** Highly inefficient due to the triple nested loop.; Will likely result in a 'Time Limit Exceeded' error for larger inputs.
### Explanation
First, we need to determine the target number of distinct elements. We can do this by iterating through the entire `nums` array once and storing the elements in a `HashSet`. The size of this set is our target count, let's call it `k`.

Then, we use two nested loops to define the start (`i`) and end (`j`) indices of all possible subarrays. For each subarray `nums[i...j]`, we use a third loop to iterate through its elements, count the number of distinct elements using another temporary `HashSet`, and check if this count equals `k`. If it does, we increment our result counter.

```java
import java.util.HashSet;
import java.util.Set;

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

        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                // Subarray is nums[i...j]
                Set<Integer> subArrayDistinctSet = new HashSet<>();
                for (int l = i; l <= j; l++) {
                    subArrayDistinctSet.add(nums[l]);
                }
                if (subArrayDistinctSet.size() == k) {
                    count++;
                }
            }
        }
        return count;
    }
}
```
### Algorithm
*   1. Create a `HashSet` from the entire `nums` array to find the total number of distinct elements, `k`.
*   2. Initialize a counter `count` to 0.
*   3. Use a nested loop with index `i` from 0 to `n-1` to mark the start of a subarray.
*   4. Use another nested loop with index `j` from `i` to `n-1` to mark the end of a subarray.
*   5. For each subarray `nums[i...j]`, create a temporary `HashSet`.
*   6. Iterate from `i` to `j` and add elements of the subarray to the temporary set.
*   7. If the size of the temporary set equals `k`, increment `count`.
*   8. After all loops complete, return `count`.

## Optimized Brute Force with Double Loop
We can optimize the brute-force approach by avoiding the redundant work of recounting distinct elements for each subarray from scratch. For a fixed starting point `i`, as we extend the subarray by moving the endpoint `j`, we can maintain a running count of distinct elements.
**Time:** O(N^2), where N is the length of the array. We have two nested loops. The outer loop runs N times, and the inner loop runs up to N times. The `HashSet` insertion is an O(1) operation on average. · **Space:** O(N), where N is the length of the array. The `currentDistinctSet` can store up to N elements in the worst case.
**Pros:** More efficient than the O(N^3) approach.; Still relatively easy to reason about.
**Cons:** Not the most optimal solution.; Can be slow for very large N, though it should pass the given constraints (N <= 1000).
### Explanation
Similar to the first approach, we begin by finding the total number of distinct elements, `k`.

We then iterate through all possible starting positions `i` of a subarray. For each `i`, we initialize a new `HashSet` to keep track of the distinct elements in the subarray starting at `i`. We then use a second loop to iterate from `j = i` to the end of the array. In this inner loop, we add `nums[j]` to our set and check if the set's size has reached `k`. If it has, we've found a complete subarray. A key insight here is that if `nums[i...j]` is complete, then any subarray `nums[i...p]` where `p > j` will also be complete. This is because it will contain all the distinct elements from `nums[i...j]`. So, once we find the first complete subarray starting at `i` (ending at `j`), we can add the remaining number of subarrays (`n - j`) to our count and break the inner loop.

```java
import java.util.HashSet;
import java.util.Set;

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

        for (int i = 0; i < n; i++) {
            Set<Integer> currentDistinctSet = new HashSet<>();
            for (int j = i; j < n; j++) {
                currentDistinctSet.add(nums[j]);
                if (currentDistinctSet.size() == k) {
                    // If nums[i...j] is complete, so is nums[i...j+1], nums[i...j+2], etc.
                    // There are (n - 1) - j + 1 = n - j such subarrays.
                    count += (n - j);
                    break; // Move to the next starting point i
                }
            }
        }
        return count;
    }
}
```
*Note: A simpler O(N^2) implementation without the `break` is also possible, where you just increment the count for every complete subarray found. The version with the `break` is a more optimized O(N^2) solution.*
### Algorithm
*   1. Calculate the total number of distinct elements, `k`, in `nums`.
*   2. Initialize a counter `count` to 0.
*   3. Loop with index `i` from 0 to `n-1` for the start of the subarray.
*   4. Inside this loop, create a new `HashSet` called `currentDistinctSet`.
*   5. Loop with index `j` from `i` to `n-1` for the end of the subarray.
*   6. Add `nums[j]` to `currentDistinctSet`.
*   7. If `currentDistinctSet.size()` equals `k`, it means `nums[i...j]` is a complete subarray, so increment `count`.
*   8. Return `count` after the loops finish.

## Sliding Window Approach
The most efficient solution uses the sliding window technique. The key observation is that if a subarray `nums[i...j]` is complete, then any larger subarray that contains it (e.g., `nums[i...j+1]`) is also complete. This monotonic property allows us to efficiently count subarrays without re-computation.
**Time:** O(N), where N is the length of the array. Both the `right` and `left` pointers traverse the array at most once. `HashMap` operations take O(1) time on average, so the overall time complexity is linear. · **Space:** O(D), where D is the number of distinct elements in the array. The `HashMap` and the initial `HashSet` will store at most D unique elements. In the worst case, D can be N, so the space complexity is O(N).
**Pros:** Optimal time complexity.; Efficiently processes the array in a single pass.
**Cons:** The logic can be slightly more complex to understand compared to brute-force methods.
### Explanation
We first calculate the required number of distinct elements, `k`. We then use two pointers, `left` and `right`, to define a 'window' on the array. We expand the window by moving `right` and shrink it by moving `left`.

We iterate `right` from the beginning to the end of the array, adding elements to our window and tracking their frequencies in a `HashMap`. When the number of distinct elements in our window (i.e., `map.size()`) equals `k`, we have found a complete subarray `nums[left...right]`.

At this point, we know that `nums[left...right]` is complete. Crucially, any subarray that starts at `left` and ends at an index greater than or equal to `right` will also be complete. There are `n - right` such subarrays. We add this number to our total count.

After counting, we need to find the next valid starting position. We shrink the window from the left by incrementing `left` and updating the frequency map. We continue shrinking as long as the window remains complete, adding `n - right` to the count at each step. This process continues until the `right` pointer has traversed the entire array.

```java
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

class Solution {
    public int countCompleteSubarrays(int[] nums) {
        Set<Integer> totalDistinctSet = new HashSet<>();
        for (int num : nums) {
            totalDistinctSet.add(num);
        }
        int k = totalDistinctSet.size();
        int n = nums.length;
        int count = 0;
        int left = 0;
        Map<Integer, Integer> windowCounts = new HashMap<>();

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

            // While the window is "complete"
            while (windowCounts.size() == k) {
                // The subarray nums[left...right] is complete.
                // Any subarray starting at `left` and ending at `right` or later is also complete.
                // There are (n - 1) - right + 1 = n - right such subarrays.
                count += (n - right);

                // Shrink the window from the left
                windowCounts.put(nums[left], windowCounts.get(nums[left]) - 1);
                if (windowCounts.get(nums[left]) == 0) {
                    windowCounts.remove(nums[left]);
                }
                left++;
            }
        }
        return count;
    }
}
```
### Algorithm
*   1. Calculate the total number of distinct elements, `k`, in `nums`.
*   2. Initialize `count = 0`, a `left` pointer to 0, and a `HashMap` `windowCounts` to store element frequencies in the current window.
*   3. Iterate with a `right` pointer from 0 to `n-1` to expand the window.
*   4. For each `nums[right]`, increment its count in `windowCounts`.
*   5. Start a `while` loop that continues as long as the window is complete (i.e., `windowCounts.size() == k`).
*   6. Inside the `while` loop, we have found a complete subarray `nums[left...right]`. Any subarray starting at `left` and ending at or after `right` is also complete. Add `n - right` to `count`.
*   7. Shrink the window: Decrement the count of `nums[left]` in the map. If its count becomes 0, remove it. Increment `left`.
*   8. After the outer loop finishes, return `count`.

# Solutions
### Python

```python
class Solution:
    def countCompleteSubarrays(self, nums: List[int]) -> int: cnt = len(set(nums)) ans, n = 0, len(nums) for i in range(n): s = set() for x in nums[i:]: s . add(x) if len(s) == cnt: ans += 1 return ans

```

### Java

```java
class Solution { public int countCompleteSubarrays ( int [] nums ) { Set < Integer > s = new HashSet <>(); for ( int x : nums ) { s . add ( x ); } int cnt = s . size (); int ans = 0 , n = nums . length ; for ( int i = 0 ; i < n ; ++ i ) { s . clear (); for ( int j = i ; j < n ; ++ j ) { s . add ( nums [ j ]); if ( s . size () == cnt ) { ++ ans ; } } } return ans ; } }
```

### CPP

```cpp
class Solution {
public:
  int countCompleteSubarrays(vector<int> &nums) {
    unordered_set<int> s(nums.begin(), nums.end());
    int cnt = s.size();
    int ans = 0, n = nums.size();
    for (int i = 0; i < n; ++i) {
      s.clear();
      for (int j = i; j < n; ++j) {
        s.insert(nums[j]);
        if (s.size() == cnt) {
          ++ans;
        }
      }
    }
    return ans;
  }
};

```