Sort Transformed Array

Sort Transformed Array

What is this problem about?

"Sort Transformed Array" is a mathematical optimization problem. You are given a sorted integer array and three constants $a, b,$ and $c$. For each element $x$ in the array, you must calculate the result of the quadratic function $f(x) = ax^2 + bx + c$.

The goal is to return a new array containing these transformed values in sorted (ascending) order. The challenge is to do this in $O(N)$ time, taking advantage of the fact that the original array is already sorted and the quadratic function follows a predictable parabolic shape.

Why is this asked in interviews?

Google and LinkedIn ask this to see if a candidate can apply mathematical properties to algorithmic optimization. A naive solution ($O(N \log N)$) is to transform all values and then sort. However, an $O(N)$ solution requires understanding that a parabola is monotonic on either side of its vertex. This problem tests your ability to use the Two Pointers pattern in a non-obvious way.

Algorithmic pattern used

The primary pattern is the Two Pointers technique combined with Parabolic properties.

• If $a > 0$: The parabola opens upwards. The largest values are at the ends of the sorted array. Use two pointers at the ends and fill the result array from right to left.
• If $a < 0$: The parabola opens downwards. The smallest values are at the ends. Use two pointers and fill the result array from left to right.
• If $a = 0$: The function is linear ($bx + c$). Depending on the sign of $b$, either the original order is preserved or it is reversed.

Example explanation

Array: [-4, -2, 2, 4], a = 1, b = 3, c = 5 Function: $x^2 + 3x + 5$. Since $a=1 > 0$, it's an upward parabola.

1. $f(-4) = 16 - 12 + 5 = 9$
2. $f(4) = 16 + 12 + 5 = 33$
3. $33 > 9$, so 33 is the largest. Result: [..., 33]. right moves to index 2.
4. $f(2) = 4 + 6 + 5 = 15$
5. $15 > 9$, so 15 is the next largest. Result: [..., 15, 33]. right moves to index 1. And so on.

Common mistakes candidates make

A common mistake is forgetting that the vertex of the parabola $(-b/2a)$ might be in the middle of the array, meaning the values don't just increase or decrease linearly. Another error is not handling the $a < 0$ and $a > 0$ cases differently. Finally, many candidates miss the $O(N)$ constraint entirely and settle for an $O(N \log N)$ sort, which is a suboptimal answer in a high-level interview.

Interview preparation tip

When you see a problem involving a sorted array and a transformation, always check if the transformation is "monotonic" or "bitonic" (like a parabola). If it is, the Two Pointers pattern is almost always the key to achieving a linear time complexity. This is a very common "optimization" interview pattern.