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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

The k Strongest Values in an Array

Number: 1581

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given an integer array and a number k, return a list of the k strongest values in the array. The "strength" of a value is determined by its absolute difference from the centre value of the sorted array. If two values have the same absolute difference from the centre, the larger value is considered stronger. The centre is defined as the element at index ((n-1)/2) in the sorted array, where n is the array's length.

Key Insights

  • The centre of the array is obtained by sorting the array and picking the element at index ((n-1)/2).
  • The strength of an element is measured by the absolute difference between the element and the centre.
  • When two elements have equal strength, the larger element is considered stronger.
  • A two-pointer approach on the sorted array can be efficiently used to pick the k strongest values.

Space and Time Complexity

Time Complexity: O(n log n) due to the sorting step.
Space Complexity: O(n) for storing the sorted array (if not sorting in-place) and the answer list.

Solution

The solution begins by sorting the input array to determine the centre element. With the centre identified, we use two pointers: one starting at the beginning (left) and the other at the end (right) of the sorted array. In each iteration, we compare the absolute differences of the values pointed to by the two pointers with respect to the centre. The pointer with the value that has a higher absolute difference (or, if equal, the greater value) contributes its value to the result list. We then move that pointer inward. We continue this process until we have collected k elements. This two-pointer strategy ensures that we always pick the strongest available value.

Code Solutions

# Python solution using the two-pointer approach

def getStrongest(arr, k):
    # Sort the array
    arr.sort()
    n = len(arr)
    # The center element as defined in the problem
    m = arr[(n - 1) // 2]
    
    # Initialize two pointers
    left, right = 0, n - 1
    result = []
    
    # Pick k strongest values using two pointers
    while k > 0:
        # Compare absolute differences from the center m
        if abs(arr[left] - m) > abs(arr[right] - m):
            result.append(arr[left])
            left += 1  # Move left pointer inward
        else:
            result.append(arr[right])
            right -= 1  # Move right pointer inward
        k -= 1
    
    return result

# Example usage:
# print(getStrongest([1,2,3,4,5], 2))
← Back to All Questions