LeetCode 1471 - The k Strongest Values in an Array

LeetCode Problem 1471

Difficulty: 🟡 Medium
Topics: Array, Two Pointers, Sorting

Solution

Problem Understanding

This problem asks us to find the k strongest values in an array according to a custom definition of "strength".

The first important detail is the definition of the array's centre. We do not use the average or median in the mathematical sense. Instead, we first sort the array, then select the element at index:

$$\frac{n - 1}{2}$$

using integer division. This value becomes the centre m.

Once we know the centre, the strength of a value is determined by two rules:

1. A value is stronger if its absolute distance from the centre is larger.
2. If two values have the same distance from the centre, the larger numerical value is considered stronger.

For example, if the centre is 3:

• 5 and 1 are both distance 2 away from the centre.
• Since the distances are equal, 5 is stronger because 5 > 1.

The output can be returned in any order, which simplifies implementation because we do not need to preserve a particular ordering in the result.

The constraints are important:

• arr.length can be as large as 10^5
• Values can range from -10^5 to 10^5

This immediately tells us that extremely slow approaches, such as repeatedly scanning the array or using nested comparisons, will not be efficient enough.

There are several edge cases worth noticing immediately:

• Arrays with duplicate values
• Arrays with negative numbers
• Arrays where many elements have equal strength
• Arrays of size 1
• Cases where k == arr.length, meaning every element must be returned
• Even-length arrays, where the centre is still defined using integer division after sorting

The problem guarantees:

• The array is non-empty
• k is always valid
• The centre always exists

These guarantees simplify implementation because we never need to handle invalid input.

Approaches

Brute Force Approach

The most direct way to solve the problem is:

1. Sort the array to compute the centre.
2. Compute the strength of every element.
3. Sort all elements again using a custom comparator:

• Larger |x - m| comes first
• If tied, larger x comes first

4. Return the first k elements.

This works because the custom sort exactly matches the problem definition of strength.

However, while correct, this approach performs a full custom sort of all elements after already sorting once to find the centre. The second sort dominates the runtime.

Although O(n log n) is acceptable for 10^5, we can do slightly better conceptually by avoiding unnecessary comparisons after sorting.

Key Insight

After sorting the array, the strongest values must come from the ends of the sorted array.

Why?

Because elements farthest from the centre naturally appear near the smallest and largest values in sorted order.

This means we can use a two-pointer technique:

• One pointer starts at the left end
• One pointer starts at the right end
• At each step, compare which side is stronger
• Take the stronger element and move that pointer inward

This works because:

• The array is already sorted
• Distance from the centre increases toward the edges
• Tie-breaking favors larger values, which naturally means preferring the right side in ties

This lets us select the strongest k elements in linear time after sorting.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n log n)	O(n)	Sort by custom strength comparator
Optimal	O(n log n)	O(1) excluding output	Sort once, then use two pointers

Algorithm Walkthrough

1. Sort the array in ascending order.

Sorting is necessary because the centre depends on the sorted order. It also enables the two-pointer strategy. 2. Compute the centre.

The centre index is:

$$(n - 1) // 2$$

and the centre value is:

$$m = arr[(n - 1) // 2]$$ 3. Initialize two pointers.

• left = 0
• right = n - 1

These pointers represent the smallest and largest remaining values. 4. Repeatedly choose the stronger value.

While we still need more elements:

• Compute:

• abs(arr[left] - m)

• abs(arr[right] - m)

• Compare strengths:

• If the right value is stronger, take it

• Otherwise, take the left value

Remember that ties are resolved by larger numerical value, so when distances are equal, the right side wins because the array is sorted. 5. Move the corresponding pointer inward.

• If we took the left value, increment left
• If we took the right value, decrement right

6. Continue until we collect k elements.

Why it works

The sorted array guarantees that the strongest remaining element must always be at one of the two ends.

Elements closer to the centre have smaller absolute differences from m, while elements farther away are positioned toward the extremes of the sorted array.

At every step, comparing only the two ends is sufficient because all interior elements are necessarily weaker than at least one boundary element.

The tie-breaking rule also aligns perfectly with sorted order:

• Equal distances favor the larger value
• The larger value is always on the right side

Therefore, greedily selecting the stronger endpoint at each step always produces the correct set of strongest elements.

Python Solution

from typing import List

class Solution:
    def getStrongest(self, arr: List[int], k: int) -> List[int]:
        arr.sort()

        n = len(arr)
        median = arr[(n - 1) // 2]

        left = 0
        right = n - 1

        result = []

        while len(result) < k:
            left_strength = abs(arr[left] - median)
            right_strength = abs(arr[right] - median)

            if right_strength > left_strength:
                result.append(arr[right])
                right -= 1
            elif right_strength < left_strength:
                result.append(arr[left])
                left += 1
            else:
                if arr[right] >= arr[left]:
                    result.append(arr[right])
                    right -= 1
                else:
                    result.append(arr[left])
                    left += 1

        return result

The implementation begins by sorting the array because both the centre calculation and the two-pointer strategy depend on sorted order.

After sorting, we compute the centre using index (n - 1) // 2.

Two pointers are then initialized:

• left starts at the smallest value
• right starts at the largest value

At each iteration, the code compares the strengths of the values at both ends. The stronger value is appended to the result list, and the corresponding pointer moves inward.

The tie-breaking rule is handled explicitly:

• If both distances are equal, the larger value wins
• Since the array is sorted, the larger value is typically on the right side

The loop continues until exactly k elements are collected.

Go Solution

package main

import (
	"math"
	"sort"
)

func getStrongest(arr []int, k int) []int {
	sort.Ints(arr)

	n := len(arr)
	median := arr[(n-1)/2]

	left := 0
	right := n - 1

	result := make([]int, 0, k)

	for len(result) < k {
		leftStrength := int(math.Abs(float64(arr[left] - median)))
		rightStrength := int(math.Abs(float64(arr[right] - median)))

		if rightStrength > leftStrength {
			result = append(result, arr[right])
			right--
		} else if rightStrength < leftStrength {
			result = append(result, arr[left])
			left++
		} else {
			if arr[right] >= arr[left] {
				result = append(result, arr[right])
				right--
			} else {
				result = append(result, arr[left])
				left++
			}
		}
	}

	return result
}

The Go implementation closely mirrors the Python solution.

One notable difference is the use of math.Abs, which operates on float64, so integer values must be converted before taking the absolute value and then converted back to integers.

The result slice is preallocated with capacity k to reduce reallocations during appends.

Go slices are dynamic views over arrays, so appending elements is efficient and natural for this problem.

Worked Examples

Example 1

Input:

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

After sorting:

[1,2,3,4,5]

Centre:

m = 3

Step	Left Value	Right Value	Left Strength	Right Strength	Chosen	Result
1	1	5	2	2	5	[5]
2	1	4	2	1	1	[5,1]

Final answer:

[5,1]

Example 2

Input:

arr = [1,1,3,5,5]
k = 2

Sorted array:

[1,1,3,5,5]

Centre:

m = 3

Step	Left Value	Right Value	Left Strength	Right Strength	Chosen	Result
1	1	5	2	2	5	[5]
2	1	5	2	2	5	[5,5]

Final answer:

[5,5]

Example 3

Input:

arr = [6,7,11,7,6,8]
k = 5

Sorted array:

[6,6,7,7,8,11]

Centre:

m = 7

Step	Left Value	Right Value	Left Strength	Right Strength	Chosen	Result
1	6	11	1	4	11	[11]
2	6	8	1	1	8	[11,8]
3	6	7	1	0	6	[11,8,6]
4	6	7	1	0	6	[11,8,6,6]
5	7	7	0	0	7	[11,8,6,6,7]

Final answer:

[11,8,6,6,7]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting dominates the runtime
Space	O(1) excluding output	Only pointers and variables are used

The sorting step requires O(n log n) time. After sorting, the two-pointer scan only processes at most k elements, which is O(n) in the worst case.

Therefore, the overall complexity is dominated by sorting.

The algorithm uses constant auxiliary space aside from the output list itself. The sorted array is modified in place.

Test Cases

from typing import List

class Solution:
    def getStrongest(self, arr: List[int], k: int) -> List[int]:
        arr.sort()

        n = len(arr)
        median = arr[(n - 1) // 2]

        left = 0
        right = n - 1

        result = []

        while len(result) < k:
            left_strength = abs(arr[left] - median)
            right_strength = abs(arr[right] - median)

            if right_strength > left_strength:
                result.append(arr[right])
                right -= 1
            elif right_strength < left_strength:
                result.append(arr[left])
                left += 1
            else:
                if arr[right] >= arr[left]:
                    result.append(arr[right])
                    right -= 1
                else:
                    result.append(arr[left])
                    left += 1

        return result

sol = Solution()

# Example 1
assert sorted(sol.getStrongest([1,2,3,4,5], 2)) == [1,5]

# Example 2
assert sorted(sol.getStrongest([1,1,3,5,5], 2)) == [5,5]

# Example 3
assert sorted(sol.getStrongest([6,7,11,7,6,8], 5)) == [6,6,7,8,11]

# Single element array
assert sol.getStrongest([10], 1) == [10]

# All elements identical
assert sorted(sol.getStrongest([4,4,4,4], 2)) == [4,4]

# Negative values
assert sorted(sol.getStrongest([-10,-5,0,5,10], 3)) == [-10,5,10]

# k equals array length
assert sorted(sol.getStrongest([1,2,3], 3)) == [1,2,3]

# Even length array
assert sorted(sol.getStrongest([1,2,3,4], 2)) == [1,4]

# Duplicate strong values
assert sorted(sol.getStrongest([1,5,5,5,2], 3)) == [1,5,5]

# Large tie case
assert sorted(sol.getStrongest([1,2,4,5], 2)) == [1,5]

Test	Why
[1,2,3,4,5], k=2	Basic odd-length example
[1,1,3,5,5], k=2	Duplicate strong values
[6,7,11,7,6,8], k=5	Mixed duplicates and ties
[10], k=1	Minimum input size
[4,4,4,4], k=2	All values identical
[-10,-5,0,5,10], k=3	Negative numbers
[1,2,3], k=3	Return entire array
[1,2,3,4], k=2	Even-length centre calculation
[1,5,5,5,2], k=3	Multiple strongest duplicates
[1,2,4,5], k=2	Tie-breaking behavior

Edge Cases

One important edge case is when the array contains only one element. In this situation, that element is automatically the centre and also the strongest value. A buggy implementation might incorrectly move pointers or assume multiple elements exist. The current implementation handles this naturally because the loop simply selects the single available value.

Another important case is when many elements have equal strength. For example, in [1,2,4,5], the values 1 and 5 are equally distant from the centre. The problem requires the larger value to be considered stronger. The implementation explicitly handles this tie-breaking rule by selecting the larger value when strengths are equal.

Arrays with many duplicate values can also cause issues. For example, [4,4,4,4] has zero distance from the centre for every element. A careless implementation might accidentally skip values or mishandle pointer movement. Since the algorithm always consumes exactly one endpoint per iteration, duplicates are handled correctly without special cases.

Even-length arrays are another subtle edge case. The centre is not the average of two middle values. Instead, the problem specifically defines the centre as the element at index (n - 1) // 2 after sorting. The implementation follows this definition exactly, avoiding incorrect median calculations.