NeetCode #216LC-360MediumTwo Pointers
← Back to All Problems#216 · #360 · Sort Transformed Array(有序转化数组)
📌 Problem Statement & Constraints
Given a sorted array
nums and integers a, b, c, apply the quadratic function f(x) = a*x^2 + b*x + c to every element and return the results in sorted order. Constraints: 1 <= nums.length <= 200, -100 <= nums[i], a, b, c <= 100; nums is sorted ascending.💡 Core Algorithmic Approaches
fis a parabola. Ifa >= 0it opens upward, so the largest values are at the ends of the sorted input; ifa < 0it opens downward and the smallest values are at the ends.- Two pointers at the ends of
nums, comparingfat each end. - When
a >= 0, fill the output from the back with the larger value. Whena < 0, fill from the front with the smaller value. - When
a == 0the function is linear, and either branch works (thea >= 0branch is used).
💻 Benchmark Python3 Implementation
class Solution:
def sortTransformedArray(self, 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)
res = [0] * n
i, j = 0, n - 1
if a >= 0:
k = n - 1 # upward parabola: fill from the back
while i <= j:
if f(nums[i]) > f(nums[j]):
res[k] = f(nums[i])
i += 1
else:
res[k] = f(nums[j])
j -= 1
k -= 1
else:
k = 0 # downward parabola: fill from the front
while i <= j:
if f(nums[i]) < f(nums[j]):
res[k] = f(nums[i])
i += 1
else:
res[k] = f(nums[j])
j -= 1
k += 1
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): one pass with two pointers, no sorting.
💾 Space Complexity
O(n) for the result (O(1) extra).
⚠️ Interview Pitfalls & Follow-ups
- Applying
fand then sorting: O(n log n) and misses the parabola structure. - Filling from the wrong end for a downward parabola: when
a < 0, the extremes are the smallest values, so the result must be filled from the front. - Recomputing
ffour times per iteration: it is called twice per branch, which is fine, but precomputing the transformed array once is cleaner. - Assuming
amust be non-zero:a == 0is allowed and falls into thea >= 0branch correctly.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.