The k Strongest Values in an Array — LeetCode 1471 Python Solution

The problem

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.

Example

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.

Python solution

class Solution:
    def getStrongest(self, arr: List[int], k: int) -> List[int]:
        arr.sort()
        m = arr[(len(arr) - 1) >> 1]
        arr.sort(key=lambda x: (-abs(x - m), -x))
        return arr[:k]

Complexity

Pattern: Two Pointers

Use the order already in the input to discard half the search space at every step. LeetCode 1471. The k Strongest Values in an Array is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Two Pointers.

The two pointers guide has the Python template for the pattern and the 201 LeetCode problems that use it.

Related problems