The k Strongest Values in an Array

Medium

Asked by:

17 views

Topics:

Arrays

Given an array of integers arr and an integer k.

Return a list of the strongest k values in the array. return the answer in any arbitrary order.

The centre is the middle value in an ordered integer list. More formally, if the length of the list is n, the centre 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 centre is obtained by sorting the array arr = [-3, 2, 6, 7, 11] and the centre is arr[m] where m = ((5 - 1) / 2) = 2. The centre is 6.
For arr = [-7, 22, 17, 3], n = 4 and the centre is obtained by sorting the array arr = [-7, 3, 17, 22] and the centre is arr[m] where m = ((4 - 1) / 2) = 1. The centre is 3.

Example 1:

Input: arr = [1,2,3,4,5], k = 2
Output: [5,1]
Explanation: Centre 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 also accepted answer.
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 = 2
Output: [5,5]
Explanation: Centre 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 = 5
Output: [11,8,6,6,7]
Explanation: Centre 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] is accepted.

Constraints:

1 <= arr.length <= 10⁵
-10⁵ <= arr[i] <= 10⁵
1 <= k <= arr.length

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for elements within the input array?
Can the input array be empty, or can k be zero, or larger than the array's size?
By 'strongest,' is there a specific rule for how to handle ties, e.g., is it lexicographical or based on original array order?
Should I return the strongest values in any specific order?
Does the input array only contain integers, or could there be floating-point numbers?

Brute Force Solution

Approach

To find the 'strongest' values, we'll check every single number in the list one by one. We'll then compare each of them to a special value, and see how 'strong' they are. We will then simply pick the top k 'strongest' numbers according to this criteria.

Here's how the algorithm would work step-by-step:

Calculate the middle value of the list.
For each number in the list, find its difference from the middle value.
Decide how 'strong' each number is by looking at its difference from the middle value; a larger difference means it's stronger.
Now, go through the list of numbers and their 'strength' values.
Pick out the numbers with the k highest 'strength' values.
Return these k numbers as the 'strongest' values in the list.

Code Implementation

def get_k_strongest_values(
        numbers, k):

    middle_value = sorted(numbers)[(len(numbers) - 1) // 2]

    # Calculate the strength of each number based on its distance from the median
    strength_values = []
    for number in numbers:
        strength = abs(number - middle_value)
        strength_values.append((number, strength))

    # Sort the numbers by their strength in descending order
    strongest_values = sorted(
        strength_values,
        key=lambda item: item[1],
        reverse=True
    )

    # Extract the k strongest numbers
    result = [number for number, _ in strongest_values[:k]]

    return result

Big(O) Analysis

Time Complexity

O(n log n) – The solution involves calculating the median of the array, which requires sorting. Sorting an array of size n typically takes O(n log n) time. After sorting, iterating through the array once takes O(n) time to calculate the strength of each value, and selecting the k strongest values can be done in O(n log k) if we use a heap of size k or O(n log n) if we do a full sort of the strength values. However, without using more advanced selection algorithms, we can assume a sorting method is used in the later steps. Since the initial sort dominates the strength calculations, the overall time complexity is O(n log n).

Space Complexity

O(N) – The algorithm implicitly requires storing the differences between each number and the median, which could be done in an auxiliary array of size N where N is the number of elements in the input array. Also, to keep track of the 'strength' and its corresponding value, another array of size N might be used. Therefore, the space complexity is directly proportional to the input size N, resulting in O(N) space.

Optimal Solution

Approach

To find the strongest values efficiently, we first need to know the middle point of the values. Then, we can compare each value to that middle point and pick out the ones that are farthest away, because those are considered the strongest.

Here's how the algorithm would work step-by-step:

First, arrange all the values from smallest to largest.
Find the middle value in the sorted list. If the list has an even number of values, the middle is the average of the two values closest to the middle.
Now, compare each value to the middle value. The 'strength' of a value is how far away it is from the middle value.
Arrange all the values based on their strength, with the strongest values first. If two values have the same strength, keep the one that appears earlier in the original list.
Finally, pick the first 'k' values from this strength-ordered list. These are the 'k' strongest values.

Code Implementation

def get_strongest(array, k):
    array.sort()
    array_length = len(array)
    median = array[(array_length - 1) // 2]

    # Sort by strength, then original order.
    sorted_by_strength = sorted(array, key=lambda number:
                               (abs(number - median), array.index(number,0,len(array))),reverse=True)

    # Return the first k strongest values
    return sorted_by_strength[:k]

Big(O) Analysis

Time Complexity

O(n log n) – The initial step involves sorting the input array of size n, which typically takes O(n log n) time using efficient sorting algorithms like merge sort or quicksort. After sorting, finding the median takes constant time, O(1). Calculating the strength (absolute difference from the median) for each element is O(n). Finally, sorting the elements based on strength, maintaining original order for ties, also takes O(n log n) time. Therefore, the dominant operations are the two sorting steps, resulting in a total time complexity of O(n log n).

Space Complexity

O(N) – The algorithm sorts the input array of size N, which typically requires auxiliary space depending on the sorting algorithm used. Common sorting algorithms like merge sort need O(N) auxiliary space for temporary arrays during the merge process. Also, the strength calculation and sorting of values based on strength creates a list to store the strength-ordered values which is of size N in the worst-case. Therefore, the overall auxiliary space complexity is O(N).

Edge Cases

Case	How to Handle
Null or empty input array	Return an empty list or throw an IllegalArgumentException, depending on the specific requirements of the problem and coding style.
Array with fewer than k elements	Return the array sorted by strength value, or truncate to the length of the array if k exceeds the array length.
Array with all identical values	The median will be the repeated value, and the k strongest values will be the first k elements when sorted by index (or any k elements).
Large array size impacting sorting performance	Consider using a more efficient sorting algorithm like quicksort or mergesort if the naive approach of sorting takes too long (O(n log n) or better) on large arrays.
Integer overflow when calculating strength (\|arr[i] - median\|)	Use long data type to prevent overflow during the subtraction and absolute value calculation.
k is zero or negative	Return an empty list or throw an IllegalArgumentException, since there is no valid set of strongest values.
Array contains duplicate strongest values.	The problem definition should clarify how to handle ties in strength when selecting the top k elements; select any k values that satisfy the strongest criteria.
Array contains negative numbers, zeros, and positive numbers.	The absolute value calculation ensures that strength is always a non-negative value, so the algorithm works correctly with mixed positive, negative, and zero values.

Null or empty input array

How to Handle:

Return an empty list or throw an IllegalArgumentException, depending on the specific requirements of the problem and coding style.

Array with fewer than k elements

How to Handle:

Return the array sorted by strength value, or truncate to the length of the array if k exceeds the array length.

Array with all identical values

How to Handle:

The median will be the repeated value, and the k strongest values will be the first k elements when sorted by index (or any k elements).

Large array size impacting sorting performance

How to Handle:

Consider using a more efficient sorting algorithm like quicksort or mergesort if the naive approach of sorting takes too long (O(n log n) or better) on large arrays.

Integer overflow when calculating strength (|arr[i] - median|)

How to Handle:

Use long data type to prevent overflow during the subtraction and absolute value calculation.

k is zero or negative

How to Handle:

Return an empty list or throw an IllegalArgumentException, since there is no valid set of strongest values.

Array contains duplicate strongest values.

How to Handle:

The problem definition should clarify how to handle ties in strength when selecting the top k elements; select any k values that satisfy the strongest criteria.

Array contains negative numbers, zeros, and positive numbers.

How to Handle:

The absolute value calculation ensures that strength is always a non-negative value, so the algorithm works correctly with mixed positive, negative, and zero values.