Extreme Subsequence Medians

Easy

0/40

0 upvote

Asked in company

Problem statement

You are given an array of n integers and an integer k. Your task is to find the maximum and minimum possible median values among all possible subsequences of length k.

A subsequence is a sequence that can be derived from the array by deleting zero or more elements without changing the order of the remaining elements. The median of a subsequence is the middle element after it has been sorted.

1) For a subsequence of odd length k, the median is the element at position (k+1)/2 (1-based).

2) For a subsequence of even length k, the median is the element at position k/2 (the lower-middle element, 1-based).

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of input contains two space-separated integers, 'n' and 'k'.

The second line contains 'n' space-separated integers, representing the elements of the array.

Output Format:

Print a single line containing two space-separated integers: the maximum possible median followed by the minimum possible median.

Note:

The key insight is that the order of elements in the original array does not affect the values within a chosen subsequence, only their eligibility.

Sample Input 1:

3 2
1 2 3

Sample Output 1:

2 1

Explanation for Sample 1:

The array is `{1, 2, 3}` and k=2.
To find the minimum median: Pick the k=2 smallest elements: `{1, 2}`. The median of `{1, 2}` is 1.
To find the maximum median: Pick the k=2 largest elements: `{2, 3}`. The median of `{2, 3}` is 2.

Sample Input 2:

5 3
10 20 30 40 50

Sample Output 2:

40 20

Explanation for Sample 2:

The array is already sorted. k=3.
Minimum Median: Subsequence `{10, 20, 30}`. Median is 20.
Maximum Median: Subsequence `{30, 40, 50}`. Median is 40.

Expected Time Complexity:

The expected time complexity is O(N log N).

Constraints:

1 <= k <= n <= 10^5
-10^9 <= array element <= 10^9

Time limit: 1 sec

Approaches (1)

Approach 1

Extreme Subsequence Medians

Time Complexity

Space Complexity

(100% EXP penalty)

Extreme Subsequence Medians

Console