FastPrep
Problem · Binary Search

Find Median of Subarray Uniqueness 🥑

Learn this problem
● HardAmazonFULLTIMEOA
See Amazon hiring insights

Problem 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:

  • 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 of [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

    findMedianOfSubarrayUniqueness(arr: int[]) → int

    Complete the function findMedianOfSubarrayUniqueness in the editor.

    findMedianOfSubarrayUniqueness has the following parameter:

    1. int arr[n]: the array

    Returns

    int: the median of the generated array subarray_uniqueness

    Constraints

    • 1 ≤ n ≤ 10^5
    • 1 ≤ arr[i] ≤ n

    Examples

    Example 1

    arr = [1, 1]return = 1
    The subarrays along with their uniqueness values are:
  • [1]: uniqueness = 1
  • [1, 1]: uniqueness = 1
  • [1]: uniqueness = 1
    • subarray_uniqueness is [1, 1, 1].

    Example 2

    arr = [1, 2, 3]return = 1
    Given n = 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 = 1
    • subarray_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
    The subarrays 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 arr is [1, 1, 1, 2, 2, 2]. The choice is between the two bold values. Return the min of the two, 1. [1]: uniqueness = 1

    More Amazon problems

    drafts saved locally
    public int findMedianOfSubarrayUniqueness(int[] arr) {
    // write your code here
}
    arr[1, 1]
    expected1
    checking account