The k Strongest Values in an Array - Video Solutions
The k Strongest Values in an Array | LeetCode 1471 | Medium
The k Strongest Values in an Array - Video Solution
Watch 10 video solutions for The k Strongest Values in an Array, a medium level problem involving Array, Two Pointers, Sorting. This walkthrough by Naresh Gupta has 635 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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).
- For
arr = [6, -3, 7, 2, 11],n = 5and the median is obtained by sorting the arrayarr = [-3, 2, 6, 7, 11]and the median isarr[m]wherem = ((5 - 1) / 2) = 2. The median is6. - For
arr = [-7, 22, 17, 3],n = 4and the median is obtained by sorting the arrayarr = [-7, 3, 17, 22]and the median isarr[m]wherem = ((4 - 1) / 2) = 1. The median is3.
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.length
Approach Overview
Problem 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.
Complexity Analysis
| 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 |