Sort Transformed Array — Solution in Python, Java & C++
Sort Transformed Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Sort Transformed Array is a medium coding problem on arrays, math and sorting, asked in Amazon, Google and Adobe interviews.
- Difficulty: Medium
- Topics: Arrays, Math, Sorting, Two Pointers
- Asked at: Amazon, Google, Adobe
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given a sorted array nums and the quadratic f(x) = a·x² + b·x + c.
Apply f to every element and return the results in sorted ascending order.
Example 1
Input: nums = [-4,-2,2,4], a = 1, b = 3, c = 5
Output: [3,9,15,33]
Explanation: The parabola opens upward, so the extremes of the input give the largest values.
Example 2
Input: nums = [-4,-2,2,4], a = -1, b = 3, c = 5
Output: [-23,-5,1,7]
Explanation: Opening downward reverses which ends are largest.
Example 3
Input: nums = [1,2,3], a = 0, b = 2, c = 1
Output: [3,5,7]
Explanation: With a = 0 the function is linear and increasing.
Constraints
1 <= nums.length <= 200-100 <= nums[i], a, b, c <= 100nums is sorted in ascending order.
Hints for Sort Transformed Array
Hint 1
Sorting the transformed values costs an extra
log n; two pointers get it in linear time.Hint 2
A parabola with
a > 0takes its largest values at the ends of a sorted input, so fill the output from the back.Hint 3
With
a < 0the largest values sit in the middle, so fill from the front taking the smaller end each time.
How to solve Sort Transformed Array
A quadratic is monotone away from its vertex, so on a sorted input the extreme values always sit at the two ends. Which end wins depends on the sign of a, and a two-pointer sweep fills the output in the right direction.
Approach
- Evaluate
fat the current left and right ends. - If
a >= 0the parabola opens upward: the larger of the two goes at the back of the output, and that pointer moves inward. - If
a < 0it opens downward: the smaller of the two goes at the front, and that pointer moves inward. - Continue until the pointers cross.
Why it works
For a > 0, f decreases then increases, so along a sorted input the maximum over any contiguous stretch is at one of its ends. Repeatedly removing that end therefore emits the values in decreasing order, which filling the output backwards turns into ascending order. The a < 0 case is the mirror image, and a = 0 makes f monotone, which both branches handle correctly.
Complexity
- Time —
O(n) - Space —
O(n) for the output
Pitfalls
- Assuming
a > 0always puts the maximum at the right end — with a vertex inside the range, the left end can be larger. - Treating
a = 0as a separate case is unnecessary but harmless; the upward branch handles it. - The values reach about
100 · 100² = 10^6, comfortably insideint.
Reference solution
Python
from typing import List
def sortTransformedArray(nums: List[int], a: int, b: int, c: int) -> List[int]:
def f(x: int) -> int:
return a * x * x + b * x + c
n = len(nums)
out = [0] * n
lo, hi = 0, n - 1
idx = n - 1 if a >= 0 else 0
while lo <= hi:
left, right = f(nums[lo]), f(nums[hi])
if a >= 0:
if left >= right:
out[idx] = left
lo += 1
else:
out[idx] = right
hi -= 1
idx -= 1
else:
if left <= right:
out[idx] = left
lo += 1
else:
out[idx] = right
hi -= 1
idx += 1
return outJava
public static int[] sortTransformedArray(int[] nums, int a, int b, int c) {
int n = nums.length;
int[] out = new int[n];
int lo = 0, hi = n - 1;
int idx = a >= 0 ? n - 1 : 0;
while (lo <= hi) {
int left = a * nums[lo] * nums[lo] + b * nums[lo] + c;
int right = a * nums[hi] * nums[hi] + b * nums[hi] + c;
if (a >= 0) {
if (left >= right) { out[idx] = left; lo++; } else { out[idx] = right; hi--; }
idx--;
} else {
if (left <= right) { out[idx] = left; lo++; } else { out[idx] = right; hi--; }
idx++;
}
}
return out;
}C++
vector<int> sortTransformedArray(vector<int>& nums, int a, int b, int c) {
int n = (int) nums.size();
vector<int> out(n);
int lo = 0, hi = n - 1;
int idx = a >= 0 ? n - 1 : 0;
while (lo <= hi) {
int left = a * nums[lo] * nums[lo] + b * nums[lo] + c;
int right = a * nums[hi] * nums[hi] + b * nums[hi] + c;
if (a >= 0) {
if (left >= right) { out[idx] = left; lo++; } else { out[idx] = right; hi--; }
idx--;
} else {
if (left <= right) { out[idx] = left; lo++; } else { out[idx] = right; hi--; }
idx++;
}
}
return out;
}JavaScript
var sortTransformedArray = function(nums, a, b, c) {
var f = function(x) { return a * x * x + b * x + c; };
var n = nums.length;
var out = [];
for (var t = 0; t < n; t++) out.push(0);
var lo = 0, hi = n - 1;
var idx = a >= 0 ? n - 1 : 0;
while (lo <= hi) {
var left = f(nums[lo]), right = f(nums[hi]);
if (a >= 0) {
if (left >= right) { out[idx] = left; lo++; } else { out[idx] = right; hi--; }
idx--;
} else {
if (left <= right) { out[idx] = left; lo++; } else { out[idx] = right; hi--; }
idx++;
}
}
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms