Get started

The k Strongest Values in an Array — Medium Problem & Solution

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

  • 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

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]

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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue