The k Strongest Values in an Array

MEDIUM

Description

Given an array of integers arr and an integer k.

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 <= 10⁵
-10⁵ <= arr[i] <= 10⁵
1 <= k <= arr.length

Approaches

Checkout 3 different approaches to solve The k Strongest Values in an Array. Click on different approaches to view the approach and algorithm in detail.

Full Sort with Custom Comparator

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.

The algorithm proceeds as follows:

First, sort the array arr to find the median. The median m is the element at index (n-1)/2.
To use a custom comparator with Arrays.sort, we convert the primitive int[] to an Integer[].
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).
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 Analysis

Time Complexity: 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 Complexity: 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.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for The k Strongest Values in an Array. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for The k Strongest Values in an Array

Algorithms:

Sorting

Patterns:

Two Pointers

Data Structures:

Array