A new Amazon intern encountered a challenging task.
Currently, the intern has n integers, where the value of the ith element is represented by the array element values[i].
The intern is curious to play with arrays and subsequences and thus asks you to join him.
Given an integer array values and an integer k, find the maximum and minimum median among all subsequences of length k.
Return an integer array in the form [maximum median, minimum median].
Example:
Given values = [1, 2, 3] and k = 2, the subsequences of length 2 are [1, 2], [1, 3], and [2, 3]. Their medians are 1, 1, and 2 respectively. The maximum median is 2 and the minimum median is 1.
Complete the function medians in the editor below.
medians has the following parameter(s):
values[n]: the array of integersk: the given integer
Returns
int[]: the maximum and minimum median among all subsequences of lengthkin the form[maximum median, minimum median].
This Amazon OA problem is about understanding how the median behaves in subsequences of length <code>k</code>. Since the subsequence does not need to be contiguous, sorting the array is enough to reason about the possible medians. With the median definition used by the examples, the answer can be derived directly from positions in the sorted array: one value for the maximum median and one for the minimum median. The key insight is that the problem reduces to a sorted-index lookup rather than enumerating subsequences, giving an <code>O(n log n)</code> solution dominated by sorting.
