Sort Transformed Array
Medium · Two Pointers · Explanation and code example
Two Pointers on a Quadratic Transform
How it works
A quadratic that opens upward has its largest transformed values at the ends of a sorted interval; one that opens downward has its smallest values there. Compare transformed endpoints and fill the result from the appropriate end without sorting it again.
Steps
- Transform every input value.
- Compare the two endpoints.
- Fill backward for a > 0, or forward otherwise, advancing the chosen endpoint.
Complexity
- Time: O(n).
- Space: O(n) for transformed values and result in these examples.
Things to watch for
- For a = 0 the function is linear, and the endpoint rule still works.
- Choose the fill direction from the sign of a.
- Do not assume the transformed input remains sorted.
Python code example
class Solution:
def sortTransformedArray(
self,
nums: list[int],
a: int,
b: int,
c: int,
) -> list[int]:
n = len(nums)
upward = a > 0
ans = [0] * n
# The concavity of f only depends on a's sign.
def f(x: int, a: int, b: int, c: int) -> int:
return (a * x + b) * x + c
quad = [f(num, a, b, c) for num in nums]
i = n - 1 if upward else 0
l = 0
r = n - 1
while l <= r:
if upward: # is the maximum in the both ends
if quad[l] > quad[r]:
ans[i] = quad[l]
l += 1
else:
ans[i] = quad[r]
r -= 1
i -= 1
else: # is the minimum in the both ends
if quad[l] < quad[r]:
ans[i] = quad[l]
l += 1
else:
ans[i] = quad[r]
r -= 1
i += 1
return ans
C++ code example
class Solution {
public:
vector<int> sortTransformedArray(vector<int>& nums, int a, int b, int c) {
const int n = nums.size();
const bool upward = a > 0;
vector<int> ans(n);
vector<int> quad;
for (const int num : nums)
quad.push_back(f(num, a, b, c));
int i = upward ? n - 1 : 0;
for (int l = 0, r = n - 1; l <= r;)
if (upward) // is the maximum in the both ends
ans[i--] = quad[l] > quad[r] ? quad[l++] : quad[r--];
else // is the minimum in the both ends
ans[i++] = quad[l] < quad[r] ? quad[l++] : quad[r--];
return ans;
}
private:
// The concavity of f only depends on a's sign.
int f(int x, int a, int b, int c) {
return (a * x + b) * x + c;
}
};
Source and license
Explanation by LC Tracker. Code adapted from walkccc / Peng-Yu Chen · MIT license. Node types are supplied by LeetCode where needed.