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).
arr = [6, -3, 7, 2, 11], n = 5 and the median is obtained by sorting the array arr = [-3, 2, 6, 7, 11] and the median is arr[m] where m = ((5 - 1) / 2) = 2. The median is 6.arr = [-7, 22, 17, 3], n = 4 and the median is obtained by sorting the array arr = [-7, 3, 17, 22] and the median is arr[m] where m = ((4 - 1) / 2) = 1. The median is 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.
Constraints:
1 <= arr.length <= 105-105 <= arr[i] <= 1051 <= k <= arr.lengthProblem Overview: You receive an integer array and must return the k strongest values. Strength is defined relative to the median m of the sorted array. A value x is stronger than y if |x - m| > |y - m|, or if the distances are equal but x > y. The task is to efficiently pick the k elements with the highest strength.
Approach 1: Sort and Custom Sort (O(n log n) time, O(1) extra space)
Start by sorting the array to compute the median m = arr[(n-1)/2]. After the median is known, reorder elements by their strength using a custom comparator: compare |x - m| and |y - m|, and break ties using the actual value. This effectively ranks all elements by strength. Finally, return the first k values from the reordered array. This approach is straightforward and easy to implement using built-in sorting with a custom comparator. It relies heavily on sorting and simple arithmetic comparisons.
Approach 2: Two Pointers Technique (O(n log n) time, O(1) extra space)
Sort the array first to determine the median. Instead of re-sorting by strength, use two pointers: one at the start (left) and one at the end (right). At each step, compare the strengths of arr[left] and arr[right] using the median. If the right value is stronger, add it to the result and move right--; otherwise add the left value and move left++. Continue until k elements are selected. Because the array is already sorted, the strongest candidates always lie near the edges. This method combines array traversal with the classic two pointers pattern and avoids an additional full sort.
Recommended for interviews: The two pointers approach is typically preferred. Sorting first shows you understand how the median defines strength, and the pointer comparison efficiently extracts the top k candidates without an extra comparator sort. Interviewers often expect this reasoning because it demonstrates control over ordering and pointer-based scanning.
This approach utilizes sorting to find the median and then sorts the array again based on a custom comparator to determine the strongest elements.
Steps involved:
We first sort the array to find the median value. Using qsort_r, we sort the elements based on their 'strength', defined by their distance from the median. The result is then the first k elements from the 'strongly' sorted array.
Time Complexity: O(n log n) due to sorting the array twice.
Space Complexity: O(1) for in-place sorting.
This approach utilizes the two-pointer technique to find the strongest elements without the need for an additional sorting phase post-median discovery.
Steps involved:
After sorting to find the median, two pointers are used: one starting from the beginning and the other from the end. At each step, the stronger out of the elements pointed by these pointers is selected until k elements are processed.
Time Complexity: O(n log n) for the initial sorting.
Space Complexity: O(1) as it's done directly on the input array.
We first sort the array arr and then find the median m of the array.
Next, we sort the array according to the rules described in the problem, and finally return the first k elements of the array.
The time complexity is O(n times log n), and the space complexity is O(n). Here, n is the length of the array arr.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Sort and Custom Sort | Time Complexity: O(n log n) due to sorting the array twice. Space Complexity: O(1) for in-place sorting. |
| Two Pointers Technique | Time Complexity: O(n log n) for the initial sorting. Space Complexity: O(1) as it's done directly on the input array. |
| Sorting | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sort and Custom Sort | O(n log n) | O(1) | When you want the simplest implementation using a comparator that directly ranks elements by strength |
| Two Pointers Technique | O(n log n) | O(1) | When the array is already sorted or after sorting once and you want to extract the k strongest efficiently |
The k Strongest Values in an Array | LeetCode 1471 | Medium • Naresh Gupta • 616 views views
Watch 9 more video solutions →Practice The k Strongest Values in an Array with our built-in code editor and test cases.
Practice on FleetCode