Problem Description

Given an array of integers arr and an integer k, you are to find the k strongest values in the array according to the following definition of strength:

• First, find the median value m of the array arr. If the array has an odd length, m is the middle element after sorting. If even, m is the element at index (n-1)//2 after sorting, where n is the array's length.
• The strength of a value x is defined as |x - m|. If two values have the same strength, the larger value is considered stronger.
• You should return an array of the k strongest values, in any order.

Constraints:

• 1 ≤ arr.length ≤ 10⁵
• 1 ≤ arr[i] ≤ 10⁵
• 1 ≤ k ≤ arr.length

Thought Process

At first glance, it may seem like we need to compute the strength for every element and then pick the top k strongest. A brute-force approach would be to:

• Sort the array to find the median.
• For each element, compute its strength.
• Sort all elements by their strength (and value for ties).
• Take the first k elements.

However, since sorting and recomputing strengths could be expensive for large arrays, we look for optimizations. Notably, since strength depends on the median, and sorting is required for finding the median anyway, we can reuse this sorted order to efficiently select the strongest values.

Using two pointers (one from each end of the sorted array), we can always pick the stronger of the two candidates at each step. This leverages the fact that values farthest from the median are at the ends of the sorted array.

Solution Approach

• Step 1: Sort the array.
  Sorting is necessary to find the median and to efficiently pick strongest values.
• Step 2: Find the median.
  For an array of length n, the median is at index (n-1)//2 in the sorted array.
• Step 3: Use two pointers to select strongest values.
  Initialize two pointers, left at the start and right at the end of the array. At each step:
  • Compare the strength of arr[left] and arr[right] (i.e., |arr[left] - m| vs |arr[right] - m|).
  • If the right value is stronger (or equal but larger), pick arr[right] and decrement right.
  • Otherwise, pick arr[left] and increment left.
  • Repeat until k elements are picked.
• Step 4: Return the result.
  The collected values are the k strongest, as defined.

This approach is efficient because it avoids sorting the entire array by strength, and instead picks strongest values directly using the sorted order.

Example Walkthrough

Let's walk through an example with arr = [1, 2, 3, 4, 5] and k = 2.

1. Sort the array: [1, 2, 3, 4, 5]
2. Find the median:
   Array length is 5, so median index is (5-1)//2 = 2.
   Thus, m = 3.
3. Use two pointers:
   • left = 0 (arr[0] = 1), right = 4 (arr[4] = 5)
   • Strengths: |1-3|=2, |5-3|=2. Both have same strength, but 5 is larger, so pick 5. right--
   • Result: [5]
   • left = 0, right = 3 (arr[3] = 4)
   • Strengths: |1-3|=2, |4-3|=1. 1 is stronger, so pick 1. left++
   • Result: [5, 1]
4. Return: [5, 1] (order doesn't matter)

Time and Space Complexity

• Brute-Force Approach:
  • Sorting the array: O(n log n)
  • Computing strength for each element: O(n)
  • Sorting by strength: O(n log n)
  • Total: O(n log n)
• Optimized Approach (Two Pointers):
  • Sorting the array: O(n log n)
  • Two-pointer selection: O(k)
  • Total: O(n log n)
  • Space: O(n) for the sorted array and result
• The bottleneck is the sorting step. The two-pointer selection is efficient and does not dominate the overall complexity.

Summary

The key insight is that, after sorting, the strongest elements (those farthest from the median) are at the ends of the array. By using two pointers, we can efficiently select the k strongest values without the need for an additional sort by strength. This makes the solution both elegant and efficient, with time complexity dominated by the initial sort.

Code Implementation

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

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

import java.util.*;

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

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