Problem Description

Given an array of integers arr and an integer k, you need to find the strongest k values in the array.

The strength of values is determined by a special comparison rule based on the median of the array:

Finding the Median (m):

• First, sort the array
• The median m is located at position (n-1)/2 in the sorted array (using integer division and 0-indexing)
• For example:
  • Array [6, -3, 7, 2, 11] becomes [-3, 2, 6, 7, 11] after sorting, median is at index (5-1)/2 = 2, so m = 6
  • Array [-7, 22, 17, 3] becomes [-7, 3, 17, 22] after sorting, median is at index (4-1)/2 = 1, so m = 3

Strength Comparison Rules: A value arr[i] is stronger than arr[j] if:

1. |arr[i] - m| > |arr[j] - m| (the value with greater distance from median is stronger)
2. If distances are equal (|arr[i] - m| == |arr[j] - m|), then the larger value is stronger (arr[i] > arr[j])

Your task is to return a list containing the k strongest values from the array. The values can be returned in any order.

The solution approach involves:

1. Sorting the array to find the median
2. Re-sorting the array based on the strength criteria (by distance from median, then by value)
3. Returning the first k elements from this strength-sorted array

Intuition

The key insight is that we need to perform two separate sorting operations for different purposes.

First, we need to find the median, which requires sorting the array in ascending order. The median isn't the mathematical average but rather the middle element in the sorted array at position (n-1)/2. This gives us our reference point m for measuring strength.

Once we have the median, we need to identify which elements are "strongest". The strength definition creates a custom ordering where:

• Elements farther from the median are stronger
• Among elements equally distant from the median, larger values are stronger

This naturally suggests using a custom sorting approach. We can sort all elements by their strength criteria and then simply take the first k elements from this sorted list.

The sorting key needs to prioritize:

1. Distance from median (larger distance = stronger): We use -abs(x - m) with a negative sign because Python sorts in ascending order by default, but we want elements with larger distances first
2. Value itself as tiebreaker (larger value = stronger): We use -x for the same reason - to get larger values first when distances are equal

By sorting with the key lambda x: (-abs(x - m), -x), we arrange all elements from strongest to weakest. The tuple comparison in Python naturally handles our two-level priority: it first compares by distance, then by value if distances are equal.

After this custom sort, the problem becomes trivial - just return the first k elements, which are guaranteed to be the k strongest values in the array.

Learn more about Two Pointers and Sorting patterns.

Solution Approach

The implementation follows a straightforward two-step sorting strategy:

Step 1: Find the Median

arr.sort()
m = arr[(len(arr) - 1) >> 1]

• First, we sort the array in ascending order using arr.sort()
• Then we calculate the median position using (len(arr) - 1) >> 1
  • The >> 1 is a bitwise right shift operation, equivalent to integer division by 2
  • This gives us the index (n-1)/2 for the median
• We store the median value in variable m

Step 2: Sort by Strength

arr.sort(key=lambda x: (-abs(x - m), -x))

• We perform a second sort on the array using a custom key function
• The key function returns a tuple (-abs(x - m), -x) for each element x
• Python sorts tuples lexicographically (comparing first element, then second if first is equal)
• Breaking down the key:
  • -abs(x - m): Negative absolute distance from median. The negative sign ensures elements with larger distances come first (since Python sorts in ascending order)
  • -x: Negative value of the element itself. Used as a tiebreaker when distances are equal - larger values come first

Step 3: Return Result

return arr[:k]

• After sorting by strength, the array is ordered from strongest to weakest
• We use array slicing arr[:k] to return the first k elements
• These are guaranteed to be the k strongest values

The solution leverages Python's stable sort algorithm (Timsort) which maintains relative order of equal elements. The time complexity is O(n log n) due to the two sorting operations, and space complexity is O(1) if we don't count the space used by the sorting algorithm itself.

Example Walkthrough

Let's walk through the solution with the array arr = [6, -3, 7, 2, 11] and k = 3.

Step 1: Find the Median

• Sort the array: [-3, 2, 6, 7, 11]
• Calculate median index: (5-1) >> 1 = 4 >> 1 = 2
• Median value: m = 6

Step 2: Calculate Strength for Each Element

Let's calculate the strength metrics for each original element:

• 6: distance = |6 - 6| = 0, value = 6
• -3: distance = |-3 - 6| = 9, value = -3
• 7: distance = |7 - 6| = 1, value = 7
• 2: distance = |2 - 6| = 4, value = 2
• 11: distance = |11 - 6| = 5, value = 11

Step 3: Sort by Strength

Using our sorting key (-abs(x - m), -x), each element gets:

• 6: (-0, -6) = (0, -6)
• -3: (-9, 3) = (-9, 3)
• 7: (-1, -7) = (-1, -7)
• 2: (-4, -2) = (-4, -2)
• 11: (-5, -11) = (-5, -11)

Sorting these tuples in ascending order:

1. (-9, 3) → -3 (largest distance: 9)
2. (-5, -11) → 11 (distance: 5)
3. (-4, -2) → 2 (distance: 4)
4. (-1, -7) → 7 (distance: 1)
5. (0, -6) → 6 (distance: 0)

After sorting by strength: [-3, 11, 2, 7, 6]

Step 4: Return k Strongest

Return the first k = 3 elements: [-3, 11, 2]

These are the 3 strongest values because:

• -3 is strongest (farthest from median with distance 9)
• 11 is second strongest (distance 5 from median)
• 2 is third strongest (distance 4 from median)

Solution Implementation

Time and Space Complexity

The time complexity is O(n × log n), where n is the length of the array arr. This is because:

• The first arr.sort() operation takes O(n × log n) time
• Finding the median m takes O(1) time
• The second arr.sort() with a custom key also takes O(n × log n) time
• Slicing the array to return arr[:k] takes O(k) time, which is at most O(n)
• Overall: O(n × log n) + O(1) + O(n × log n) + O(k) = O(n × log n)

The space complexity is O(n), where n is the length of the array arr. This is because:

• The sorting operations in Python's Timsort algorithm require O(n) auxiliary space in the worst case
• The slicing operation arr[:k] creates a new list of size k, which is at most O(n)
• Overall: O(n) space complexity

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Median Calculation for Even-Length Arrays

A common mistake is assuming the median calculation (n-1)//2 works the same way as traditional median calculations. In this problem, the median is specifically defined as the element at index (n-1)//2 regardless of whether the array length is odd or even.

Pitfall Example:

# WRONG: Traditional median for even-length arrays
if len(arr) % 2 == 0:
    m = (arr[len(arr)//2 - 1] + arr[len(arr)//2]) / 2  # Average of two middle elements
else:
    m = arr[len(arr)//2]

Correct Approach:

# RIGHT: Always use (n-1)//2 as specified
m = arr[(len(arr) - 1) // 2]

2. Modifying Original Array Without Considering Side Effects

The solution modifies the input array twice with arr.sort(). If the problem requires preserving the original array or if the caller expects the array to remain unchanged, this could cause issues.

Solution:

def getStrongest(self, arr: List[int], k: int) -> List[int]:
    # Create a copy to avoid modifying the original
    sorted_arr = sorted(arr)
    m = sorted_arr[(len(sorted_arr) - 1) // 2]
  
    # Sort by strength criteria
    sorted_arr.sort(key=lambda x: (-abs(x - m), -x))
    return sorted_arr[:k]

3. Incorrect Sorting Key for Tie-Breaking

When distances from median are equal, the problem states the larger value is stronger. A common mistake is forgetting the negative sign or using the wrong comparison.

Pitfall Example:

# WRONG: Smaller values would come first in ties
arr.sort(key=lambda x: (-abs(x - m), x))  # Missing negative on second element

# WRONG: Would sort by ascending distance (weakest first)
arr.sort(key=lambda x: (abs(x - m), -x))  # Missing negative on first element

Correct Approach:

# RIGHT: Both components need negation for descending order
arr.sort(key=lambda x: (-abs(x - m), -x))

4. Using Bitwise Operator Without Understanding

While (len(arr) - 1) >> 1 works correctly as integer division by 2, it can be confusing and error-prone.

More Readable Alternative:

# Clearer and equally efficient
median_index = (len(arr) - 1) // 2

5. Edge Case: k equals array length

While the provided solution handles this correctly with slicing (arr[:k]), explicitly checking can prevent potential issues if the implementation changes.

Defensive Programming:

def getStrongest(self, arr: List[int], k: int) -> List[int]:
    if k == len(arr):
        return arr  # All elements are the answer
  
    # ... rest of the solution