The k Strongest Values in an Array

Medium
770.

The k Strongest Values in an Array

The k Strongest Values in an Array is a medium coding problem on arrays, sorting and two pointers, asked in Amazon, Microsoft and TCS interviews.

Let m be the median of arr, defined as the element at index (n - 1) / 2 after sorting (integer division).

A value a is stronger than b when |a - m| > |b - m|, or when the two distances tie and a > b.

Return the k strongest values, ordered from strongest to weakest.

Example 1

Input
arr = [1,2,3,4,5], k = 2
Output
[5,1]
Explanation
m = 3. Both 5 and 1 sit two away, and 5 > 1, so 5 comes first.

Example 2

Input
arr = [1,1,3,5,5], k = 2
Output
[5,5]
Explanation
m = 3, and the two 5s are the furthest.

Example 3

Input
arr = [6,7,11,7,6,8], k = 5
Output
[11,8,6,6,7]
Explanation
Sorted it is [6,6,7,7,8,11], so m = 7.

Constraints

  • 1 <= arr.length <= 100000
  • -100000 <= arr[i] <= 100000
  • 1 <= k <= arr.length
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} arr
 * @param {number} k
 * @return {number[]}
 */
var getStrongest = function(arr, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

The k Strongest Values in an Array — Problem & Solution

The k Strongest Values in an Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

The k Strongest Values in an Array is a medium coding problem on arrays, sorting and two pointers, asked in Amazon, Microsoft and TCS interviews.

  • Difficulty: Medium
  • Topics: Arrays, Sorting, Two Pointers
  • Asked at: Amazon, Microsoft, TCS
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Let m be the median of arr, defined as the element at index (n - 1) / 2 after sorting (integer division).

A value a is stronger than b when |a - m| > |b - m|, or when the two distances tie and a > b.

Return the k strongest values, ordered from strongest to weakest.

Example 1

Input: arr = [1,2,3,4,5], k = 2
Output: [5,1]
Explanation: m = 3. Both 5 and 1 sit two away, and 5 > 1, so 5 comes first.

Example 2

Input: arr = [1,1,3,5,5], k = 2
Output: [5,5]
Explanation: m = 3, and the two 5s are the furthest.

Example 3

Input: arr = [6,7,11,7,6,8], k = 5
Output: [11,8,6,6,7]
Explanation: Sorted it is [6,6,7,7,8,11], so m = 7.

Constraints

  • 1 <= arr.length <= 100000
  • -100000 <= arr[i] <= 100000
  • 1 <= k <= arr.length

Hints for The k Strongest Values in an Array

  1. Hint 1

    The median is not the average — it is the element at index (n - 1) / 2 of the sorted array.

  2. Hint 2

    Once m is known, strength is a total order on values, so a single sort by that comparator answers the question.

  3. Hint 3

    Linear alternative: after sorting, the strongest values are always at one of the two ends, so two pointers peel them off.

How to solve The k Strongest Values in an Array

Strength depends only on the distance to the median, with ties broken by the value itself. Both parts are decided once m is known, so the whole thing reduces to a sort by a custom comparator — or, after the sort that finds m, a linear two-pointer peel from both ends.

Approach

  1. Sort a copy and read m = sorted[(n - 1) / 2].
  2. Sort the values by |v - m| descending, breaking ties by v descending.
  3. Return the first k.

Why it works

The comparator is a strict weak ordering: distances are compared first, and equal distances are broken by value, which is itself a total order. Sorting therefore lists the values from strongest to weakest, and the first k are exactly the answer. The two-pointer variant works because on a sorted array the furthest value from m is always at one end.

Complexity

  • Time — O(n log n)
  • Space — O(n)

Pitfalls

  • Using the arithmetic mean, or index n / 2, gives the wrong median for even lengths.
  • Comparing distances with >= instead of splitting the tie on value gets the order wrong when two values are equidistant.
  • Distances reach 2 · 10^5, so plain int is fine.

Reference solution

Python

from typing import List

def getStrongest(arr: List[int], k: int) -> List[int]:
    s = sorted(arr)
    m = s[(len(s) - 1) // 2]
    order = sorted(arr, key=lambda v: (-abs(v - m), -v))
    return order[:k]

Java

public static int[] getStrongest(int[] arr, int k) {
    int n = arr.length;
    int[] s = arr.clone();
    Arrays.sort(s);
    final int m = s[(n - 1) / 2];
    Integer[] order = new Integer[n];
    for (int i = 0; i < n; i++) order[i] = arr[i];
    Arrays.sort(order, (a, b) -> {
        int da = Math.abs(a - m), db = Math.abs(b - m);
        if (da != db) return Integer.compare(db, da);
        return Integer.compare(b, a);
    });
    int[] res = new int[k];
    for (int i = 0; i < k; i++) res[i] = order[i];
    return res;
}

C++

vector<int> getStrongest(vector<int>& arr, int k) {
    vector<int> s = arr;
    sort(s.begin(), s.end());
    int m = s[(int) (s.size() - 1) / 2];
    vector<int> order = arr;
    sort(order.begin(), order.end(), [m](int a, int b) {
        int da = abs(a - m), db = abs(b - m);
        if (da != db) return da > db;
        return a > b;
    });
    return vector<int>(order.begin(), order.begin() + k);
}

JavaScript

var getStrongest = function(arr, k) {
    var s = arr.slice().sort(function(a, b) { return a - b; });
    var m = s[Math.floor((s.length - 1) / 2)];
    var order = arr.slice().sort(function(a, b) {
        var da = Math.abs(a - m), db = Math.abs(b - m);
        if (da !== db) return db - da;
        return b - a;
    });
    return order.slice(0, k);
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms