Leetcode 1471. The k Strongest Values in an Array

Problem Explanation

In this problem, we are asked to find the strongest k values in an array. To find the strongest value, we first need to compute the median. The median is the middle number in a sorted list, if the list length is odd. Alternatively, it is the average of the two middle numbers if the list length is even.

If the absolute difference between an element arr[i] and the median is greater than the absolute difference between another element arr[j] and the median, we consider arr[i] to be stronger than arr[j]. If the absolute differences are equal, the element with the larger numerical value is considered stronger.

For instance, arr = [1,2,3,4,5], k = 2, the median value is 3. The strongest values are 5 and 1 because the absolute differences |5-3| and |1-3| are both 2. Between 5 and 1, 5 has a larger numerical value and is therefore stronger.

Solution Approach

The first step in the solution is to sort the array. After sorting the array, we can calculate the median of the array. The median is found in the ((n - 1) / 2) position of the sorted array.

The solution then uses two pointers l and r. l is set at the start of the array and r is set at the end. We then check whether |arr[l]-median| > |arr[r]-median|. If arr[l] is closer to the median, arr[l] is added to the answer and we move l one step forward. If arr[r] is closer to the median, arr[r] is added to the answer and we move r one step back. If they are equal, we choose arr[r] because it has the bigger value. We stop this process once we have chosen k number of array elements to be in our answer.

For example, given arr = [6,7,11,7,6,8], k = 5, after sorting, arr becomes [6, 6, 7, 7, 8, 11]. The median is 7. We find the strongest k elements [11, 8, 6, 6, 7] by applying the process as discussed.

Solutions

C++ solution

1
2cpp
3class Solution {
4public:
5    vector<int> getStrongest(vector<int>& arr, int k) {
6        sort(arr.begin(), arr.end());
7        int n = arr.size();
8        int median = arr[(n - 1) / 2];
9        vector<int> ans;
10
11        for (int l = 0, r = n - 1; k > 0; --k)
12            if (median - arr[l] > arr[r] - median)
13                ans.push_back(arr[l++]);
14            else
15                ans.push_back(arr[r--]);
16
17        return ans;
18    }
19};

Python solution

1
2python
3class Solution:
4    def getStrongest(self, arr: List[int], k: int) -> List[int]:
5        arr.sort()
6        median = arr[(len(arr) - 1) // 2]
7        ans = sorted(arr, key= lambda x: (abs(x - median), x), reverse=True)
8        return ans[:k]

Java solution

1
2java
3class Solution {
4    public int[] getStrongest(int[] arr, int k) {
5        Arrays.sort(arr);
6        int median = arr[(arr.length - 1) / 2];
7        int l = 0, r = arr.length - 1;
8        int[] ans = new int[k];
9        for(int i = 0; i < k; i++){
10            if (median - arr[l] > arr[r] - median){
11                ans[i] = arr[l++];
12            } else {
13                ans[i] = arr[r--];
14            }
15        }
16        return ans;
17    }
18}

JavaScript solution

1
2js
3var getStrongest = function(arr, k) {
4    arr.sort((a, b) => a - b);
5    let median = arr[Math.floor((arr.length - 1) / 2)];
6
7    return arr.sort((a, b) => {
8        let diffA = Math.abs(a - median);
9        let diffB = Math.abs(b - median);
10        if (diffA === diffB) {
11            return b - a;
12        }
13
14        return diffB - diffA;
15    }).splice(0, k);
16};

C# solution

1
2csharp
3public class Solution {
4    public int[] GetStrongest(int[] arr, int k) {
5        Array.Sort(arr);
6        int median = arr[(arr.Length - 1) / 2];
7        int[] ans = new int[k];
8        int l = 0, r = arr.Length - 1;
9        for(int i = 0; i < k; i++){
10            if (median - arr[l] > arr[r] - median){
11                ans[i] = arr[l++];
12            } else {
13                ans[i] = arr[r--];
14            }
15        }
16        return ans;
17    }
18}

Explanation of the code

In the code now, we begin by sorting the array and calculating the median. We then use the two-pointer method as discussed to identify the strongest k values. If the lefthand value (arr[l]) is more distant from the median, we add arr[l] to our result and move the left pointer forward. If the righthand value (arr[r]) is more or equally distant, we add arr[r] and move the right pointer backwards. This process will select the 'strongest' values in the array.In the Python solution, we are using Python’s built-in sort and list slicing to solve the problem in a more pythonic way. After sorting the array, we sort it again using a custom sort function that ranks the numbers first by their distance from the median, and then by their absolute value. We then return the first k elements from this sorted list.

The Java solution follows the two-pointer method explained earlier. We first sort the array and calculate the median. Then, we use two pointers, l and r, to point to the left and right ends of the array. We then compare the distance from the median of the numbers pointed to by l and r. If the number at l is farther from the median, it is considered stronger and added to our answer array. Otherwise, the number at r is added. This comparison is repeated for k times to get the first k strongest numbers.

In the JavaScript solution, we start by sorting the array and computing the median. After that, we sort the array again using a custom sort function. In this function, we take the difference between each element and the median. If two elements have the same difference, then the larger number is considered stronger and is sorted before the smaller number. Finally, we return the first k elements of the sorted array to get our answer.

In the C# solution, it sorts the given array and calculates the median in the same way. Using a for loop, it adds the stronger number which is calculated by the same concept we have already known to the answer. The obtained array is then returned.

In all these solutions, the most important concept is to calculate the median after sorting and use the property of absolute difference to find out the stronger number. Even though the implementations in these languages are slightly different, the core idea remains the same.