Algorithm Learning

English

简体中文

English

简体中文

Appearance

1471. The k Strongest Values in an Array Medium ​

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 example, given arr = [6, -3, 7, 2, 11], n = 5: the array sorted is arr = [-3, 2, 6, 7, 11], the median is arr[((5 - 1) / 2)] = arr[2] = 6.

For example, given arr = [-7, 22, 17, 3], n = 4: the array sorted is arr = [-7, 3, 17, 22], the median is arr[((4 - 1) / 2)] = arr[1] = 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.

Approach ​

Input: An integer array arr, an integer k

Output: Return the "strongest k elements" in the arr array. The strongest value implies maximizing the absolute difference with the median of the sorted arr array.

This is an opposite-direction two pointers problem.

First, we need to sort arr and get the value of the middle position based on (len(arr) - 1) // 2.

Then, use opposite-direction two pointers to compare the difference one by one with the median. Add the left one if the left difference is greater, and add the right one if the right difference is greater.

Since it's sorted, the right value must be greater than or equal to the left. Therefore, when the differences are equal, we also add the right value.

Whichever side's value is chosen, move the pointer of that side towards the center. You need to select a total of k values.

Finally, return the array of these k strongest values.

Implementation ​

python
class Solution:
    def getStrongest(self, arr: List[int], k: int) -> List[int]:
        # Sort the array for binary search
        arr.sort()
        n = len(arr)
        
        # Calculate the median index, note the handling of odd and even lengths
        mid = (n - 1) // 2
        median = arr[mid]
        
        # Initialize the result array and two pointers
        ans = []
        left = 0
        right = n - 1
        
        # Select k strongest elements
        while k > 0 and left <= right:
            # Calculate the absolute difference between the left/right pointers and the median
            left_diff = abs(arr[left] - median)
            right_diff = abs(arr[right] - median)
            
            # Compare the absolute differences, choosing the larger one
            if left_diff > right_diff:
                ans.append(arr[left])
                left += 1
            else:
                ans.append(arr[right])
                right -= 1
            
            k -= 1
        
        return ans
javascript
/**
 * @param {number[]} arr
 * @param {number} k
 * @return {number[]}
 */
var getStrongest = function(arr, k) {
    const ans = [];

    let left = 0;
    let right = arr.length - 1;

    arr.sort((a, b) => a - b);
    const mid = Math.floor((arr.length - 1) / 2);

    while (k > 0) {
        if (Math.abs(arr[left] - arr[mid]) > Math.abs(arr[right] - arr[mid])) {
            ans.push(arr[left]);
            left ++;
        } else {
            ans.push(arr[right]);
            right --;
        }

        k --;
    }

    return ans;
};

Complexity Analysis ​

  • Time Complexity: O(n log n)
  • Space Complexity: O(1) or O(n) depending on the sort implementation

1471. The k Strongest Values in an Array (English)1471. 数组中的 k 个最强值 (Chinese)