Given an array of integers arr and an integer k.

A value arr[i] is said to be stronger than a value arr[j] if |arr[i] - m| &gt; |arr[j] - m| where m is the median of the array.
If |arr[i] - m| == |arr[j] - m|, then arr[i] is said to be stronger than arr[j] if arr[i] &gt; arr[j].

Return a list of the strongest k values in the array. return the answer in any arbitrary order.

Median is the middle value in an ordered integer list. More formally, if the length of the list is n, the median is the element in position ((n - 1) / 2) in the sorted list (0-indexed).


	For arr = [6, -3, 7, 2, 11], n = 5 and the median is obtained by sorting the array arr = [-3, 2, 6, 7, 11] and the median is arr[m] where m = ((5 - 1) / 2) = 2. The median is 6.
	For arr = [-7, 22, 17, 3], n = 4 and the median is obtained by sorting the array arr = [-7, 3, 17, 22] and the median is arr[m] where m = ((4 - 1) / 2) = 1. The median is 3.


&nbsp;
Example 1:

Input: arr = [1,2,3,4,5], k = 2
Output: [5,1]
Explanation: Median is 3, the elements of the array sorted by the strongest are [5,1,4,2,3]. The strongest 2 elements are [5, 1]. [1, 5] is also accepted answer.
Please note that although |5 - 3| == |1 - 3| but 5 is stronger than 1 because 5 &gt; 1.


Example 2:

Input: arr = [1,1,3,5,5], k = 2
Output: [5,5]
Explanation: Median is 3, the elements of the array sorted by the strongest are [5,5,1,1,3]. The strongest 2 elements are [5, 5].


Example 3:

Input: arr = [6,7,11,7,6,8], k = 5
Output: [11,8,6,6,7]
Explanation: Median is 7, the elements of the array sorted by the strongest are [11,8,6,6,7,7].
Any permutation of [11,8,6,6,7] is accepted.


&nbsp;
Constraints:


	1 &lt;= arr.length &lt;= 105
	-105 &lt;= arr[i] &lt;= 105
	1 &lt;= k &lt;= arr.length


class Solution:
    def getStrongest(self, arr: List[int], k: int) -> List[int]:
        n = len(arr)
        medInd = (n-1)//2
        arr = sorted(arr)
        med = arr[medInd]
        
        start, end = 0, n-1
        ans = []
        while start <= end and len(ans) < k:
            if abs(med - arr[end]) < abs(med - arr[start]):
                ans.append(arr[start])
                start += 1
            else:# abs(med - arr[end]) >= abs(med - arr[start]):
                # <= because end is always bigger in a sorted array
                ans.append(arr[end])
                end -= 1
        
        return ans
class Solution {
    public int[] getStrongest(int[] arr, int k) {
        int[] result = new int[k];
        int n = arr.length, left = 0, right = n - 1, idx = 0;
        Arrays.sort(arr);
        int median = arr[(n - 1) / 2];
        while (left <= right) {
            int diff_l = Math.abs(arr[left] - median);
            int diff_r = Math.abs(arr[right] - median);

            if (diff_r > diff_l)
                result[idx++] = arr[right--];
            else if (diff_l > diff_r)
                result[idx++] = arr[left++];
            else if (arr[right] > arr[left])
                result[idx++] = arr[right--];
            else
                result[idx++] = arr[left++];
            if (idx == k)
                break;
        }
        return result;
    }
}
class Solution 
{
public:
    vector<int> getStrongest(vector<int>& arr, int k) 
    {
        int n=arr.size();
        sort(arr.begin(),arr.end());
        int m=arr[(n-1)/2];
        priority_queue<pair<int,int>> pq;
        for(auto it: arr)
        {
            pq.push({abs(it-m),it});
        }
        vector<int> ans;
        while(k-- && !pq.empty())
        {
            ans.push_back(pq.top().second);
            pq.pop();
        }
        return ans;
    }
};
var getStrongest = function(arr, k) {
    // sort array so we can easily find median
    const sorted = arr.sort((a,b) => a-b)
    // get index of median
    const medianIndex = Math.floor(((sorted.length-1)/2))
    // get median
    const median = sorted[medianIndex]

    // custom sort function following the parameters given us in the description
    const compareFunction = (a, b) => {
        if (Math.abs(a-median) > Math.abs(b-median)) {
            return 1
        }
        else if (Math.abs(a-median) === Math.abs(b-median) && a > b) {
            return 1
        } else {
            return -1
        }
    }

    // sort array using our custom sort function
    const strongest = arr.sort(compareFunction).reverse().slice(0,k);

    return strongest;
};
The k Strongest Values in an Array