# 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 getStrongest(vector& arr, int k) { sort(arr.begin(), arr.end()); const int n = arr.size(); const int median = arr[(n - 1) / 2]; vector 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