The k Strongest Values in an Array: Two-Pointer Selection
1471. The k Strongest Values in an Array asks you to define "strength" relative to the median, then pick the k strongest elements. The twist is how the problem defines the median (always the lower middle value) and how ties are broken (larger values win). Once you see how sorting sets up a two-pointer sweep, the solution falls into place quickly.
Given arr = [1, 2, 3, 4, 5] and k = 2, the sorted array is [1, 2, 3, 4, 5]. The median m = arr[(5-1)/2] = arr[2] = 3. The strength of each value is its absolute distance from the median: |1-3|=2, |2-3|=1, |3-3|=0, |4-3|=1, |5-3|=2. Values 1 and 5 are tied at strength 2, but 5 wins the tiebreak because 5 > 1. The answer is [5, 1].
Why this problem matters
This problem combines three core skills: sorting, understanding how a custom comparator works, and recognizing when a two-pointer approach beats brute force. In interviews, problems that layer multiple techniques test whether you can decompose a problem rather than reaching for a single trick.
The "strength" definition also forces you to think carefully about tie-breaking rules. Many sorting problems have a secondary comparator, and getting comfortable with that pattern transfers directly to problems like Top K Frequent Elements and custom interval sorting.
The key insight
After sorting the array, the strongest values live at the extremes. The elements farthest from the median are at the left end (small values) and the right end (large values). You do not need to compute every strength and sort by it. Instead, place one pointer at each end of the sorted array and greedily pick whichever pointer points to the stronger value. This is the same two-pointer pattern you see in Container With Most Water and 3Sum, but applied to strength instead of area.
The solution
def get_strongest(arr: list[int], k: int) -> list[int]:
arr.sort()
m = arr[(len(arr) - 1) // 2]
result = []
left, right = 0, len(arr) - 1
while len(result) < k:
if abs(arr[right] - m) >= abs(arr[left] - m):
result.append(arr[right])
right -= 1
else:
result.append(arr[left])
left += 1
return result
The algorithm has three stages. First, sort the array. Second, find the median at index (n - 1) // 2. Third, run two pointers from the ends inward, always picking the stronger side. The >= in the comparison handles the tiebreak rule: when strengths are equal, arr[right] >= arr[left] is always true (since the array is sorted), so the right pointer's value wins.
The tiebreak is baked into the pointer logic. In a sorted array, arr[right] is always at least as large as arr[left]. When their distances from the median are equal, picking the right side automatically picks the larger value, which matches the problem's tiebreak rule. No extra condition needed.
Visual walkthrough
Step 1: Sort the array and find the median
Sort arr = [1, 2, 3, 4, 5]. Median index = (5-1)/2 = 2, so m = 3.
Step 2: Place two pointers at both ends
left=0 (value 1, strength 2), right=4 (value 5, strength 2). The strongest values live at the extremes.
Step 3: Compare strengths. Pick 5 (tiebreak: 5 > 1)
|5-3|=2 vs |1-3|=2. Equal strength, but 5 > 1, so pick right. Move right pointer inward. Result = [5].
Step 4: Compare again. Pick 1 (stronger than 4)
|4-3|=1 vs |1-3|=2. Left is stronger. Pick left. Result = [5, 1]. We have k=2 values, done.
Each comparison picks one value and moves the corresponding pointer inward. After k picks, you have your answer. The two pointers never cross because we stop after exactly k iterations, and k is always at most n.
Complexity analysis
| Approach | Time | Space |
|---|---|---|
| Sort + two pointers | O(n log n) | O(n) for the result |
| Sort + custom comparator | O(n log n) | O(n) |
| Brute force (compute all strengths, sort) | O(n log n) | O(n) |
The sorting step dominates at O(n log n). The two-pointer sweep itself is O(k), which is at most O(n). All approaches share the same time complexity, but the two-pointer version avoids building a separate list of (strength, value) pairs and re-sorting it. It is cleaner and uses less overhead.
The space is O(n) for the result array. If you count the sort as in-place (Python's .sort() is in-place), the auxiliary space beyond the result is O(1).
The building blocks
1. Sorting as preprocessing
Sorting transforms a scattered array into one where you can reason about positions. Here, sorting lets you find the median by index and guarantees that the strongest values sit at the edges. This is the same preprocessing step you use in problems like Two Sum (sorted variant) and 3Sum.
arr.sort()
median = arr[(len(arr) - 1) // 2]
2. Two-pointer sweep from both ends
Once the array is sorted, two pointers converge from the outside in. At each step, you compare the values at both ends and consume whichever is stronger. This is the classic shrinking-window two-pointer pattern.
left, right = 0, len(arr) - 1
while len(result) < k:
if abs(arr[right] - m) >= abs(arr[left] - m):
result.append(arr[right])
right -= 1
else:
result.append(arr[left])
left += 1
3. Tiebreak via sorted order
When two elements have the same distance from the median, the larger one wins. In a sorted array, the right pointer always points to the larger value. By using >= instead of >, you automatically handle the tiebreak without a separate check.
if abs(arr[right] - m) >= abs(arr[left] - m):
# right wins ties because arr[right] >= arr[left]
Edge cases
- All elements are the same.
arr = [5, 5, 5],k = 2. Every element has strength 0. The tiebreak picks the rightmost values. The answer is[5, 5]. - k equals n. You return the entire array. The two pointers will sweep through every element before they meet.
- Even-length array.
arr = [6, 7, 11, 7, 6, 8]sorted is[6, 6, 7, 7, 8, 11]. Median index is(6-1)//2 = 2, som = 7. The lower median rule matters here. - Negative numbers.
arr = [-7, 11, -2, 0, 1]. The logic works unchanged because absolute distance handles negatives naturally. - k = 1. You pick the single strongest element, which is the one farthest from the median (with the tiebreak favoring the larger value).
From understanding to recall
The two-pointer sweep after sorting is a pattern that shows up in many problems, but the details vary each time. In this problem, the custom strength comparator and the tiebreak rule are the parts most likely to trip you up under pressure. Spaced repetition helps here: you practice writing the comparison condition from scratch until the >= trick for tiebreaking becomes automatic.
CodeBricks breaks this problem into its building blocks (sorting, median finding, two-pointer sweep) and drills each one independently. That way, when you see a new problem that combines these techniques, you can assemble the pieces instead of starting from zero.
Related posts
- Top K Frequent Elements - Another "pick the top k" problem, solved with heaps or bucket sort
- Kth Largest Element - Finding a single kth element using heaps or quickselect
- Sort Colors - The Dutch national flag algorithm, another pointer-based partition technique