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.
This approach involves dividing the problem into smaller subproblems, solving each subproblem independently, and combining the results. This is useful for problems that can be broken down recursively.
This C code represents a typical divide and conquer structure, recursively dividing the problem into two halves until a base condition is met, and then combining the solution. This is a generic template and can be adapted for specific problems like merge sort.
Time Complexity: O(n log n)
Space Complexity: O(log n) due to recursive stack space.
This approach uses an explicit stack to replace the function call stack, providing an iterative solution to problems that are typically solved recursively. It's beneficial in avoiding stack overflow and managing deeper recursion paths.
This C code demonstrates replacing the recursive stack with an explicit stack. We simulate function calls and solve subproblems iteratively, preventing stack overflow on large inputs.
Time Complexity: O(n log n)
Space Complexity: O(n) for stack usage.
Let the length of the array nums be n. The length of the uniqueness array is m = \frac{(1 + n) times n}{2}, and the median of the uniqueness array is the \frac{m + 1}{2}-th smallest number among these m numbers.
Consider how many numbers in the uniqueness array are less than or equal to x. As x increases, there will be more and more numbers less than or equal to x. This property is monotonic, so we can use binary search to enumerate x and find the first x such that the number of elements in the uniqueness array less than or equal to x is greater than or equal to \frac{m + 1}{2}. This x is the median of the uniqueness array.
We define the left boundary of the binary search as l = 0 and the right boundary as r = n. Then we perform binary search. For each mid, we check whether the number of elements in the uniqueness array less than or equal to mid is greater than or equal to \frac{m + 1}{2}. We achieve this through the function check(mx).
The implementation idea of the function check(mx) is as follows:
Since the longer the subarray, the more different elements it contains, we can use two pointers to maintain a sliding window such that the number of different elements in the window does not exceed mx. Specifically, we maintain a hash table cnt, where cnt[x] represents the number of occurrences of element x in the window. We use two pointers l and r, where l represents the left boundary of the window and r represents the right boundary. Initially, l = r = 0.
We enumerate r. For each r, we add nums[r] to the window and update cnt[nums[r]]. If the number of different elements in the window exceeds mx, we need to move l to the right until the number of different elements in the window does not exceed mx. At this point, the subarrays with the right endpoint r and left endpoints in the range [l, .., r] all meet the condition, and there are r - l + 1 such subarrays. We accumulate this count into k. If k is greater than or equal to \frac{m + 1}{2}, it means that the number of elements in the uniqueness array less than or equal to mid is greater than or equal to \frac{m + 1}{2}, and we return true; otherwise, we return false.
The time complexity is O(n times log n), and the space complexity is O(n). Here, n is the length of the array nums.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Divide and Conquer | Time Complexity: O(n log n) |
| Iterative Solution With Stack | Time Complexity: O(n log n) |
| Binary Search + Two Pointers | — |
| 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 |
3134. Find the Median of the Uniqueness Array (Leetcode Hard) • Programming Live with Larry • 743 views views
Watch 5 more video solutions →Practice Find the Median of the Uniqueness Array with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor