problemmediumalgorithmsleetcode-1471leetcode 1471leetcode1471

The k Strongest Values in an Array

MediumUpdated: Aug 2, 2025
Practice on:
LeetCode

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

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

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

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

C++
#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;
}
Java
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;
    }
}
Python
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
Rust
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
}
TypeScript
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)

Comments