Skip to content

1471. The k Strongest Values in an Array 👍

Approach 1: Naive

  • Time: $O(\texttt{sort})$
  • Space: $O(k)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
 public:
  vector<int> getStrongest(vector<int>& arr, int k) {
    ranges::sort(arr);

    const int n = arr.size();
    const int median = arr[(n - 1) / 2];
    vector<int> ans;

    for (int l = 0, r = n - 1; k > 0; --k)
      if (median - arr[l] > arr[r] - median)
        ans.push_back(arr[l++]);
      else
        ans.push_back(arr[r--]);

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
  public int[] getStrongest(int[] arr, int k) {
    Arrays.sort(arr);

    final int n = arr.length;
    final int median = arr[(n - 1) / 2];
    int[] ans = new int[k];

    for (int i = 0, l = 0, r = n - 1; i < k; ++i)
      if (median - arr[l] > arr[r] - median)
        ans[i] = arr[l++];
      else
        ans[i] = arr[r--];

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
  def getStrongest(self, arr: list[int], k: int) -> list[int]:
    arr.sort()

    ans = []
    median = arr[(len(arr) - 1) // 2]
    l = 0
    r = len(arr) - 1

    for _ in range(k):
      if median - arr[l] > arr[r] - median:
        ans.append(arr[l])
        l -= 1
      else:
        ans.append(arr[r])
        r += 1

    return ans

Approach 2: Heuristic

  • Time: $O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
 public:
  vector<int> getStrongest(vector<int>& arr, int k) {
    const int midIndex = (arr.size() - 1) / 2;
    nth_element(arr.begin(), arr.begin() + midIndex, arr.end());
    const int median = arr[midIndex];

    nth_element(arr.begin(), arr.begin() + k, arr.end(), [&](int a, int b) {
      const int da = abs(a - median);
      const int db = abs(b - median);
      return da == db ? a > b : da > db;
    });

    arr.resize(k);
    return arr;
  }
};