Is Sort Transformed Array easy or hard?

Sort Transformed Array is generally considered a medium-level problem. The brute force solution is simple, but the optimal O(n) solution requires recognizing how a quadratic function affects ordering and applying the two pointers technique correctly.

How to solve Sort Transformed Array in O(n)?

Exploit the shape of the quadratic function f(x) = ax^2 + bx + c. If a >= 0, the largest transformed values come from the ends of the sorted array, so compare both ends and fill the result from the back. If a < 0, the smallest values come from the ends, so fill from the front while moving two pointers inward.

What is the best approach for Sort Transformed Array?

The optimal approach uses Math + Two Pointers. Because the input array is already sorted and the transformation is a quadratic function, the largest or smallest results appear near the ends of the array depending on the sign of 'a'. Using two pointers from both ends allows you to construct the sorted output in O(n) time.

What data structure is used in Sort Transformed Array?

The solution mainly uses arrays along with the two pointers technique. Two indices track the left and right ends of the sorted input array while a result array is filled from either direction depending on the quadratic coefficient.

What is the time complexity of Sort Transformed Array?

The optimal solution runs in O(n) time and O(n) space. Each element is transformed once and placed into the correct position using two pointers. A simpler brute force method transforms every element and sorts the result, which takes O(n log n) time.

Sort Transformed Array Python or Java solution approach?

Both Python and Java implementations follow the same logic: evaluate the quadratic function for elements at the left and right pointers, compare results, and insert into the correct position in a result array. The pointer movement depends on whether the parabola opens upward or downward.

Is Sort Transformed Array asked at Google, Amazon, or Meta?

Sort Transformed Array has appeared in interviews at companies like Google and other large tech firms because it combines mathematical reasoning with the two pointers pattern. Interviewers use it to test whether candidates recognize structural properties instead of relying on sorting.

Description Hints 2 Solution Video 17:13

360. Sort Transformed Array

Q: What is the best approach for Sort Transformed Array?

The optimal approach uses Math + Two Pointers. Because the input array is already sorted and the transformation is a quadratic function, the largest or smallest results appear near the ends of the array depending on the sign of 'a'. Using two pointers from both ends allows you to construct the sorted output in O(n) time.

Q: What data structure is used in Sort Transformed Array?

The solution mainly uses arrays along with the two pointers technique. Two indices track the left and right ends of the sorted input array while a result array is filled from either direction depending on the quadratic coefficient.

Q: What is the time complexity of Sort Transformed Array?

The optimal solution runs in O(n) time and O(n) space. Each element is transformed once and placed into the correct position using two pointers. A simpler brute force method transforms every element and sorts the result, which takes O(n log n) time.

Q: Sort Transformed Array Python or Java solution approach?

Both Python and Java implementations follow the same logic: evaluate the quadratic function for elements at the left and right pointers, compare results, and insert into the correct position in a result array. The pointer movement depends on whether the parabola opens upward or downward.

Q: Is Sort Transformed Array asked at Google, Amazon, or Meta?

Sort Transformed Array has appeared in interviews at companies like Google and other large tech firms because it combines mathematical reasoning with the two pointers pattern. Interviewers use it to test whether candidates recognize structural properties instead of relying on sorting.

Medium58.0% acceptance3 companiesPremium elsewhere, free here

Given a sorted integer array nums and three integers a, b and c, apply a quadratic function of the form f(x) = ax² + bx + c to each element nums[i] in the array, and return the array in a sorted order.

Example 1:

Input: nums = [-4,-2,2,4], a = 1, b = 3, c = 5
Output: [3,9,15,33]

Example 2:

Input: nums = [-4,-2,2,4], a = -1, b = 3, c = 5
Output: [-23,-5,1,7]

Constraints:

1 <= nums.length <= 200
-100 <= nums[i], a, b, c <= 100
nums is sorted in ascending order.

Follow up: Could you solve it in O(n) time?

Asked at 3 companies

Google Meta

Topics

Hints open one at a time

Hint 1

x^2 + x will form a parabola.

Hint 2

Parameter A in: A * x^2 + B * x + C dictates the shape of the parabola.
Positive A means the parabola remains concave (high-low-high), but negative A inverts the parabola to be convex (low-high-low).

17:13

Still stuck?Read the written solution, or watch a walkthrough.

Open solution