Problem Brief

Find Array Uniqueness Median 🐈

FULLTIMEOA

See Microsoft online assessment and hiring insights

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

1Example 1

Input

arr = [1, 2, 1]

Output

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

2Example 2

Input

arr = [1, 2, 3]

Output

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

Limits and guarantees your solution can rely on.

1 <= n <= 1e5
1 <= arr[i] <= 1e5