2856. Count Complete Subarrays In An Array¶

LeetCode Problem View on GitHub

2856. Count Complete Subarrays in an Array

Medium

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

Solution¶

class Solution {
    public int countCompleteSubarrays(int[] nums) {
        int n = nums.length;
        HashSet<Integer> req = new HashSet<>();
        for (int ele : nums) req.add(ele);
        int unique = req.size();
        int count = 0;
        for (int i = 0; i < n; i++) {
            HashSet<Integer> set = new HashSet<>();
            for (int j = i; j < n; j++) {
                int x = nums[j];
                set.add(x);
                if (set.size() == unique) count++;
            }
        }
        return count;
    }
}

Complexity Analysis¶

• Time Complexity: O(?)
• Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here