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) {
    sort(arr.begin(), arr.end());

    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