Learn randomized algorithm today which solves this problem in O(n).
Two Approaches: O(nlogn) and O(n) - Sort and Randomized Algorithm\n\nThe problem is not complex to find the solution of but it can get complex in implementation
**Two Approaches: O(nlogn) and O(n) - Sort and Randomized Algorithm**\n\nThe problem is not complex to find the solution of but it can get complex in implementation. Basically you want to find the median of the array and then find k values that result in the maximum value for the requested operation.\n\n**A Straightforward way - Sorting**\nSort the array.\nGet the median i.e. ((n-1)/2)th element.\nCreate a new array where each element, new_arr[i] = abs(original_arr[i] -median)\nSort the new array.\nReturn the highest k values.\n\nThe tricky part is to handle the scenarios when values in new_array are the same. You then want to sort based the original array value. For this, you might have to write a custom comparison method depending on the programming language.\n\nIf you sort the entire array, then time complexity is O(nlogn).\nHence the time complexity of this solution is O(nlogn).\n\n```\nint median;\nstruct compare {\n    bool operator()(const int &a, const int &b) {\n        return (abs(a-median) > abs(b-median)) || (abs(a-median) == abs(b-median) && a>b);\n    }\n} compare;\n\nclass Solution {\npublic:    \n    vector<int> getStrongest(vector<int>& arr, int k) {\n        sort(arr.begin(), arr.end());                   // Sort first to find the median.\n        median = arr[(arr.size()-1)/2];                 // Find median.\n        sort(arr.begin(), arr.end(), compare);          // Sort again based on a specific way.\n        return vector<int>(arr.begin(), arr.begin()+k); // Return the answer.\n    }\n};\n```\n\n\n**B. Advanced way - Randomized Algorithms**\nYou don\u2019t have to sort the entire array. There are only 2 things of interest.\nThe median. So you want `((n-1)/2)`th number in the array. There is a randomized algorithm that can give the result in O(n) time. (Basically how quicksort sorts the array by choosing a pivot element).\nThe strongest k values. An important thing to note here is that the order of those values is not important. The question states that any order is fine. So the same randomized algorithm helps here too.\n\nTime complexity: O(n).\n\n\nIn C++, the method is nth_element for arranging first k-1 elements to be smaller than kth element & remaining elements at the end. Other languages must also have something similar.\nWhat is the way in your language? I would be curious to know, put that in comments.\n\n**Thanks**\nPlease upvote if you found this helpful.\n\n```\nint median;\nstruct compare {\n    bool operator()(const int &a, const int &b) {\n        return (abs(a-median) > abs(b-median)) || (abs(a-median) == abs(b-median) && a>b);\n    }\n} compare;\n\nclass Solution {\npublic:    \n    vector<int> getStrongest(vector<int>& arr, int k) {\n        nth_element(arr.begin(), arr.begin()+(arr.size()-1)/2, arr.end());  // Just find median element correctly.\n        median = arr[(arr.size()-1)/2];                                                             // Get median.\n        nth_element(arr.begin(), arr.begin()+k, arr.end(), compare);             // Sort just enough that k strongest are at the beginning.\n        return vector<int>(arr.begin(), arr.begin()+k);                                   // Return the answer.\n    }\n};\n```\n\n\n**How Randomized Median Find Work**\n\n1. It choses an element as pivot.\n2. Shuffles the array so that all elements to the left of it are smaller than itself while the ones on the right are greater.\n3. If that element turns out to be at the index \'k\' that we pass as a parameter,  the algorithm stops. At this time - we have the array with `k`-th element at correct place (the place had the array been sorted.) AND we have smaller elements on left side and larger on right. This is exactly what helps us here for solving this problem.\n4. If the element is not at `k` we decide which part (left or right) to go into to get to the kth element.\n\nAdditional Info on ref: https://en.wikipedia.org/wiki/Partial_sorting
[]