# Find the Median of the Uniqueness Array
**Difficulty:** HARD
[External](https://leetcode.com/problems/find-the-median-of-the-uniqueness-array)
Canonical: https://scaleengineer.com/dsa/problems/find-the-median-of-the-uniqueness-array
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array, Hash Table
---
## Problem
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`

# Approaches
## Brute Force Generation and Sort
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.
**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.
**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.
### Explanation
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.

```java
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);
    }
}
```
### Algorithm
*   Initialize an empty list, `uniqueness_array`.
*   Use a nested loop to iterate through all possible start (`i`) and end (`j`) indices of subarrays, where `0 <= i <= j < n`.
*   For each subarray `nums[i..j]`, create a temporary `HashSet` to count its distinct elements.
*   Use a third loop to iterate from `i` to `j`, adding each element to the `HashSet`.
*   Add the size of the `HashSet` to the `uniqueness_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) / 2` in the sorted array.

## Optimized Subarray Traversal
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.
**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.
**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.
### Explanation
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.

```java
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);
    }
}
```
### Algorithm
*   Initialize an empty list, `uniqueness_array`.
*   Iterate through each possible starting index `i` from `0` to `n-1`.
*   For each `i`, initialize a `HashSet` to keep track of distinct elements for subarrays starting at `i`.
*   Start a second loop for the ending index `j` from `i` to `n-1`.
*   In the inner loop, add `nums[j]` to the `HashSet`. The size of the set at this point is the number of distinct elements in `nums[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`.

## Binary Search on Answer with Sliding Window
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.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### 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 `x` in the binary search:
    *   Count the number of subarrays that have at most `x` distinct elements. This is done using a sliding window (two-pointer) technique in `O(n)` time.
    *   Let this count be `count_le(x)`.
*   If `count_le(x) >= k`, it means the true median is less than or equal to `x`. We record `x` as a potential answer and search in the lower half (`high = x - 1`).
*   If `count_le(x) < k`, the median must be greater than `x`. We search in the upper half (`low = x + 1`).
*   The final answer is the smallest `x` for which `count_le(x) >= k`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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)

```