Sort Transformed Array
Sort Transformed Array is a medium arrays & hashing problem solved with the two pointer pattern.
The best approach, optimal (two pointers from the ends), runs in O(n) time and O(n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (transform, then sort) up.
Problem
You are given an integer array nums sorted in non-decreasing order and three integers a, b and c. Apply the quadratic function f(x) = a·x² + b·x + c to every element.
Return the transformed values as an array sorted in non-decreasing order.
Can you do it in O(n) time, without a general-purpose sort?
Examples
Example 1
- Input
nums = [-3,-1,0,2,5], a = 1, b = -2, c = 1- Output
[1,1,4,16,16]- Why
- f(x) = x² - 2x + 1 = (x - 1)² maps the values to 16, 4, 1, 1, 16, which sorted are [1,1,4,16,16].
Example 2
- Input
nums = [-2,0,3], a = 0, b = -3, c = 4- Output
[-5,4,10]- Why
- With a = 0 the function is the line -3x + 4, which reverses the order: 10, 4, -5.
Example 3
- Input
nums = [-4,-2,1,3], a = -1, b = 0, c = 10- Output
[-6,1,6,9]- Why
- The parabola opens downward, so the values far from 0 become the smallest: -6, 6, 9, 1 sorted.
Constraints
1 <= nums.length <= 200-100 <= nums[i], a, b, c <= 100numsis sorted in non-decreasing order.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (transform, then sort) | O(n log n) | O(n) |
| Optimal (two pointers from the ends) | O(n) | O(n) |
1Brute force (transform, then sort)
O(n log n)The transform is linear and the sort costs n log n.O(n)The output array.Compute f(x) for every element and sort the results.
- res[i] = a · nums[i]² + b · nums[i] + c.
- Sort res and return it.
class Solution {
public int[] sortTransformedArray(int[] nums, int a, int b, int c) {
int n = nums.length;
int[] res = new int[n];
for (int i = 0; i < n; i++) res[i] = a * nums[i] * nums[i] + b * nums[i] + c;
Arrays.sort(res);
return res;
}
}class Solution:
def sortTransformedArray(self, nums: List[int], a: int, b: int, c: int) -> List[int]:
return sorted(a * x * x + b * x + c for x in nums)class Solution {
public:
vector<int> sortTransformedArray(vector<int>& nums, int a, int b, int c) {
vector<int> res;
for (int x : nums) res.push_back(a * x * x + b * x + c);
sort(res.begin(), res.end());
return res;
}
};function sortTransformedArray(nums, a, b, c) {
return nums.map((x) => a * x * x + b * x + c).sort((p, q) => p - q);
}2Optimal (two pointers from the ends)
O(n)Each step places one value and moves one pointer.O(n)Only the output array; O(1) extra besides it.A quadratic is monotonic on each side of its vertex, so for a sorted input the extreme results sit at the two ends. If a >= 0 the ends hold the largest values, so fill the output from the back with the larger of f(nums[left]) and f(nums[right]). If a < 0 the ends hold the smallest values, so fill from the front with the smaller one. A straight line (a = 0) works with either rule.
- left = 0, right = n - 1; idx = a >= 0 ? n - 1 : 0.
- While left <= right: fl = f(nums[left]), fr = f(nums[right]).
- If a >= 0: put max(fl, fr) at res[idx--] and move that pointer inward.
- Else: put min(fl, fr) at res[idx++] and move that pointer inward.
class Solution {
public int[] sortTransformedArray(int[] nums, int a, int b, int c) {
int n = nums.length;
int[] res = new int[n];
int left = 0, right = n - 1;
int idx = a >= 0 ? n - 1 : 0;
while (left <= right) {
int fl = f(nums[left], a, b, c), fr = f(nums[right], a, b, c);
if (a >= 0) {
if (fl >= fr) { res[idx--] = fl; left++; }
else { res[idx--] = fr; right--; }
} else {
if (fl <= fr) { res[idx++] = fl; left++; }
else { res[idx++] = fr; right--; }
}
}
return res;
}
private int f(int x, int a, int b, int c) {
return a * x * x + b * x + c;
}
}class Solution:
def sortTransformedArray(self, nums: List[int], a: int, b: int, c: int) -> List[int]:
def f(x):
return a * x * x + b * x + c
n = len(nums)
res = [0] * n
left, right = 0, n - 1
idx = n - 1 if a >= 0 else 0
while left <= right:
fl, fr = f(nums[left]), f(nums[right])
if a >= 0:
if fl >= fr:
res[idx] = fl
left += 1
else:
res[idx] = fr
right -= 1
idx -= 1
else:
if fl <= fr:
res[idx] = fl
left += 1
else:
res[idx] = fr
right -= 1
idx += 1
return resclass Solution {
public:
vector<int> sortTransformedArray(vector<int>& nums, int a, int b, int c) {
auto f = [&](int x) { return a * x * x + b * x + c; };
int n = nums.size();
vector<int> res(n);
int left = 0, right = n - 1;
int idx = a >= 0 ? n - 1 : 0;
while (left <= right) {
int fl = f(nums[left]), fr = f(nums[right]);
if (a >= 0) {
if (fl >= fr) { res[idx--] = fl; left++; }
else { res[idx--] = fr; right--; }
} else {
if (fl <= fr) { res[idx++] = fl; left++; }
else { res[idx++] = fr; right--; }
}
}
return res;
}
};function sortTransformedArray(nums, a, b, c) {
const f = (x) => a * x * x + b * x + c;
const n = nums.length;
const res = new Array(n);
let left = 0, right = n - 1;
let idx = a >= 0 ? n - 1 : 0;
while (left <= right) {
const fl = f(nums[left]), fr = f(nums[right]);
if (a >= 0) {
if (fl >= fr) { res[idx--] = fl; left++; }
else { res[idx--] = fr; right--; }
} else {
if (fl <= fr) { res[idx++] = fl; left++; }
else { res[idx++] = fr; right--; }
}
}
return res;
}Edge cases to test
a = 0: the function is a straight line (increasing, decreasing, or constant when b = 0 too)a < 0: the parabola opens downward- All inputs on one side of the vertex, so the result keeps or reverses the input order
- Duplicate values in
nums - A single element
Hints
Hint 1
The simplest correct answer: apply the function to each value and sort.
Hint 2
For a > 0 the parabola is U-shaped: the largest results come from the two ends of the sorted input, and they shrink toward the vertex.
Hint 3
Use two pointers at the ends. If a >= 0, repeatedly place the larger of f(left) and f(right) at the back of the output; if a < 0, place the smaller one at the front.
FAQ
What is the best time complexity for Sort Transformed Array?
Optimal (two pointers from the ends) runs in O(n) time and O(n) extra space. Each step places one value and moves one pointer.
Which pattern does Sort Transformed Array use?
It is a arrays & hashing problem that uses the two pointer pattern. Other problems with the same pattern: Two Sum II - Input Array Is Sorted, Valid Triangle Number, Container With Most Water.
Is there a brute force solution for Sort Transformed Array?
Yes. Brute force (transform, then sort) takes O(n log n) time and O(n) space. Compute f(x) for every element and sort the results.
Which edge cases should I test for Sort Transformed Array?
a = 0: the function is a straight line (increasing, decreasing, or constant when b = 0 too); a < 0: the parabola opens downward; All inputs on one side of the vertex, so the result keeps or reverses the input order; Duplicate values in nums; A single element.