Description
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
Solution
Python3
class Solution:
def medianOfUniquenessArray(self, nums: List[int]) -> int:
N = len(nums)
total = N * (N + 1) // 2
# to find the number of subarrays with at most k different numbers
def atMost(k):
counter = Counter()
count = unique = i = 0
for j, x in enumerate(nums):
counter[x] += 1
if counter[x] == 1:
unique += 1
while unique > k:
counter[nums[i]] -= 1
if counter[nums[i]] == 0:
unique -= 1
i += 1
count += j - i + 1
return count
left, right = 1, N
while left < right:
mid = left + (right - left) // 2
# atMost(k) >= total - atMost(k)
if atMost(mid) * 2 >= total:
right = mid
else:
left = mid + 1
return left