Find the Median of the Uniqueness Array

Find the Median of the Uniqueness Array

What is this problem about?

In the Find the Median of the Uniqueness Array coding problem, you are given an array nums. The "uniqueness array" is formed by taking the count of distinct elements in every possible contiguous subarray of nums. You need to find the median value of this uniqueness array.

Why is this asked in interviews?

This "Hard" problem is used by Microsoft and Amazon to test mastery of Binary Search on the Answer and Sliding Window techniques. Since the number of subarrays is $O(N^2)$, you cannot actually construct the uniqueness array. Instead, you must binary search for the median value $X$ and efficiently count how many subarrays have a uniqueness count $\le X$.

Algorithmic pattern used

This is a Binary Search on Answer problem.

1. The possible values for the uniqueness count are $[1, ext{DistinctCountInTotal}]$.
2. Binary search for a target value $M$.
3. For each $M$, count how many subarrays have $\le M$ distinct elements using a Sliding Window with a frequency map.
4. If the count of such subarrays is $\ge$ half of the total number of subarrays ($N(N+1)/4$), then the median is $\le M$.
5. Otherwise, the median is $> M$.

Example explanation

nums = [1, 2, 3]. Subarrays: [1], [2], [3], [1,2], [2,3], [1,2,3]. Uniqueness counts: 1, 1, 1, 2, 2, 3. Total subarrays = 6. Median is the 3rd or 4th value.

1. Try $M=1$: Subarrays with $\le 1$ distinct elements: [1], [2], [3]. Count = 3.
2. Since $3 \ge 6/2$, the median is 1. (Actually, for even counts, it's often the smaller of the two middle elements in these problems).

Common mistakes candidates make

• $O(N^2)$ approach: Trying to iterate through all subarrays to find the counts.
• Sliding Window Logic: Failing to correctly remove elements from the frequency map (forgetting to remove the key when count hits 0).
• Median Calculation: Getting the index of the median wrong when the total number of subarrays is large.

Interview preparation tip

When asked for the median of a virtual or derived array that is too large to store, always think about Binary Search on the possible value range. Combining this with a sliding window to count "at most $X$" is a top-tier algorithmic pattern.