Find Median of Subarray Uniqueness 🥑
Learn this problem
AmazonFULLTIMEOAProblem statement
In an Amazon coding marathon, the following challenge was given.
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 for discussion. Find the median of the generated array subarray_uniqueness.
Notes:
[1, 5, 8] is 5, and of [2, 3, 7, 11] is 3.[1, 2, 3] is a subarray of [6, 1, 2, 3, 5] but [6, 2] is not.Function
findMedianOfSubarrayUniqueness(arr: int[]) → int
Complete the function findMedianOfSubarrayUniqueness in the editor.
findMedianOfSubarrayUniqueness has the following parameter:
int arr[n]: the array
Returns
int: the median of the generated array subarray_uniqueness
Constraints
1 ≤ n ≤ 10^51 ≤ arr[i] ≤ n
Examples
Example 1
arr = [1, 1]return = 1[1]: uniqueness = 1[1, 1]: uniqueness = 1[1]: uniqueness = 1subarray_uniqueness is [1, 1 , 1].Example 2
arr = [1, 2, 3]return = 1n = 3 and arr = [1, 2, 3], the subarrays along with their uniqueness values are:
[1]: uniqueness = 1[1, 2]: uniqueness = 2[1, 2, 3]: uniqueness = 3[2]: uniqueness = 1[2, 3]: uniqueness = 2[3]: uniqueness = 1subarray_uniqueness is [1, 2, 3, 1, 2, 1], and after sorting it is [1, 1, 1, 2, 2, 3].Example 3
arr = [1, 2, 1]return = 1