FastPrep

Description

Solutions

Find Array Uniqueness Median 🐈

🔥 FULLTIME📚RELATED PROBLEMS

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 Description

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

Example 1:

Input:  arr = [1, 2, 1]
Output: 1 
Explanation:
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:

Input:  arr = [1, 2, 3]
Output: 1 
Explanation:
arr = [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 <= 1e5
1 <= arr[i] <= 1e5