Maximum and Minimum Median of Subsequences

Problem Statement
An Amazon intern has an array of n integers called values and an integer k. The task is to find the maximum and minimum median among all possible subsequences of length k from this array. A subsequence maintains the original order but not necessarily contiguous positions. The median of a subsequence of length k is the ((k+1)/2)-th smallest element when sorted.[1][2]

Example
For n=3, values=, k=2:[2][3][1]

• Subsequences: (median=1), (median=1), (median=2).[3][1][2] Maximum median is 2; minimum median is 1.[1][3]

Constraints
Typical for Amazon OA: 1 ≤ n ≤ 10^5, 1 ≤ k ≤ n, values[i] in [-10^9, 10^9]. Exact bounds from OA not public, but solutions imply O(n log n) time via sorting is feasible.[2]