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

Sort By

Number: 2860

Difficulty: Easy

Paid? No

Companies: Google

Problem Description

Given an array arr and a function fn that returns numbers, return a new array sortedArr where arr is sorted in ascending order based on the value returned by applying fn to each element. It is guaranteed that for each element in arr, fn produces a unique number.

Key Insights

  • We need to sort based on a computed key from each element using the provided function.
  • Since fn returns unique numbers for each element, there are no collisions in the key values.
  • A simple sort with a custom comparator (that compares fn output) will solve the problem.

Space and Time Complexity

Time Complexity: O(n log n) due to the sorting algorithm. Space Complexity: O(n) if using a sort implementation that requires extra space for sorting; otherwise O(1) for in-place sorts.

Solution

The solution involves sorting the array by using the output of the function fn on each element as the key. This is done by:

  • Evaluating fn(element) for each element during the comparison in sorting.
  • Leveraging built-in sorting functions that accept a custom comparator or key extractor.
  • Ensuring the sorted order is ascending based on fn(element). In Python, this can be achieved with the sorted() function and its key parameter. In JavaScript, we use the Array.sort() method with a comparator that subtracts fn(a) from fn(b). The C++ and Java solutions follow a similar strategy with lambdas and custom comparators respectively.

Code Solutions

# Define the function to sort the array based on the fn output.
def sortBy(arr, fn):
    # Use Python's built-in sorted() function with a custom key function.
    # sorted() returns a new list sorted in ascending order.
    return sorted(arr, key=fn)

# Example usage:
if __name__ == "__main__":
    # Example 1:
    arr1 = [5, 4, 1, 2, 3]
    sorted_arr1 = sortBy(arr1, lambda x: x)
    print(sorted_arr1)  # Outputs: [1, 2, 3, 4, 5]
    
    # Example 2:
    arr2 = [{"x": 1}, {"x": 0}, {"x": -1}]
    sorted_arr2 = sortBy(arr2, lambda d: d["x"])
    print(sorted_arr2)  # Outputs: [{'x': -1}, {'x': 0}, {'x': 1}]
← Back to All Questions