1471. The k Strongest Values in an Array

Medium

593

129

Given an array of integers `arr`

and an integer `k`

.

A value `arr[i]`

is said to be stronger than a value `arr[j]`

if `|arr[i] - m| > |arr[j] - m|`

where `m`

is the **median** of the array.

If `|arr[i] - m| == |arr[j] - m|`

, then `arr[i]`

is said to be stronger than `arr[j]`

if `arr[i] > arr[j]`

.

Return *a list of the strongest k* values in the array. return the answer

**Median** is the middle value in an ordered integer list. More formally, if the length of the list is n, the median is the element in position `((n - 1) / 2)`

in the sorted list **(0-indexed)**.

- For
`arr = [6, -3, 7, 2, 11]`

,`n = 5`

and the median is obtained by sorting the array`arr = [-3, 2, 6, 7, 11]`

and the median is`arr[m]`

where`m = ((5 - 1) / 2) = 2`

. The median is`6`

. - For
`arr = [-7, 22, 17, 3]`

,`n = 4`

and the median is obtained by sorting the array`arr = [-7, 3, 17, 22]`

and the median is`arr[m]`

where`m = ((4 - 1) / 2) = 1`

. The median is`3`

.

**Example 1:**

Input:arr = [1,2,3,4,5], k = 2Output:[5,1]Explanation:Median is 3, the elements of the array sorted by the strongest are [5,1,4,2,3]. The strongest 2 elements are [5, 1]. [1, 5] is alsoacceptedanswer. Please note that although |5 - 3| == |1 - 3| but 5 is stronger than 1 because 5 > 1.

**Example 2:**

Input:arr = [1,1,3,5,5], k = 2Output:[5,5]Explanation:Median is 3, the elements of the array sorted by the strongest are [5,5,1,1,3]. The strongest 2 elements are [5, 5].

**Example 3:**

Input:arr = [6,7,11,7,6,8], k = 5Output:[11,8,6,6,7]Explanation:Median is 7, the elements of the array sorted by the strongest are [11,8,6,6,7,7]. Any permutation of [11,8,6,6,7] isaccepted.

**Constraints:**

`1 <= arr.length <= 10`

^{5}`-10`

^{5}<= arr[i] <= 10^{5}`1 <= k <= arr.length`

Accepted

33.3K

Submissions

55K

Acceptance Rate

60.5%

Seen this question in a real interview before?

1/4

Yes

No

Discussion (0)

Related Topics

Copyright ©️ 2023 LeetCode All rights reserved