The K Strongest Values In An Array - Leetcode Solution

Problem Statement:

Given an array of integers arr and an integer k. We have to find the k strongest numbers in the array. The k strongest numbers are the k numbers that are the closest to the median of the array, and the absolute difference between the elements and the median is maximum.

Return an array of k strongest integers from arr.

The median is the middle value in the sorted order of a list. If the list has odd length, the middle value is the one in the middle, if it’s even, it’s the average of the two middle values.

Input:

The input consists of three parameters:

1. arr: An array of n integers where 1 ≤ n ≤ 10^5.

2. k: An integer where 1 ≤ k ≤ n.

Output:

The output should be an array of k integers.

Note:

1. The array arr will contain only distinct elements.

2. The output array should be sorted in non-increasing order.

Approach:

1. Sort the array.

2. Now calculate the median of the given array. If the length of the array is odd, the median would be arr[n//2], else the median would be (arr[n//2] + arr[n//2 - 1])/2.

3. Then, iterate the array and calculate the absolute difference between each element of the array and the median. Store the absolute difference along with the element in a list.

4. Sort the list in descending order based on the absolute difference.

5. Select the first k elements from the sorted list.

6. Extract the original elements from the selected elements (exclude the absolute difference).

7. Sort the k elements in decreasing order.

8. Return the array of k strongest integers.

Pseudo code:

def getStrongest(arr: List[int], k: int) -> List[int]: n = len(arr) arr.sort() median = arr[(n - 1) // 2] if n % 2 else (arr[n//2] + arr[n//2 - 1])/2 temp = [] for i in range(n): temp.append((abs(arr[i]-median), arr[i])) temp.sort(reverse=True) result = [] for i in range(k): result.append(temp[i][1]) result.sort(reverse=True) return result

Time complexity:

The time complexity of the algorithm is O(n log n + n) which is dominated by the sorting algorithm.

1