Skip to main content
Talentd

Find the Median of the Uniqueness Array - Solution & Explanation

HardArrayHash TableBinary SearchSliding Window24 min readAsked at: Amazon, Microsoft
Practice this problem

Problem Statement

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 <= 105
  • 1 <= nums[i] <= 105

Approach Overview

Problem 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 1: Divide and Conquer

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n)
Space Complexity: O(log n) due to recursive stack space.

Try this approach in the editor →

Approach 2: Iterative Solution With Stack

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n)
Space Complexity: O(n) for stack usage.

Try this approach in the editor →

Approach 3: Binary Search + Two Pointers

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Divide and Conquer

Time Complexity: O(n log n)
Space Complexity: O(log n) due to recursive stack space.

Iterative Solution With Stack

Time Complexity: O(n log n)
Space Complexity: O(n) for stack usage.

Binary Search + Two Pointers—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force with Hash SetO(n² log n)O(n²)Understanding the problem or when n is very small
Binary Search + Sliding WindowO(n log n)O(n)General optimal solution for large arrays

Video Solution

3134. Find the Median of the Uniqueness Array (Leetcode Hard) • Programming Live with Larry • 763 views views

Watch 4 more video solutions →

Frequently Asked Questions

Is Find the Median of the Uniqueness Array easy or hard?
Find the Median of the Uniqueness Array is considered a Hard problem because it combines multiple techniques: counting subarrays, sliding window frequency tracking, and binary search on the answer. Recognizing that the median can be found through monotonic counting rather than explicit enumeration is the main challenge.
Find the Median of the Uniqueness Array Python/Java solution
In Python or Java, implement a helper function that counts subarrays with at most k distinct elements using a hash map and two pointers. Wrap this function inside a binary search over the possible uniqueness range. This pattern keeps the implementation concise while maintaining O(n log n) performance.
How to solve Find the Median of the Uniqueness Array in O(n log n)?
First compute the total number of subarrays and determine the median index. Then binary search the possible uniqueness values. For each candidate value k, use a sliding window with a hash table to count how many subarrays contain at most k distinct elements. If the count is at least the median position, move the search left; otherwise move right.
What is the best approach for Find the Median of the Uniqueness Array?
The most efficient approach uses binary search on the answer combined with a sliding window counting technique. For each candidate uniqueness value k, count how many subarrays have at most k distinct elements using a hash map and two pointers. Binary search over the range of possible distinct counts finds the smallest value that satisfies the median position. The overall complexity is O(n log n) time and O(n) space.
Is Find the Median of the Uniqueness Array asked at Google/Amazon/Meta?
Problems combining sliding window counting with binary search frequently appear in interviews at companies like Google, Amazon, and Meta. Variants of counting subarrays with at most k distinct elements are especially common because they test understanding of two‑pointer techniques and frequency maps.
What data structure is used in Find the Median of the Uniqueness Array?
The solution mainly relies on a hash table (or dictionary) to store frequencies of elements in the sliding window. Two pointers maintain the window boundaries, and binary search is used to determine the median uniqueness value without enumerating every subarray.
What is the time complexity of Find the Median of the Uniqueness Array?
The optimal solution runs in O(n log n) time. Each step of the binary search performs a sliding window scan of the array in O(n) time to count subarrays with at most k distinct values. Space complexity is O(n) due to the frequency hash table used by the sliding window.

Ready to solve this problem?

Practice Find the Median of the Uniqueness Array with our built-in code editor and test cases.

Practice on FleetCode
Previous

Find K-th Smallest Pair Distance

Next

Total Appeal of A String