1471. k Strongest Values in Array - Solution

The problem

Given an array of integers arr and an integer k.

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 <= 10⁵
-10⁵ <= arr[i] <= 10⁵
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:

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

Python

def get_strongest(arr, k):
    arr.sort()
    median = arr[(len(arr) - 1) // 2]
    arr.sort(key=lambda x: (abs(x - median), x), reverse=True)
    return arr[:k]

arr = [1, 2, 3, 4, 5]
k = 2
result = get_strongest(arr, k)
print(result)

Java

import java.util.Arrays;

public class StrongestValues {
    public static int[] getStrongest(int[] arr, int k) {
        Arrays.sort(arr);
        int median = arr[(arr.length - 1) / 2];
        Integer[] boxedArr = Arrays.stream(arr).boxed().toArray(Integer[]::new);
        Arrays.sort(boxedArr, (a, b) -> {
            int diffA = Math.abs(a - median), diffB = Math.abs(b - median);
            return diffA == diffB ? b - a : diffB - diffA;
        });
        return Arrays.stream(boxedArr).mapToInt(i -> i).limit(k).toArray();
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        int k = 2;
        int[] result = getStrongest(arr, k);
        System.out.println(Arrays.toString(result));
    }
}

C++

#include <iostream>
#include <vector>
#include <algorithm>

std::vector<int> getStrongest(std::vector<int>& arr, int k) {
    std::sort(arr.begin(), arr.end());
    int median = arr[(arr.size() - 1) / 2];
    std::sort(arr.begin(), arr.end(), [median](int a, int b) {
        int diffA = abs(a - median), diffB = abs(b - median);
        if (diffA == diffB) return a > b;
        return diffA > diffB;
    });
    return std::vector<int>(arr.begin(), arr.begin() + k);
}

int main() {
    std::vector<int> arr = {1, 2, 3, 4, 5};
    int k = 2;
    std::vector<int> result = getStrongest(arr, k);
    for (int num : result) {
        std::cout << num << ' ';
    }
    return 0;
}

JavaScript

function getStrongest(arr, k) {
    arr.sort((a, b) => a - b);
    const median = arr[Math.floor((arr.length - 1) / 2)];
    arr.sort((a, b) => {
        let diffA = Math.abs(a - median), diffB = Math.abs(b - median);
        if (diffA === diffB) return b - a;
        return diffB - diffA;
    });
    return arr.slice(0, k);
}

const arr = [1, 2, 3, 4, 5];
const k = 2;
const result = getStrongest(arr, k);
console.log(result);

#include <stdio.h>
#include <stdlib.h>

int compare(const void * a, const void * b, void * median_ptr) {
    int median = *(int*)median_ptr;
    int a_val = *(int*)a;
    int b_val = *(int*)b;
    int diff_a = abs(a_val - median);
    int diff_b = abs(b_val - median);
    if (diff_a == diff_b) return b_val - a_val;
    return diff_b - diff_a;
}

int compare_ints(const void * a, const void * b) {
    return *(int*)a - *(int*)b;
}

void strongestValues(int* arr, int arrSize, int k, int* returnArray) {
    qsort(arr, arrSize, sizeof(int), compare_ints);
    int median = arr[(arrSize - 1) / 2];
    qsort_r(arr, arrSize, sizeof(int), compare, &median);
    for (int i = 0; i < k; ++i) {
        returnArray[i] = arr[i];
    }
}

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int k = 2;
    int result[2];
    strongestValues(arr, 5, k, result);
    printf("["'%d', '%d']\n", result[0], result[1]);
    return 0;
}

using System;
using System.Linq;

public class StrongestValues {
    public static int[] GetStrongest(int[] arr, int k) {
        Array.Sort(arr);
        int median = arr[(arr.Length - 1) / 2];
        return arr.OrderByDescending(x => (Math.Abs(x - median), x)).Take(k).ToArray();
    }

    public static void Main() {
        int[] arr = {1, 2, 3, 4, 5};
        int k = 2;
        int[] result = GetStrongest(arr, k);
        Console.WriteLine(string.Join(", ", result));
    }
}

In Python, the solution involves sorting the array twice: first to find the median, and second using a lambda function that sorts based on the absolute difference to the median. The top k elements from this list of 'strongest' elements are returned.

Complexity

Time Complexity: O(n log n) primarily due to the sorting operations involved.

Space Complexity: O(n), mainly due to the internal workings of Python's sorting algorithm which might duplicate the list.

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:

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

Python

def get_strongest(arr, k):
    arr.sort()
    median = arr[(len(arr) - 1) // 2]
    left, right = 0, len(arr) - 1
    result = []
    while len(result) < k:
        if abs(arr[right] - median) >= abs(arr[left] - median):
            result.append(arr[right])
            right -= 1
        else:
            result.append(arr[left])
            left += 1
    return result

arr = [1, 2, 3, 4, 5]
k = 2
result = get_strongest(arr, k)
print(result)

Java

import java.util.Arrays;

public class StrongestValues {
    public static int[] getStrongest(int[] arr, int k) {
        Arrays.sort(arr);
        int median = arr[(arr.length - 1) / 2];
        int left = 0, right = arr.length - 1;
        int[] result = new int[k];
        int index = 0;
        while (index < k) {
            if (Math.abs(arr[right] - median) >= Math.abs(arr[left] - median)) {
                result[index++] = arr[right--];
            } else {
                result[index++] = arr[left++];
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        int k = 2;
        int[] result = getStrongest(arr, k);
        System.out.println(Arrays.toString(result));
    }
}

C++

#include <iostream>
#include <vector>
#include <algorithm>

std::vector<int> getStrongest(std::vector<int>& arr, int k) {
    std::sort(arr.begin(), arr.end());
    int median = arr[(arr.size() - 1) / 2];
    int left = 0, right = arr.size() - 1;
    std::vector<int> result;
    while (result.size() < k) {
        if (abs(arr[right] - median) >= abs(arr[left] - median)) {
            result.push_back(arr[right--]);
        } else {
            result.push_back(arr[left++]);
        }
    }
    return result;
}

int main() {
    std::vector<int> arr = {1, 2, 3, 4, 5};
    int k = 2;
    std::vector<int> result = getStrongest(arr, k);
    for (int num : result) {
        std::cout << num << ' ';
    }
    return 0;
}

JavaScript

function getStrongest(arr, k) {
    arr.sort((a, b) => a - b);
    const median = arr[Math.floor((arr.length - 1) / 2)];
    const result = [];
    let left = 0, right = arr.length - 1;
    while (result.length < k) {
        if (Math.abs(arr[right] - median) >= Math.abs(arr[left] - median)) {
            result.push(arr[right--]);
        } else {
            result.push(arr[left++]);
        }
    }
    return result;
}

const arr = [1, 2, 3, 4, 5];
const k = 2;
const result = getStrongest(arr, k);
console.log(result);

#include <stdio.h>
#include <stdlib.h>

int compare_ints(const void * a, const void * b) {
    return *(int*)a - *(int*)b;
}

void strongestValues(int* arr, int arrSize, int k, int* returnArray) {
    qsort(arr, arrSize, sizeof(int), compare_ints);
    int median = arr[(arrSize - 1) / 2];
    int left = 0, right = arrSize - 1;
    for (int i = 0; i < k; ++i) {
        if (abs(arr[right] - median) >= abs(arr[left] - median)) {
            returnArray[i] = arr[right--];
        } else {
            returnArray[i] = arr[left++];
        }
    }
}

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int k = 2;
    int result[2];
    strongestValues(arr, 5, k, result);
    printf("[%d, %d]\n", result[0], result[1]);
    return 0;
}

using System;
using System.Linq;

public class StrongestValues {
    public static int[] GetStrongest(int[] arr, int k) {
        Array.Sort(arr);
        int median = arr[(arr.Length - 1) / 2];
        int left = 0, right = arr.Length - 1;
        int[] result = new int[k];
        int index = 0;
        while (index < k) {
            if (Math.Abs(arr[right] - median) >= Math.Abs(arr[left] - median)) {
                result[index++] = arr[right--];
            } else {
                result[index++] = arr[left++];
            }
        }
        return result;
    }

    public static void Main() {
        int[] arr = {1, 2, 3, 4, 5};
        int k = 2;
        int[] result = GetStrongest(arr, k);
        Console.WriteLine(string.Join(", ", result));
    }
}

In this Python solution, a two-pointer method is used after sorting to efficiently find the strongest k elements by comparing elements from the outer indices towards the center.

Complexity

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

Space Complexity: O(1) when considering result space not included.

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.

TypeScript

function getStrongest(arr: number[], k: number): number[] {
    arr.sort((a, b) => a - b);
    const m = arr[(arr.length - 1) >> 1];
    return arr.sort((a, b) => Math.abs(b - m) - Math.abs(a - m) || b - a).slice(0, k);
}

func getStrongest(arr []int, k int) []int {
	sort.Ints(arr)
	m := arr[(len(arr)-1)>>1]
	sort.Slice(arr, func(i, j int) bool {
		x, y := abs(arr[i]-m), abs(arr[j]-m)
		if x == y {
			return arr[i] > arr[j]
		}
		return x > y
	})
	return arr[:k]
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Sort and Custom Sort	Time Complexity: O(n log n) primarily due to the sorting operations involved. Space Complexity: O(n), mainly due to the internal workings of Python's sorting algorithm which might duplicate the list.
Two Pointers Technique	Time Complexity: O(n log n) due to sorting. Space Complexity: O(1) when considering result space not included.
Sorting	–

Approach

Complexity

Sort and Custom Sort

Time Complexity: O(n log n) primarily due to the sorting operations involved.

Space Complexity: O(n), mainly due to the internal workings of Python's sorting algorithm which might duplicate the list.

Two Pointers Technique

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

Space Complexity: O(1) when considering result space not included.

Sorting

–

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

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.

The k Strongest Values in an Array solution and explanation

The problem

Approach overview

Approach 1: Sort and Custom Sort

Approach 2: Two Pointers Technique

Approach 3: Sorting

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

The k Strongest Values in an Array solution and explanation

The problem

Approach overview

Approach 1: Sort and Custom Sort

Approach 2: Two Pointers Technique

Approach 3: Sorting

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems