C++/Java/Python Two Pointers + 3 Bonuses
My initial solution during the contest was to sort the array to figure out the median, and then sort the array again based on the abs(arr[i] - median) criteria.
My initial solution during the contest was to sort the array to figure out the `median`, and then sort the array again based on the `abs(arr[i] - median)` criteria.\n\nThen I noticed that we have smallest and largest elements in the array in the result. That makes sense based on the problem definition. So, instead of sorting the array again, we can use the two pointers pattern to enumerate smallest and largest numbers, picking the largest `abs(a[i] - median)` each time.\n\nThe code above has one trick: we check that `a[i] > a[j]` first. This way, if `a[i] == a[j]`, we pick the element from the right side, which is largest because the array is sorted!\n\n> Update: check bonus sections below for O(n log k), O(n + k log n), and O(n) solutions.\n\n**C++**\n```cpp\nvector<int> getStrongest(vector<int>& arr, int k) {\n    sort(begin(arr), end(arr));\n    int i = 0, j = arr.size() - 1;\n    int med = arr[(arr.size() - 1) / 2];\n    while (--k >= 0)\n        if (med - arr[i] > arr[j] - med)\n            ++i;  \n        else\n            --j;\n    arr.erase(begin(arr) + i, begin(arr) + j + 1);\n    return arr;\n}\n```\n**Java**\n```java\npublic int[] getStrongest(int[] arr, int k) {\n    Arrays.sort(arr);\n    int i = 0, j = arr.length - 1, p = 0;\n    int median = arr[(arr.length - 1) / 2];\n    int[] res = new int[k];\n    while (p < k)\n        if (median - arr[i] > arr[j] - median)\n            res[p++] = arr[i++];  \n        else\n            res[p++] = arr[j--];      \n    return res;\n}\n```\n**Python**\n```python\nclass Solution:\n    def getStrongest(self, arr: List[int], k: int) -> List[int]:\n        arr.sort()\n        i, j = 0, len(arr) - 1\n        median = arr[(len(arr) - 1) // 2]\n        while len(arr) + i - j <= k:\n            if median - arr[i] > arr[j] - median:\n                i = i + 1\n            else:\n                j = j - 1\n        return arr[:i] + arr[j + 1:]\n```\n**Complexity Analysis**\n- Time: O(n log n) for the sorting.\n- Memory: only what\'s needed for the sorting (implementation-specific), and output.\n\n#### Bonus 1: O(n log k)\nWe can find a median in O(n) average complexity by using quick select. Then, we insert all elements in a sorted set, limiting the set size to `k`. Even better, we can use a partial sort algorithm that will move `k` strongest values to the front of the array.\n\n```cpp\nvector<int> getStrongest(vector<int>& arr, int k) {\n    nth_element(begin(arr), begin(arr) + (arr.size() - 1) / 2, end(arr));\n    int m = arr[(arr.size() -1) / 2];\n    partial_sort(begin(arr), begin(arr) + k, end(arr), [&](int a, int b) { \n        return abs(a - m) == abs(b - m) ? a > b : abs(a - m) > abs(b - m); \n    });\n    arr.resize(k);\n    return arr;\n}\n```\n#### Bonus 2: O(n + k log n)\nSimilar to the first bonus, but using a max heap. Why this is O(n + k log n):\n- `nth_element` is quick select, which is O(n);\n- `priority_queue` initialized with array is heapify, which is also O(n);\n- Pulling from priority queue is O(log n), and we do it `k` times.\n\n```cpp\nvector<int> getStrongest(vector<int>& arr, int k) {\n    nth_element(begin(arr), begin(arr) + (arr.size() - 1) / 2, end(arr));\n    int m = arr[(arr.size() -1) / 2];\n    auto cmp = [&](int a, int b) { \n        return abs(a - m) == abs(b - m) ? a < b : abs(a - m) < abs(b - m); \n    };\n    priority_queue<int, vector<int>, decltype(cmp)> pq(begin(arr), end(arr), cmp);\n    vector<int> res;\n    while (res.size() < k) {\n        res.push_back(pq.top());\n        pq.pop();\n    }\n    return res;\n}\n```\n#### Bonus 3: O(n)\nThe order in output does not need to be sorted. So, after we find our median, we can do another quick select to move k strongest elements to the beginning of the array.\n> Note: quickselect has O(n) average time complexity, and O(n ^ 2) worst time complexity. It can be improved to O(n) worst time complexity using the median of medians approach to find a pivot. In practice though, a simpler randomization version is faster than median of medians, as the latter requires an extra O(n) scan to find a pivot.\n\n```cpp\nvector<int> getStrongest(vector<int>& arr, int k) {\n    nth_element(begin(arr), begin(arr) + (arr.size() - 1) / 2, end(arr));\n    int m = arr[(arr.size() -1) / 2];\n    nth_element(begin(arr), begin(arr) + k, end(arr), [&](int a, int b) { \n        return abs(a - m) == abs(b - m) ? a > b : abs(a - m) > abs(b - m); \n    });\n    arr.resize(k);\n    return arr;\n}\n```
[]