Skip to main content
Talentd

The k Strongest Values in an Array - Solution & Explanation

MediumArrayTwo PointersSorting17 min readAsked at: Google
Practice this problem

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 = 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.
  • For 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] <= 105
  • 1 <= 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.

Approach 1: Sort and Custom Sort

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:

  1. Sort the array and find the median.
  2. Define a comparison function that compares elements based on their distance to the median and their value if distances are equal.
  3. Sort the array using this comparison function.
  4. Select the first k elements from the sorted array.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n) due to sorting the array twice.

Space Complexity: O(1) for in-place sorting.

Try this approach in the editor →

Approach 2: Two Pointers Technique

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:

  1. Sort the array to find the median.
  2. Initialize two pointers: one at the beginning and the other at the end of the array.
  3. Iteratively select the stronger value from the two pointers until k values are selected, moving the pointers appropriately.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n) for the initial sorting.

Space Complexity: O(1) as it's done directly on the input array.

Try this approach in the editor →

Approach 3: Sorting

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Sort and Custom SortO(n log n)O(1)When you want the simplest implementation using a comparator that directly ranks elements by strength
Two Pointers TechniqueO(n log n)O(1)When the array is already sorted or after sorting once and you want to extract the k strongest efficiently

Video Solution

The k Strongest Values in an Array | LeetCode 1471 | Medium • Naresh Gupta • 635 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is The k Strongest Values in an Array easy or hard?
The problem is classified as Medium. The challenge comes from correctly interpreting the strength definition and using the median to compare elements. Once the array is sorted, the two pointer strategy makes the selection logic straightforward.
The k Strongest Values in an Array Python/Java solution
In Python or Java, sort the array first to compute the median. Then use two pointers from the start and end of the array, comparing absolute differences from the median and selecting the stronger value each step until k elements are collected.
How to solve The k Strongest Values in an Array in O(n)?
A theoretical O(n) solution could use Quickselect to find the median and then partition elements by strength relative to that median. However, implementing this correctly with the tie-breaking rule is more complex. Most practical solutions rely on sorting, giving O(n log n) time with simpler code.
What is the best approach for The k Strongest Values in an Array?
The two pointers approach after sorting the array is the most efficient and interview-friendly solution. First sort the array to determine the median, then compare elements from both ends using their distance from the median. This method selects the strongest values in O(n log n) time due to sorting and O(1) extra space.
Is The k Strongest Values in an Array asked at Google/Amazon/Meta?
Problems involving median-based comparisons, sorting, and two pointer selection frequently appear in interviews at companies like Amazon, Google, and Meta. Variants of this question test your ability to reason about ordering rules and efficiently extract top elements from an array.
What data structure is used in The k Strongest Values in an Array?
The primary structure is a standard array combined with sorting and pointer traversal. After sorting, two indices move inward from both ends to compare element strengths relative to the median. No complex data structures are required.
What is the time complexity of The k Strongest Values in an Array?
The dominant cost comes from sorting the array, which takes O(n log n) time. After sorting, selecting the k strongest elements with two pointers requires only O(k) additional operations. Space complexity remains O(1) if the result array is not counted.

Ready to solve this problem?

Practice The k Strongest Values in an Array with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays