Given an integer array `arr` and an integer `k`, the goal is to identify the `k` strongest values. The strength of an element is determined by its absolute difference from the array's median.
Let `m` be the median of the array. An element `arr[i]` is considered stronger than `arr[j]` if either condition is met:
- `|arr[i] - m| > |arr[j] - m|`
- `|arr[i] - m| == |arr[j] - m|` and `arr[i] > arr[j]`
The median is defined as the element at the middle index of a sorted list. For a list of length `n`, the median is the element at index `(n - 1) / 2`.
Approach 1: Sorting and Two Pointers
An efficient strategy involves sorting the array first to locate the median. Once sorted, the strongest elements are guaranteed to be at the extremes of the array (either the smallest or largest values relative to the median). This allows us to use a two-pointer technique to select the top `k` elements without sorting the entire array again based on strength criteria.
The algorithm proceeds as follows:
- Sort the input array `arr` in ascending order.
- Calculate the median index as `(arr.length - 1) >> 1`.
- Initialize two pointers: `left` at the start (index 0) and `right` at the end (index `arr.length - 1`).
- Initialize an empty result array.
- Repeat `k` times:
- Calculate the absolute difference of the element at `left` from the median (`diffLeft`).
- Calculate the absolute difference of the element at `right` from the median (`diffRight`).
- If `diffLeft` is greater than `diffRight`, the left element is stronger. Add it to the result and increment `left`.
- If `diffRight` is greater than or equal to `diffLeft`, the right element is stronger (or equally strong but larger). Add it to the result and decrement `right`.
- Return the result array.
This approach runs in O(n log n) time due to the initial sorting step, which is optimal for this problem, and uses O(n) space for the result (or O(1) if modifying the array in-place).
/**
* @param {number[]} data
* @param {number} k
* @return {number[]}
*/
var findStrongest = function(data, k) {
// Step 1: Sort the array to easily find the median
data.sort((x, y) => x - y);
const n = data.length;
// Step 2: Identify the median value
const medianIndex = Math.floor((n - 1) / 2);
const medianValue = data[medianIndex];
// Step 3: Initialize pointers and result array
let low = 0;
let high = n - 1;
const strongestElements = [];
// Step 4: Select k strongest elements
while (k > 0) {
const distLow = Math.abs(data[low] - medianValue);
const distHigh = Math.abs(data[high] - medianValue);
if (distLow > distHigh) {
// The smallest element is "stronger" (farther from median)
strongestElements.push(data[low]);
low++;
} else {
// The largest element is "stronger" (or ties and is larger)
strongestElements.push(data[high]);
high--;
}
k--;
}
return strongestElements;
};Approach 2: Custom Sorting (Brute Force)
While the two-pointer method is preferred for its efficiency, a naive approach involves sorting the array based entirely on the strength criteria. This requires computing the median first, then applying a custom comparator to the sort function.
Note that in JavaScript, the comparator function for `Array.prototype.sort()` should return a number (negative, zero, or positive) rather than a boolean to ensure consistent behavior across different engines. Comparators expecting boolean logic (like `true`/`false`) may lead to incorrect sorting or performance issues.
/**
* @param {number[]} data
* @param {number} k
* @return {number[]}
*/
var findStrongestBySorting = function(data, k) {
// Initial sort to find median
data.sort((x, y) => x - y);
const medianVal = data[Math.floor((data.length - 1) / 2)];
// Custom sort based on strength rules
data.sort((x, y) => {
const diffX = Math.abs(x - medianVal);
const diffY = Math.abs(y - medianVal);
if (diffX === diffY) {
// Tie-breaker: larger value is stronger
return y - x;
}
// Larger distance is stronger
return diffY - diffX;
});
// Return the first k elements
return data.slice(0, k);
};This method sorts the array twice, resulting in a higher computational cost compared to the two-pointer strategy. However, it is conceptually simpler and directly implements the problem's definition of "stronger".