Problem

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|

|arr[j] - m|wheremis the **median** of the array. If|arr[i] - m| == |arr[j] - m|, then arr[i]is said to be stronger thanarr[j]ifarr[i] > arr[j]`.

Return a list of the strongestk 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.

Examples

Example 1

1
2
3
4

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 > 1.

Example 2

1
2
3

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

1
2
3
4

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**.

Constraints

  • 1 <= arr.length <= 10^5
  • -10^5 <= arr[i] <= 10^5
  • 1 <= k <= arr.length

Solution

Method 1 - Two Pointers After Sorting

Sort the array, find the median, then use two pointers to select the k strongest values by the problem’s definition.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

#include <vector>
#include <algorithm>
using namespace std;
vector<int> getStrongest(vector<int>& arr, int k) {
    sort(arr.begin(), arr.end());
    int n = arr.size(), m = arr[(n-1)/2];
    int l = 0, r = n-1;
    vector<int> res;
    while (res.size() < k) {
        if (abs(arr[l] - m) > abs(arr[r] - m) || (abs(arr[l] - m) == abs(arr[r] - m) && arr[l] > arr[r]))
            res.push_back(arr[l++]);
        else
            res.push_back(arr[r--]);
    }
    return res;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

import java.util.*;
class Solution {
    public int[] getStrongest(int[] arr, int k) {
        Arrays.sort(arr);
        int n = arr.length, m = arr[(n-1)/2];
        int l = 0, r = n-1;
        int[] res = new int[k];
        for (int i = 0; i < k; ++i) {
            if (Math.abs(arr[l] - m) > Math.abs(arr[r] - m) || (Math.abs(arr[l] - m) == Math.abs(arr[r] - m) && arr[l] > arr[r]))
                res[i] = arr[l++];
            else
                res[i] = arr[r--];
        }
        return res;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

from typing import List
def getStrongest(arr: List[int], k: int) -> List[int]:
    arr.sort()
    n = len(arr)
    m = arr[(n-1)//2]
    l, r = 0, n-1
    res = []
    while len(res) < k:
        if abs(arr[l] - m) > abs(arr[r] - m) or (abs(arr[l] - m) == abs(arr[r] - m) and arr[l] > arr[r]):
            res.append(arr[l])
            l += 1
        else:
            res.append(arr[r])
            r -= 1
    return res
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

pub fn get_strongest(mut arr: Vec<i32>, k: i32) -> Vec<i32> {
    arr.sort();
    let n = arr.len();
    let m = arr[(n-1)/2];
    let (mut l, mut r) = (0, n-1);
    let mut res = Vec::new();
    while res.len() < k as usize {
        if (arr[l] - m).abs() > (arr[r] - m).abs() || ((arr[l] - m).abs() == (arr[r] - m).abs() && arr[l] > arr[r]) {
            res.push(arr[l]);
            l += 1;
        } else {
            res.push(arr[r]);
            r -= 1;
        }
    }
    res
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

function getStrongest(arr: number[], k: number): number[] {
    arr.sort((a, b) => a - b);
    const n = arr.length, m = arr[(n-1)>>1];
    let l = 0, r = n-1, res: number[] = [];
    while (res.length < k) {
        if (Math.abs(arr[l] - m) > Math.abs(arr[r] - m) || (Math.abs(arr[l] - m) === Math.abs(arr[r] - m) && arr[l] > arr[r]))
            res.push(arr[l++]);
        else
            res.push(arr[r--]);
    }
    return res;
}

Complexity

  • ⏰ Time complexity: O(n log n)
  • 🧺 Space complexity: O(k)