Find the Median of the Uniqueness Array
HardPrompt
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] <= 105
Approaches
3 approaches with complexity analysis and trade-offs.
This approach directly follows the problem definition. It involves generating every possible subarray, calculating the number of distinct elements for each one by iterating through it, collecting these counts into a list, sorting the list, and finally finding the median. This is the most straightforward but also the most inefficient method.
Algorithm
- Initialize an empty list,
uniqueness_array. - Use a nested loop to iterate through all possible start (
i) and end (j) indices of subarrays, where0 <= i <= j < n. - For each subarray
nums[i..j], create a temporaryHashSetto count its distinct elements. - Use a third loop to iterate from
itoj, adding each element to theHashSet. - Add the size of the
HashSetto theuniqueness_array. - After iterating through all subarrays, sort the
uniqueness_array. - The total number of subarrays is
L = n * (n + 1) / 2. The median is the element at index(L - 1) / 2in the sorted array.
Walkthrough
The algorithm works by systematically considering every single subarray. For an array of length n, there are n * (n + 1) / 2 subarrays. For each of these subarrays, we perform a separate calculation to find the number of unique elements. This is done by creating a new hash set for each subarray and populating it with the subarray's elements. The size of the set gives the uniqueness count. All these counts are stored in a list, which is then sorted to find the median.
import java.util.*; class Solution { public int medianOfUniquenessArray(int[] nums) { int n = nums.length; List<Integer> uniqueness_array = new ArrayList<>(); for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { Set<Integer> distinctElements = new HashSet<>(); // Subarray is nums[i..j] for (int k = i; k <= j; k++) { distinctElements.add(nums[k]); } uniqueness_array.add(distinctElements.size()); } } Collections.sort(uniqueness_array); int size = uniqueness_array.size(); return uniqueness_array.get((size - 1) / 2); }}Complexity
Time
O(N^3), where N is the length of `nums`. There are `O(N^2)` subarrays. For each subarray of average length `O(N)`, we iterate through it to count distinct elements, leading to `O(N^3)` complexity. Sorting adds `O(N^2 log N)`, but it's dominated by the generation part.
Space
O(N^2), where N is the length of `nums`. We need to store the uniqueness value for each of the `O(N^2)` subarrays.
Trade-offs
Pros
Simple to understand and implement.
Directly translates the problem statement into code.
Cons
Extremely inefficient due to its cubic time complexity.
Will result in a 'Time Limit Exceeded' error for even moderately sized inputs (e.g., n > 200).
Requires a large amount of memory to store the uniqueness values for all subarrays.
This approach improves upon the naive brute force method by optimizing the process of counting distinct elements. Instead of re-calculating for each subarray from scratch, we can iterate through all possible starting points and extend the subarray one element at a time, updating the count of distinct elements incrementally using a single HashSet for each starting point.
Algorithm
- Initialize an empty list,
uniqueness_array. - Iterate through each possible starting index
ifrom0ton-1. - For each
i, initialize aHashSetto keep track of distinct elements for subarrays starting ati. - Start a second loop for the ending index
jfromiton-1. - In the inner loop, add
nums[j]to theHashSet. The size of the set at this point is the number of distinct elements innums[i..j]. - Add the set's size to the
uniqueness_array. - After the loops complete, sort the
uniqueness_array. - Return the median element at index
(size - 1) / 2.
Walkthrough
The core idea is to fix the starting point i of a subarray and then extend the end point j from i to n-1. As we extend the subarray, we maintain a HashSet of the elements seen so far for that specific starting point. This avoids the third nested loop of the previous approach. For each pair of (i, j), we get the count of distinct elements in O(1) average time (the time to add an element to the set) and add it to our list. Finally, we sort this list of O(N^2) values to find the median.
import java.util.*; class Solution { public int medianOfUniquenessArray(int[] nums) { int n = nums.length; List<Integer> uniqueness_array = new ArrayList<>(); for (int i = 0; i < n; i++) { Set<Integer> distinctElements = new HashSet<>(); for (int j = i; j < n; j++) { distinctElements.add(nums[j]); uniqueness_array.add(distinctElements.size()); } } Collections.sort(uniqueness_array); int size = uniqueness_array.size(); return uniqueness_array.get((size - 1) / 2); }}Complexity
Time
O(N^2 log N). Generating the `O(N^2)` uniqueness values takes `O(N^2)` time because the set operations are `O(1)` on average. Sorting the `O(N^2)` values takes `O(N^2 log(N^2))`, which simplifies to `O(N^2 log N)`.
Space
O(N^2). The `uniqueness_array` stores `O(N^2)` elements. The `HashSet` uses up to `O(N)` space within the loops.
Trade-offs
Pros
More efficient than the naive O(N^3) brute-force approach.
Still relatively easy to understand.
Cons
Still too slow and memory-intensive for the given constraints.
Will result in a 'Time Limit Exceeded' or 'Memory Limit Exceeded' error on large inputs.
The most efficient approach recognizes that we don't need to generate the entire uniqueness array. The values in this array (number of distinct elements) are bounded between 1 and N. This allows us to binary search for the median value. For a candidate median m, we can efficiently check if it's the true median by counting how many subarrays have at most m distinct elements. If this count is at least k (where k is the rank of the median), then the true median is m or smaller, guiding our binary search.
Algorithm
- Calculate the total number of subarrays,
total = n * (n + 1) / 2. - Determine the rank of the median element,
k = (total + 1) / 2. - Perform a binary search for the answer (the median value) in the range
[1, n]. - For each candidate median
xin the binary search:- Count the number of subarrays that have at most
xdistinct elements. This is done using a sliding window (two-pointer) technique inO(n)time. - Let this count be
count_le(x).
- Count the number of subarrays that have at most
- If
count_le(x) >= k, it means the true median is less than or equal tox. We recordxas a potential answer and search in the lower half (high = x - 1). - If
count_le(x) < k, the median must be greater thanx. We search in the upper half (low = x + 1). - The final answer is the smallest
xfor whichcount_le(x) >= k.
Walkthrough
The problem of finding the k-th element in a very large, implicitly defined, and monotonic-property-holding search space is a classic use case for Binary Search on the Answer. The search space for the median is [1, N]. For any candidate median x, we need a helper function countAtMost(x) that counts subarrays with at most x distinct elements. This subproblem can be solved efficiently in O(N) time using a sliding window. We use two pointers, left and right, and a frequency map. We expand the window by moving right and shrink it by moving left whenever the number of distinct elements exceeds x. For each right, the number of valid subarrays ending at right is right - left + 1. Summing this up gives countAtMost(x). The binary search then uses this count to narrow down the range for the median.
import java.util.*; class Solution { public int medianOfUniquenessArray(int[] nums) { int n = nums.length; long totalSubarrays = (long) n * (n + 1) / 2; long medianRank = (totalSubarrays + 1) / 2; int low = 1, high = n; int ans = n; while (low <= high) { int mid = low + (high - low) / 2; if (countSubarraysWithAtMostKDistinct(nums, mid) >= medianRank) { ans = mid; high = mid - 1; } else { low = mid + 1; } } return ans; } private long countSubarraysWithAtMostKDistinct(int[] nums, int k) { int n = nums.length; long count = 0; int left = 0; Map<Integer, Integer> freq = new HashMap<>(); for (int right = 0; right < n; right++) { freq.put(nums[right], freq.getOrDefault(nums[right], 0) + 1); while (freq.size() > k) { freq.put(nums[left], freq.get(nums[left]) - 1); if (freq.get(nums[left]) == 0) { freq.remove(nums[left]); } left++; } count += (right - left + 1); } return count; }}Complexity
Time
O(N log N). The binary search runs `O(log N)` times. Inside the binary search, the `countSubarraysWithAtMostKDistinct` function uses a sliding window which takes `O(N)` time.
Space
O(N). The `HashMap` used in the sliding window approach can store up to `N` distinct elements in the worst case.
Trade-offs
Pros
Highly efficient and can handle the given constraints.
Avoids the costly generation and sorting of the entire uniqueness array.
Demonstrates a powerful problem-solving pattern (Binary Search on Answer).
Cons
More complex to conceptualize and implement compared to the brute-force approaches.
Requires understanding of both binary search on the answer and the sliding window technique.
Solutions
Solution
class Solution {private long m;private int[] nums;public int medianOfUniquenessArray(int[] nums) { int n = nums.length; this.nums = nums; m = (1L + n) * n / 2; int l = 0, r = n; while (l < r) { int mid = (l + r) >> 1; if (check(mid)) { r = mid; } else { l = mid + 1; } } return l; }private boolean check(int mx) { Map<Integer, Integer> cnt = new HashMap<>(); long k = 0; for (int l = 0, r = 0; r < nums.length; ++r) { int x = nums[r]; cnt.merge(x, 1, Integer : : sum); while (cnt.size() > mx) { int y = nums[l++]; if (cnt.merge(y, -1, Integer : : sum) == 0) { cnt.remove(y); } } k += r - l + 1; if (k >= (m + 1) / 2) { return true; } } return false; }}class Solution {public: int medianOfUniquenessArray(vector<int> &nums) { int n = nums.size(); using ll = long long; ll m = (1LL + n) * n / 2; int l = 0, r = n; auto check = [&](int mx) -> bool { unordered_map<int, int> cnt; ll k = 0; for (int l = 0, r = 0; r < n; ++r) { int x = nums[r]; ++cnt[x]; while (cnt.size() > mx) { int y = nums[l++]; if (--cnt[y] == 0) { cnt.erase(y); } } k += r - l + 1; if (k >= (m + 1) / 2) { return true; } } return false; }; while (l < r) { int mid = (l + r) >> 1; if (check(mid)) { r = mid; } else { l = mid + 1; } } return l; }};class Solution: def medianOfUniquenessArray(self, nums: List[int]) -> int: def check(mx: int) -> bool: cnt = defaultdict(int) k = l = 0 for r, x in enumerate(nums): cnt[x] += 1 while len(cnt) > mx: y = nums[l] cnt[y] -= 1 if cnt[y] == 0: cnt . pop(y) l += 1 k += r - l + 1 if k >= (m + 1) // 2: return True return False n = len(nums) m = (1 + n) * n // 2 return bisect_left(range(n), True, key=check)Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.