Count the number of subarrays that contain every distinct value present in the whole array.
Problem
Given an integer array nums, a subarray is called complete if it contains all distinct values that appear anywhere in nums.
Return the number of complete subarrays.
A subarray is a contiguous non-empty segment of the array.
Notes
- The array may contain repeated values.
- A subarray is complete only if it includes every unique number present in the entire array at least once.
Input Format
- An integer array
nums.
Output Format
- Return an integer representing the number of complete subarrays.
Constraints
1 <= nums.lengthnumscontains integers.- The exact limits may vary by platform; the intended solution should be linear or near-linear in time.
Hints
- First determine how many distinct values exist in the entire array.
- Then use a sliding window to count subarrays that contain that many distinct values.
- When a window becomes complete, think about how many subarrays starting at the current left boundary can be formed.
Input Format
nums: an integer array
Find the number of contiguous subarrays that contain every distinct value appearing in nums.
Output Format
- Return the count of complete subarrays as an integer.
Constraints
- Subarrays are contiguous and non-empty.
- A complete subarray must contain every distinct value present in the whole array.
- Aim for an or approach.
Example 1
Input
nums = [1,3,1,2,2]
Output
4
Explanation
The distinct values in the whole array are {1, 2, 3}. The complete subarrays are [1,3,1,2], [1,3,1,2,2], [3,1,2], and [3,1,2,2].
Example 2
Input
nums = [5,5,5]
Output
6
Explanation
There is only one distinct value in the array, so every non-empty subarray is complete. The total number of subarrays is 3 + 2 + 1 = 6.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.