Watch 6 video solutions for Find the Median of the Uniqueness Array, a hard level problem involving Array, Hash Table, Binary Search. This walkthrough by Programming Live with Larry has 743 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an integer array nums. The uniqueness array of nums is the sorted array that contains the number of distinct elements of all the subarrays of nums. In other words, it is a sorted array consisting of distinct(nums[i..j]), for all 0 <= i <= j < nums.length.
Here, distinct(nums[i..j]) denotes the number of distinct elements in the subarray that starts at index i and ends at index j.
Return the median of the uniqueness array of nums.
Note that the median of an array is defined as the middle element of the array when it is sorted in non-decreasing order. If there are two choices for a median, the smaller of the two values is taken.
Example 1:
Input: nums = [1,2,3]
Output: 1
Explanation:
The uniqueness array of nums is [distinct(nums[0..0]), distinct(nums[1..1]), distinct(nums[2..2]), distinct(nums[0..1]), distinct(nums[1..2]), distinct(nums[0..2])] which is equal to [1, 1, 1, 2, 2, 3]. The uniqueness array has a median of 1. Therefore, the answer is 1.
Example 2:
Input: nums = [3,4,3,4,5]
Output: 2
Explanation:
The uniqueness array of nums is [1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3]. The uniqueness array has a median of 2. Therefore, the answer is 2.
Example 3:
Input: nums = [4,3,5,4]
Output: 2
Explanation:
The uniqueness array of nums is [1, 1, 1, 1, 2, 2, 2, 3, 3, 3]. The uniqueness array has a median of 2. Therefore, the answer is 2.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 105Problem Overview: You are given an integer array and must compute the uniqueness value (number of distinct elements) for every subarray. The task is to find the median among all those uniqueness values. Since an array of length n has n*(n+1)/2 subarrays, directly computing and sorting every uniqueness value quickly becomes too slow.
Approach 1: Brute Force with Hash Set (O(n²) time, O(n) space)
Iterate over every possible starting index and expand the subarray to the right. Maintain a hash set to track distinct elements in the current subarray. Each expansion updates the uniqueness count, which you store in a list. After generating all n*(n+1)/2 values, sort the list and return the middle element. This approach clearly models the problem but quickly becomes impractical because generating and sorting all uniqueness values costs O(n²) memory and up to O(n² log n) time.
Approach 2: Binary Search + Sliding Window (O(n log n) time, O(n) space)
The key insight: instead of explicitly generating all uniqueness values, you can binary search the median. Suppose you guess a value k. You only need to check how many subarrays have uniqueness ≤ k. If that count is at least the median position, the answer is ≤ k; otherwise it must be larger.
Counting subarrays with at most k distinct elements can be done in linear time using a sliding window. Move the right pointer while tracking frequencies in a hash table. If distinct elements exceed k, move the left pointer until the window becomes valid again. For every right pointer position, add the window length to the total count. This gives the number of valid subarrays in O(n) time.
Combine this counting routine with binary search over the possible uniqueness range [1, distinct(nums)]. Each step checks whether at least half of all subarrays have uniqueness ≤ k. The search converges to the smallest k that satisfies the median condition.
Recommended for interviews: The binary search + sliding window approach is what interviewers expect. Brute force demonstrates understanding of the uniqueness definition, but recognizing that the median can be found through counting and monotonic binary search shows strong algorithmic intuition and mastery of sliding window patterns.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force with Hash Set | O(n² log n) | O(n²) | Understanding the problem or when n is very small |
| Binary Search + Sliding Window | O(n log n) | O(n) | General optimal solution for large arrays |