# The k Strongest Values in an Array
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/the-k-strongest-values-in-an-array)
Canonical: https://scaleengineer.com/dsa/problems/the-k-strongest-values-in-an-array
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
---
## Problem
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 **centre** 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**.

The **centre** is the middle value in an ordered integer list. More formally, if the length of the list is n, the centre 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 centre is obtained by sorting the array `arr = [-3, 2, 6, 7, 11]` and the centre is `arr[m]` where `m = ((5 - 1) / 2) = 2`. The centre is `6`.
* For `arr = [-7, 22, 17, 3]`, `n = 4` and the centre is obtained by sorting the array `arr = [-7, 3, 17, 22]` and the centre is `arr[m]` where `m = ((4 - 1) / 2) = 1`. The centre is `3`.

**Example 1:**

**Input:** arr = [1,2,3,4,5], k = 2
**Output:** [5,1]
**Explanation:** Centre 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:** Centre 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:** Centre 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`

# Approaches
## Full Sort with Custom Comparator
This is a straightforward approach where we first determine the median of the array by sorting it. Then, we perform another sort on the entire array, this time using a custom comparison logic based on the definition of "strength". The strongest `k` values are simply the first `k` elements of this newly sorted array.
**Time:** O(N log N). Sorting to find the median is `O(N log N)`. The custom sort on `N` elements is also `O(N log N)`. The total time is dominated by these sorting steps. · **Space:** O(N). We need an auxiliary array of `Integer` objects of size `N` to perform the custom sort, as Java's `Arrays.sort` with a `Comparator` requires an object array.
**Pros:** Conceptually simple and easy to implement using standard library sorting functions.
**Cons:** Inefficient in both time and space.; It sorts the entire array of N elements based on strength, which is more work than necessary.; Requires O(N) extra space for the wrapper `Integer` array.
### Explanation
The algorithm proceeds as follows:
1.  First, sort the array `arr` to find the median. The median `m` is the element at index `(n-1)/2`.
2.  To use a custom comparator with `Arrays.sort`, we convert the primitive `int[]` to an `Integer[]`.
3.  Sort the `Integer` array using a custom `Comparator`. This comparator implements the strength logic:
    -   For any two numbers `a` and `b`, it compares `|a - m|` and `|b - m|`.
    -   The sort is in descending order of strength.
    -   If the strengths are equal, it sorts in descending order of the numbers' values (`a` vs `b`).
4.  Finally, create a result array and copy the first `k` elements from the custom-sorted array.

```java
import java.util.Arrays;
import java.util.Collections;

class Solution {
    public int[] getStrongest(int[] arr, int k) {
        int n = arr.length;
        Arrays.sort(arr);
        final int median = arr[(n - 1) / 2];

        // Convert to Integer array for custom sorting
        Integer[] integerArr = new Integer[n];
        for (int i = 0; i < n; i++) {
            integerArr[i] = arr[i];
        }

        // Custom sort based on strength
        Arrays.sort(integerArr, (a, b) -> {
            int strengthA = Math.abs(a - median);
            int strengthB = Math.abs(b - median);
            if (strengthA != strengthB) {
                return Integer.compare(strengthB, strengthA); // Descending strength
            } else {
                return Integer.compare(b, a); // Descending value
            }
        });

        // Get the first k elements
        int[] result = new int[k];
        for (int i = 0; i < k; i++) {
            result[i] = integerArr[i];
        }
        return result;
    }
}
```
### Algorithm
- Sort the array `arr` to find the median `m`.
- Convert `arr` to an `Integer[]` to allow for custom sorting.
- Sort the `Integer[]` using a custom comparator based on strength. The strongest elements will come first.
- Take the first `k` elements from the sorted array.

## Sort and Use a Min-Heap
This approach improves on the previous one by avoiding a full second sort. After finding the median via an initial sort, it uses a min-heap data structure to keep track of the `k` strongest elements encountered so far. This is a classic "Top K" algorithm pattern.
**Time:** O(N log N). The initial sort takes `O(N log N)`. Iterating through `N` elements with heap operations takes `O(N log k)`. The total complexity is dominated by the initial sort. · **Space:** O(k). The min-heap stores at most `k+1` elements. The in-place sort for primitives uses `O(log N)` stack space.
**Pros:** More space-efficient than the full sort approach.; A standard and robust pattern for "Top K" problems.
**Cons:** The overall time complexity is still bottlenecked by the `O(N log N)` sort to find the median.; Slightly more complex to implement than the two-pointer approach due to the heap and custom comparator.
### Explanation
The algorithm is as follows:
1.  Sort the array `arr` to find the median `m`.
2.  Initialize a min-priority queue (min-heap) with a custom comparator. The comparator orders elements by their strength in *ascending* order, so the weakest of the `k` strongest elements is always at the top of the heap.
3.  Iterate through each number `num` in the array `arr`.
4.  For each `num`, add it to the heap.
5.  If the heap's size grows larger than `k`, remove the top element (`poll()`). This ensures the heap only contains the `k` strongest elements seen so far.
6.  After iterating through the entire array, the heap holds the `k` strongest values. Extract them to form the result.

```java
import java.util.Arrays;
import java.util.PriorityQueue;

class Solution {
    public int[] getStrongest(int[] arr, int k) {
        int n = arr.length;
        Arrays.sort(arr);
        final int median = arr[(n - 1) / 2];

        // Min-heap to store the k strongest elements
        // The comparator for a min-heap is the reverse of the strength definition
        PriorityQueue<Integer> minHeap = new PriorityQueue<>((a, b) -> {
            int strengthA = Math.abs(a - median);
            int strengthB = Math.abs(b - median);
            if (strengthA != strengthB) {
                return Integer.compare(strengthA, strengthB); // Ascending strength
            } else {
                return Integer.compare(a, b); // Ascending value
            }
        });

        for (int num : arr) {
            minHeap.offer(num);
            if (minHeap.size() > k) {
                minHeap.poll();
            }
        }

        int[] result = new int[k];
        for (int i = 0; i < k; i++) {
            result[i] = minHeap.poll();
        }
        return result;
    }
}
```
### Algorithm
- Sort `arr` to find the median `m`.
- Create a min-heap of size `k` with a custom comparator for "weakness" (the reverse of the strength definition).
- Iterate through `arr`, adding each element to the heap.
- If the heap size exceeds `k`, remove the minimum (weakest) element from the top.
- After the loop, the final heap contains the `k` strongest elements.

## Sort and Use Two Pointers
This is a highly efficient approach that leverages the properties of a sorted array. After sorting, the strongest elements (those furthest from the median) will be located at the two ends of the array. We can use two pointers, one at the beginning and one at the end, to greedily pick the `k` strongest elements in linear time relative to `k` after the initial sort.
**Time:** O(N log N). The `Arrays.sort` call takes `O(N log N)`. The two-pointer traversal to find the `k` strongest elements takes `O(k)`. The total time is dominated by sorting. · **Space:** O(k) or O(log N). `O(k)` is required for the result array. The space for sorting depends on the implementation; in Java, `Arrays.sort` for primitives is in-place and uses `O(log N)` stack space.
**Pros:** Optimal time complexity given the need to sort.; Very efficient in terms of space and has low constant factors compared to other approaches.; The logic is clean, intuitive, and easy to implement.
**Cons:** The `O(N log N)` sorting step is the performance bottleneck. While optimal for this strategy, a different strategy using a linear-time median-finding algorithm (like Quickselect) could be asymptotically faster.
### Explanation
The algorithm works as follows:
1.  Sort the array `arr` in non-decreasing order.
2.  Identify the median `m = arr[(n - 1) / 2]`.
3.  Initialize two pointers, `left = 0` and `right = n - 1`, and a result array of size `k`.
4.  Iterate `k` times to fill the result array. In each step:
    -   Compare the strength of `arr[left]` and `arr[right]`. Strength is `|value - m|`.
    -   The element with the higher strength is added to the result.
    -   If strengths are equal, the one with the larger value is stronger. Since `arr[right] >= arr[left]`, `arr[right]` is chosen in a tie.
    -   Move the pointer (`left`++ or `right`--) corresponding to the element that was chosen.
5.  Return the result array.

```java
import java.util.Arrays;

class Solution {
    public int[] getStrongest(int[] arr, int k) {
        int n = arr.length;
        Arrays.sort(arr);
        int median = arr[(n - 1) / 2];

        int[] result = new int[k];
        int left = 0;
        int right = n - 1;
        int resultIndex = 0;

        while (resultIndex < k) {
            if (Math.abs(arr[left] - median) > Math.abs(arr[right] - median)) {
                result[resultIndex++] = arr[left++];
            } else {
                // If strengths are equal, arr[right] is chosen because it's the larger value.
                // If right's strength is greater, it's also chosen.
                result[resultIndex++] = arr[right--];
            }
        }
        return result;
    }
}
```
### Algorithm
- Sort the array `arr`.
- Find the median `m`.
- Initialize two pointers, `left` at the start and `right` at the end of the array.
- In a loop that runs `k` times, compare the strength of `arr[left]` and `arr[right]`.
- Add the stronger element to the result and move the corresponding pointer inward.
- Handle ties by picking the larger value, which will always be `arr[right]`.

# Solutions
### Java

```java
class Solution {
public
  int[] getStrongest(int[] arr, int k) {
    Arrays.sort(arr);
    int m = arr[(arr.length - 1) >> 1];
    List<Integer> nums = new ArrayList<>();
    for (int v : arr) {
      nums.add(v);
    }
    nums.sort((a, b)->{
      int x = Math.abs(a - m);
      int y = Math.abs(b - m);
      return x == y ? b - a : y - x;
    });
    int[] ans = new int[k];
    for (int i = 0; i < k; ++i) {
      ans[i] = nums.get(i);
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> getStrongest(vector<int> &arr, int k) {
    sort(arr.begin(), arr.end());
    int m = arr[(arr.size() - 1) >> 1];
    sort(arr.begin(), arr.end(), [&](int a, int b) {
      int x = abs(a - m), y = abs(b - m);
      return x == y ? a > b : x > y;
    });
    vector<int> ans(arr.begin(), arr.begin() + k);
    return ans;
  }
};

```

### Python

```python
class Solution:
    def getStrongest(self, arr: List[int], k: int) -> List[int]: arr . sort() m = arr[(len(arr) - 1) >> 1] arr . sort(key=lambda x: (- abs(x - m), - x)) return arr[: k]

```