Sort Transformed Array

medium two pointers math

Problem

Given a sorted array nums and coefficients a, b, c of a quadratic f(x) = ax² + bx + c, return the sorted array of f(nums[i]).

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

Output[3,9,15,33]

f values: 9, 3, 15, 33 → sorted.

nums (sorted)

def sort_transformed_array(nums, a, b, c):
    def f(x): return a * x * x + b * x + c
    n = len(nums)
    out = [0]*n
    i, j = 0, n - 1
    k = n - 1 if a >= 0 else 0
    step = -1 if a >= 0 else 1
    while i <= j:
        fi, fj = f(nums[i]), f(nums[j])
        if a >= 0:
            if fi >= fj: out[k] = fi; i += 1
            else: out[k] = fj; j -= 1
        else:
            if fi <= fj: out[k] = fi; i += 1
            else: out[k] = fj; j -= 1
        k += step
    return out

function sortTransformedArray(nums, a, b, c) {
  const f = x => a * x * x + b * x + c;
  const n = nums.length;
  const out = new Array(n);
  let i = 0, j = n - 1;
  let k = a >= 0 ? n - 1 : 0;
  const step = a >= 0 ? -1 : 1;
  while (i <= j) {
    const fi = f(nums[i]), fj = f(nums[j]);
    if (a >= 0) {
      if (fi >= fj) { out[k] = fi; i++; } else { out[k] = fj; j--; }
    } else {
      if (fi <= fj) { out[k] = fi; i++; } else { out[k] = fj; j--; }
    }
    k += step;
  }
  return out;
}

class Solution {
    public int[] sortTransformedArray(int[] nums, int a, int b, int c) {
        int n = nums.length;
        int[] out = new int[n];
        int i = 0, j = n - 1, k = a >= 0 ? n - 1 : 0, step = a >= 0 ? -1 : 1;
        while (i <= j) {
            int fi = f(a, b, c, nums[i]), fj = f(a, b, c, nums[j]);
            if (a >= 0) { if (fi >= fj) { out[k] = fi; i++; } else { out[k] = fj; j--; } }
            else { if (fi <= fj) { out[k] = fi; i++; } else { out[k] = fj; j--; } }
            k += step;
        }
        return out;
    }
    int f(int a, int b, int c, int x) { return a * x * x + b * x + c; }
}

vector sortTransformedArray(vector& nums, int a, int b, int c) {
    auto f = [&](int x) { return a * x * x + b * x + c; };
    int n = nums.size();
    vector out(n);
    int i = 0, j = n - 1, k = a >= 0 ? n - 1 : 0, step = a >= 0 ? -1 : 1;
    while (i <= j) {
        int fi = f(nums[i]), fj = f(nums[j]);
        if (a >= 0) { if (fi >= fj) { out[k] = fi; i++; } else { out[k] = fj; j--; } }
        else { if (fi <= fj) { out[k] = fi; i++; } else { out[k] = fj; j--; } }
        k += step;
    }
    return out;
}

Explanation

The input nums is already sorted, and applying a quadratic f(x) = ax² + bx + c bends it into a parabola. The key insight is where the extreme values land: for a parabola opening up (a >= 0) the largest f values are at the two ends; for one opening down (a < 0) the largest are in the middle.

So we use two pointers i (left) and j (right) and a merge-from-the-extremes idea. When a >= 0, the bigger of f(nums[i]) and f(nums[j]) is the current maximum, so we place it at the back of out and fill the result right to left (k starts at n-1, step = -1).

When a < 0 the logic flips: the smaller end value is the current minimum, so we fill left to right (k starts at 0, step = +1). Either way we advance whichever pointer we consumed.

Because we never sort again — just one comparison per element — this runs in linear time.

Example: nums = [-4,-2,2,4], a=1, b=3, c=5 (opens up). The f values are 9, 3, 15, 33. Comparing ends and filling from the right yields the sorted output [3, 9, 15, 33].

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