Maximum and Minimum Median of Subsequences

Problem Statement

Maximum and Minimum Median of Subsequences Problem Description A new Amazon intern encountered a challenging task. Currently, the intern has n integers, where the value of the i -th 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 n integer, array values , and an integer k , the intern needs to find the maximum and minimum median overall subsequences of length k . Note on Median: For a subsequence of length k , sort the elements in non-decreasing order. The median is the element at index (k - 1) / 2 (using 0-based indexing and integer division). For example, if k=2 and the sorted subsequence is [a, b] , the median is a . If k=3 and the sorted subsequence is [a, b, c] , the median is b . Examples Example 1: Input: n = 3, values = [1, 2, 3], k = 2 Output: [2, 1] Explanation: The subsequences of length k=2 from [1, 2, 3] and their medians are: Subsequences of length k median [1, 2] 1 [1,