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

Sort Transformed Array

Number: 360

Difficulty: Medium

Paid? Yes

Companies: LinkedIn, Google

Problem Description

Given a sorted integer array and three integers a, b, and c, apply the quadratic function f(x) = ax² + bx + c to each element in the array and return the resulting array in sorted order. The challenge is to achieve this in O(n) time by taking advantage of both the sorted input and the properties of the quadratic function.

Key Insights

  • The input array is sorted in ascending order.
  • The quadratic function forms a parabola, which is either convex (opens upward when a > 0) or concave (opens downward when a < 0).
  • Depending on the value of a, the transformation may cause the largest or smallest values to appear at the ends of the array.
  • A two-pointers approach can be used to efficiently merge the results into a sorted order in O(n) time by comparing transformed values from both ends.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

The solution leverages a two-pointers technique. First, define a helper function to compute f(x) = ax² + bx + c for any given x. Depending on whether a is positive or negative, the strategy differs:

  • If a ≥ 0 (convex parabola): The two extreme ends of the sorted array generate the largest transformed values. Initialize two pointers (left at the beginning and right at the end) and fill a result array from the end backwards. Compare f(nums[left]) and f(nums[right]) and place the larger value at the current end position, moving the corresponding pointer.
  • If a < 0 (concave parabola): The smallest values are at the ends. This time, fill the result array from the beginning forwards using a similar two-pointer approach. This technique avoids the need to sort the transformed values from scratch and meets the O(n) time requirement.

Code Solutions

# Python solution for Sort Transformed Array

def sort_transformed_array(nums, a, b, c):
    # Helper function to compute the quadratic transformation.
    def f(x):
        return a * x * x + b * x + c

    n = len(nums)
    result = [0] * n  # Initialize result array.
    
    left, right = 0, n - 1
    # Choose filling direction based on the sign of a.
    # If a is positive, fill from the end since larger values come from the ends.
    # Otherwise, fill from the beginning.
    index = n - 1 if a >= 0 else 0
    
    while left <= right:
        left_val = f(nums[left])
        right_val = f(nums[right])
        
        if a >= 0:
            # For convex parabola, place larger transformed values at the end.
            if left_val >= right_val:
                result[index] = left_val
                left += 1
            else:
                result[index] = right_val
                right -= 1
            index -= 1  # Fill backwards
        else:
            # For concave parabola, place smaller transformed values at the beginning.
            if left_val <= right_val:
                result[index] = left_val
                left += 1
            else:
                result[index] = right_val
                right -= 1
            index += 1  # Fill forwards
    return result

# Example usage:
print(sort_transformed_array([-4, -2, 2, 4], 1, 3, 5))   # Output: [3, 9, 15, 33]
print(sort_transformed_array([-4, -2, 2, 4], -1, 3, 5))  # Output: [-23, -5, 1, 7]
← Back to All Questions