{x}
blog image

The k Strongest Values in an Array

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

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.

 

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

Solution Explanation: Finding the k Strongest Values

This problem requires finding the k strongest values in an array based on their distance from the median. The solution uses a two-step sorting process for efficiency.

Step 1: Find the Median

The median is the middle element of a sorted array. We efficiently find it by sorting the array (arr.sort() in Python, Arrays.sort(arr) in Java, etc.) and then accessing the middle element using arr[(len(arr) - 1) // 2] (integer division ensures correct indexing for even-length arrays).

Step 2: Sort by Strength

The core of the solution lies in the secondary sort. We need to sort the array based on the strength of each element. Strength is defined as:

  1. Distance from the Median: abs(arr[i] - m). Elements further from the median are stronger.
  2. Tiebreaker: If two elements have the same distance from the median, the larger element is stronger.

The sorting key functions in the code implement this logic. For example, in Python:

lambda x: (-abs(x - m), -x)

This lambda function sorts first by -abs(x - m) (descending order of distance, stronger elements first) and then by -x (descending order of element value, breaking ties in favor of larger elements). Similar logic is used in other languages; note how the comparison functions handle the distance and the tiebreaker.

Step 3: Return the Top k

After sorting by strength, the k strongest elements are simply the first k elements of the sorted array. We can use array slicing (arr[:k] in Python) or other equivalent methods to extract these elements.

Time Complexity Analysis:

  • Sorting: The dominant factor is the two sorting steps. Sorting an array of size n takes O(n log n) time using efficient algorithms like merge sort or quicksort (which are generally used by standard library sort functions).
  • Median Calculation: Finding the median after the first sort is O(1) (constant time).
  • Strength Calculation and Sorting: While we calculate the distance from the median for each element, this step is dominated by the O(n log n) sorting step.

Therefore, the overall time complexity is O(n log n).

Space Complexity Analysis:

  • In-place Sorting (most implementations): Many standard library sort functions perform the sorting in-place, meaning they don't require significant additional space beyond the original array.
  • Auxiliary Space: The space complexity is primarily determined by the space used by the sorting algorithm. In-place algorithms have O(1) auxiliary space, while some implementations might use O(n) space in the worst case. However, in practice, the space usage is usually quite modest.

Therefore, the space complexity is effectively O(1) for in-place sorting, or O(n) in the worst case if the sorting algorithm uses significant auxiliary space. The space used to store the final k strongest elements is insignificant compared to the size of the input array.

Code Examples (Refer to the detailed code examples in the original response): The provided code demonstrates the implementation of this solution in several programming languages, showcasing the consistent approach across languages. The core logic of sorting and using a custom comparison function or lambda remains the same.