Find Array Uniqueness Median 🐈
Microsoft● HardFULLTIMEOAProblem statement
The uniqueness of an array of integers is defined as the number of distinct elements present.
For example, the uniqueness of [1, 5, 2, 1, 3, 5] is 4, element values 1, 2, 3, and 5.
For an array arr of n integers, the uniqueness values of its subarrays is generated and stored in another array, call it subarray_uniqueness.
Notes:
- The median of a list is defined as the middle value of the list when it is sorted in non-decreasing order. If there are multiple choices for median, the smaller of the two values is taken.
For example, the median of [1, 5, 8] is 5, and [2, 3, 7, 11] is 3.
- A subarray is a contiguous part of the array.
For example, [1, 2, 3] is a subarray of [6, 1, 2, 3, 5] but [6, 2] is not.
Function
findArrayUniquenessMedian(arr: int[]) → int
Complete the function findArrayUniquenessMedian in the editor.
findArrayUniquenessMedian has the following parameter:
int[] arr: an array of integers
Returns
int: the median of the uniqueness values of all subarrays of arr
Examples
Example 1
arr = [1, 2, 1]return = 1
There are n = 3 elements in arr = [1, 2, 1]. The subarrays along with their uniqueness values are:
[1]: uniqueness = 1[1, 2]: uniqueness = 2[1, 2, 1]: uniqueness = 2[2]: uniqueness = 1[2, 1]: uniqueness = 2[1]: uniqueness = 1
The subarray_uniqueness array is [1, 2, 2, 1, 2, 1]. After sorting, the array is [1, 1, 1, 2, 2, 2].
The choice is between the two bold values. Return the minimum of the two, 1. Output: 1
Example 2
arr = [1, 2, 3]return = 1arr = [1, 2, 3]
[1]: uniqueness = 1[1, 2]: uniqueness = 2[1, 2, 3]: uniqueness = 3[2]: uniqueness = 1[2, 3]: uniqueness = 2[3]: uniqueness = 1
After sorting, the array is [1, 1, 1, 2, 2, 3]. Output: 1.
Constraints
1 <= n <= 1e51 <= arr[i] <= 1e5