Sort Transformed Array - Solution & Explanation

Problem Overview: You receive a sorted integer array nums and coefficients a, b, and c. Each element must be transformed using the quadratic function f(x) = ax^2 + bx + c. The result must remain sorted in ascending order. The challenge comes from the quadratic curve changing the order of values after transformation.

Approach 1: Transform Then Sort (Brute Force) (Time: O(n log n), Space: O(n))

The most direct solution applies the quadratic transformation to every element in the array and stores the results in a new list. Once all values are computed, you sort the resulting array using a standard sorting algorithm. The implementation is straightforward: iterate through nums, compute a*x*x + b*x + c for each element, and call a sort function. While simple, this ignores the fact that the input array is already sorted and the quadratic function has predictable behavior. Because sorting dominates the runtime, the complexity becomes O(n log n) with O(n) extra space. This approach works but rarely impresses in interviews.

Approach 2: Math + Two Pointers (Time: O(n), Space: O(n))

The key observation comes from the shape of a quadratic function. If a >= 0, the parabola opens upward and the largest transformed values appear near the ends of the input array. If a < 0, the parabola opens downward and the smallest values appear near the ends. Because the original array is sorted, you can exploit this property using the two pointers technique.

Initialize one pointer at the left end and another at the right end of the array. Compute the transformed values for both elements. If a >= 0, place the larger value at the end of the result array and move the corresponding pointer inward. If a < 0, place the smaller value at the beginning and move the corresponding pointer. Continue until all elements are processed. Each element is evaluated once, giving O(n) time with O(n) space for the result array.

This approach combines mathematical insight with a classic array scanning pattern. Instead of re-sorting the transformed numbers, you construct the sorted order directly. The method relies on understanding how quadratic functions behave and how pointer comparisons preserve order.

Recommended for interviews: Interviewers expect the Math + Two Pointers solution. Starting with the transform-and-sort approach shows you understand the problem, but recognizing the parabola behavior and eliminating the sort demonstrates stronger algorithmic thinking. The optimal solution runs in linear time and is a common application of two pointers combined with simple math reasoning.