360. Sort Transformed Array - Detailed Explanation

Problem Statement

Given a sorted integer array nums of length n and integer coefficients a, b, c, define a quadratic function

f(x) = a*x^2 + b*x + c

Apply f to each element of nums and return the resulting array in sorted order.

Examples

1. Input
   nums = [-4, -2, 2, 4], a = 1, b = 3, c = 5
   Output
   [3, 9, 15, 33]
   Explanation
   f(x) = x² + 3x + 5 → transforms to [9, 3, 15, 33] → sorted → [3, 9, 15, 33]
2. Input
   nums = [-4, -2, 2, 4], a = -1, b = 3, c = 5
   Output
   [-23, -5, 1, 7]
   Explanation
   f(x) = -x² + 3x + 5 → transforms to [-23, -5, 1, -7] → sorted → [-23, -5, 1, 7]
3. Input
   nums = [0, 1, 2], a = 0, b = 2, c = -1
   Output
   [-1, 1, 3]
   Explanation
   f(x) = 2x − 1 → [−1, 1, 3] is already sorted

Constraints

• n == nums.length
• 1 ≤ n ≤ 10⁵
• -10⁴ ≤ nums[i], a, b, c ≤ 10⁴
• nums is sorted in non‑decreasing order

Brute Force Approach

1. Transform & Sort
   • Allocate an array res of length n.
   • For each i in [0, n) compute res[i] = f(nums[i]).
   • Sort res with any O(n log n) sort.
2. Complexity
   • Time O(n log n) for the sort
   • Space O(n) for the output array

Optimal Two‑Pointer Approach

Because nums is sorted, and f(x) is a parabola opening up if a>0 or down if a<0, the largest (or smallest) transformed values lie at the ends. We can merge from the outside in:

1. Setup
   • Two pointers left = 0, right = n-1.
   • Output array res of length n.
   • An index idx pointing at either the start (if a<0) or end (if a>=0) of res.
2. Merge Loop
   • While left ≤ right:
     • Compute L = f(nums[left]), R = f(nums[right]).
     • If a >= 0: place the larger of L,R at res[idx--]; else place the smaller at res[idx++].
     • Move the pointer (left++ or right--) whose value was used.
3. Why It Works
   • Parabola shape ensures extremes produce the extreme transformed values.
   • By filling from one end inward, we maintain sorted order without extra sorting.
4. Time O(n), Space O(n)

Step‑by‑Step Walkthrough

Take nums = [-4, -2, 2, 4], a = 1, b = 3, c = 5

• f(x) = x² + 3x + 5
• Initialize left=0→-4, right=3→4, idx=3 (fill from back)

1. L = f(-4)=9, R = f(4)=33 → place 33 at res[3], right→2
2. L = 9, R = f(2)=15 → place 15 at res[2], right→1
3. L = 9, R = f(-2)=3 → place 9 at res[1], left→1
4. Only left=1 remains: L=3 → place at res[0]
   Result → [3,9,15,33]

Complexity Analysis

• Time O(n) — single pass with two pointers
• Space O(n) — for output

Python Code