#1471

Medium

auto_awesomeTwo-pointer scanning with invariant tracking

LeetCode Problem Workspace

The k Strongest Values in an Array

Identify the k strongest values in an array using two-pointer scanning and careful tracking of the array's centre value.

array two pointers sorting

Problem Statement

Given an integer array arr and a positive integer k, select k elements from arr considered the strongest according to the array's centre. The centre m is the median value after sorting arr. A number's strength is determined by its distance from m, with higher values preferred when distances are equal.

Return an array of k elements representing the strongest values. Multiple valid outputs may exist due to tie-breaking rules, but all must respect the strength ordering based on distance from the centre and value comparisons.

Examples

Example 1

Input: arr = [1,2,3,4,5], k = 2

Output: [5,1]

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]

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]

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

Solution Approach

Compute the Centre

Sort the array and identify the centre m as the middle element. This median-based centre is critical for calculating the strength of each element relative to m.

Two-Pointer Selection

Initialize pointers at both ends of the sorted array. Compare the absolute difference from m for left and right elements. Pick the stronger element each time, adjusting pointers accordingly, until k elements are selected.

Maintain Strength Invariant

During selection, always respect the tie-breaking rule: if distances are equal, choose the larger value. This invariant ensures the strongest elements are picked consistently and efficiently.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n log n) for sorting plus O(k) for two-pointer selection. Space complexity is O(n) if sorting a new array; O(1) extra if sorting in-place.

What Interviewers Usually Probe

Asks to clarify the definition of 'centre' and its impact on selection order.
Probes edge cases where multiple elements are equally strong.
Wants confirmation of two-pointer invariant handling for tie-breaking.

Common Pitfalls or Variants

Common pitfalls

Ignoring the tie-breaking rule when absolute distances are equal.
Using the wrong index for the centre in even-length arrays.
Selecting elements without updating pointers correctly, leading to duplicate picks.

Follow-up variants

Return the k weakest values instead, reversing the strength comparison.
Handle arrays with negative numbers and verify distance calculations still hold.
Select elements with the largest sum of distances from the centre instead of individual strength.

FAQ

How do you define the centre in 'The k Strongest Values in an Array' problem?

The centre is the median value of the sorted array, which determines how strength is calculated for each element.

Can the output array be in any order?

Yes, as long as the k elements selected are the strongest according to distance from the centre and tie-breaking rules.

Why use a two-pointer approach instead of fully sorting by strength?

Two-pointer scanning allows linear selection after sorting, reducing comparisons and handling tie-breaking efficiently.

How does tie-breaking work when two values are equally strong?

Choose the larger value when distances from the centre are equal to maintain the strength invariant.

What is a common mistake when implementing this two-pointer scanning pattern?

Failing to update pointers correctly or ignoring the tie-breaking rule can lead to incorrect selection of strongest elements.

terminal

Solution

Solution 1: Sorting

We first sort the array $\textit{arr}$ and then find the median $m$ of the array.

1

2

3

4

5

6

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]

Continue Practicing

#1498 number of subsequences that satisfy the given sum condition #1508 range sum of sorted subarray sums #1385 find the distance value between two arrays