Leetcode 1471: The k Strongest Values in an Array

In this Leetcode problem, we are given an array arr and an integer k, we want to figure out what are the k values v in the array such that |v — m| is maximum with m the median value in the array.

Problem statement

Solution

A simple way to resolve is if to first think about sorting the array. Indeed, it seems much easier to solve the problem once the array is sorted. There could be more efficient method relying a count sort or bucketing to find the median and find the k strongest values, but I took a simpler approach.

1. Sort the array
2. Set med = arr[(n-1) / 2];
3. Keep 2 pointers low and high. They should point to the index of next potential strongest values. At the start, low = 0, and high = n — 1 point to the only 2 values that can be the strongest.
4. At each iteration, find which of arr[low] or arr[high] is the strongest, if arr[low] is the strongest, move low to the next value low + 1, if arr[high] is the strongest, move high to the next value high — 1. Do that k times until the array res is full.

class Solution {
    public int[] getStrongest(int[] arr, int k) {
        Arrays.sort(arr);
        int n = arr.length;
        int med = arr[(n-1) / 2];
        int[] res = new int[k];
        int low = 0;
        int high = n …