Scale Engineer

The k Strongest Values in an Array

Med
#1358Time: O(N log N). Sorting to find the median is `O(N log N)`. The custom sort on `N` elements is also `O(N log N)`. The total time is dominated by these sorting steps.Space: O(N). We need an auxiliary array of `Integer` objects of size `N` to perform the custom sort, as Java's `Arrays.sort` with a `Comparator` requires an object array.
Patterns
Two Pointers
Algorithms
Sorting
Data structures
Array

Prompt

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| where m is the centre of the array.
If |arr[i] - m| == |arr[j] - m|, then arr[i] is said to be stronger than arr[j] if arr[i] > arr[j].

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

The centre is the middle value in an ordered integer list. More formally, if the length of the list is n, the centre 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 centre is obtained by sorting the array arr = [-3, 2, 6, 7, 11] and the centre is arr[m] where m = ((5 - 1) / 2) = 2. The centre is 6.
  • For arr = [-7, 22, 17, 3], n = 4 and the centre is obtained by sorting the array arr = [-7, 3, 17, 22] and the centre is arr[m] where m = ((4 - 1) / 2) = 1. The centre is 3.
 
 

 

 

 

Example 1:

Input: arr = [1,2,3,4,5], k = 2
Output: [5,1]
Explanation: Centre 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: Centre 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: Centre 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 <= 105
  • -105 <= arr[i] <= 105
  • 1 <= k <= arr.length

Approaches

3 approaches with complexity analysis and trade-offs.

This is a straightforward approach where we first determine the median of the array by sorting it. Then, we perform another sort on the entire array, this time using a custom comparison logic based on the definition of "strength". The strongest k values are simply the first k elements of this newly sorted array.

Algorithm

  • Sort the array arr to find the median m.
  • Convert arr to an Integer[] to allow for custom sorting.
  • Sort the Integer[] using a custom comparator based on strength. The strongest elements will come first.
  • Take the first k elements from the sorted array.

Walkthrough

The algorithm proceeds as follows:

  1. First, sort the array arr to find the median. The median m is the element at index (n-1)/2.
  2. To use a custom comparator with Arrays.sort, we convert the primitive int[] to an Integer[].
  3. Sort the Integer array using a custom Comparator. This comparator implements the strength logic:
    • For any two numbers a and b, it compares |a - m| and |b - m|.
    • The sort is in descending order of strength.
    • If the strengths are equal, it sorts in descending order of the numbers' values (a vs b).
  4. Finally, create a result array and copy the first k elements from the custom-sorted array.
import java.util.Arrays;import java.util.Collections; class Solution {    public int[] getStrongest(int[] arr, int k) {        int n = arr.length;        Arrays.sort(arr);        final int median = arr[(n - 1) / 2];         // Convert to Integer array for custom sorting        Integer[] integerArr = new Integer[n];        for (int i = 0; i < n; i++) {            integerArr[i] = arr[i];        }         // Custom sort based on strength        Arrays.sort(integerArr, (a, b) -> {            int strengthA = Math.abs(a - median);            int strengthB = Math.abs(b - median);            if (strengthA != strengthB) {                return Integer.compare(strengthB, strengthA); // Descending strength            } else {                return Integer.compare(b, a); // Descending value            }        });         // Get the first k elements        int[] result = new int[k];        for (int i = 0; i < k; i++) {            result[i] = integerArr[i];        }        return result;    }}

Complexity

Time

O(N log N). Sorting to find the median is `O(N log N)`. The custom sort on `N` elements is also `O(N log N)`. The total time is dominated by these sorting steps.

Space

O(N). We need an auxiliary array of `Integer` objects of size `N` to perform the custom sort, as Java's `Arrays.sort` with a `Comparator` requires an object array.

Trade-offs

Pros

  • Conceptually simple and easy to implement using standard library sorting functions.

Cons

  • Inefficient in both time and space.

  • It sorts the entire array of N elements based on strength, which is more work than necessary.

  • Requires O(N) extra space for the wrapper Integer array.

Solutions

class Solution {public  int[] getStrongest(int[] arr, int k) {    Arrays.sort(arr);    int m = arr[(arr.length - 1) >> 1];    List<Integer> nums = new ArrayList<>();    for (int v : arr) {      nums.add(v);    }    nums.sort((a, b)->{      int x = Math.abs(a - m);      int y = Math.abs(b - m);      return x == y ? b - a : y - x;    });    int[] ans = new int[k];    for (int i = 0; i < k; ++i) {      ans[i] = nums.get(i);    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem