We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

The k Strongest Values in an Array

Difficulty: Medium

Problem Description

Given an array of integers arr and an integer k, a value arr[i] is stronger than a value arr[j] if |arr[i] - m| > |arr[j] - m| where m is the center of the array. If |arr[i] - m| == |arr[j] - m|, then arr[i] is stronger than arr[j] if arr[i] > arr[j]. Return a list of the strongest k values in the array in any arbitrary order.

Key Insights

  • The center of the array is defined as the element at index ((n - 1) / 2) in the sorted version of the array.
  • The strength of an element is determined by its distance from the center, and in case of a tie, by its value.
  • Sorting the array based on the strength criteria will allow us to select the strongest k elements efficiently.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting the array.
Space Complexity: O(n) for storing the sorted array and results.

Solution

To solve the problem, we can follow these steps:

  1. Sort the array to find the center element.
  2. Calculate the center value m.
  3. Create a list of tuples where each tuple contains the strength and the original value of the elements.
  4. Sort this list based on strength and value.
  5. Select the top k strongest values from the sorted list.

This approach utilizes sorting and a custom comparison for strength, which ensures correctness and efficiency.

Code Solutions

def getStrongest(arr, k):
    arr.sort()
    n = len(arr)
    m = arr[(n - 1) // 2]
    # Create a list of tuples (strength, value)
    strength_values = [(abs(x - m), x) for x in arr]
    # Sort by strength first, then by value
    strength_values.sort(key=lambda x: (x[0], x[1]), reverse=True)
    # Extract the top k strongest values
    return [strength_values[i][1] for i in range(k)]
← Back to All Questions