⚡Flashcard Drill➔
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

  1. f is a parabola. If a >= 0 it opens upward, so the largest values are at the ends of the sorted input; if a < 0 it opens downward and the smallest values are at the ends.
  2. Two pointers at the ends of nums, comparing f at each end.
  3. When a >= 0, fill the output from the back with the larger value. When a < 0, fill from the front with the smaller value.
  4. When a == 0 the function is linear, and either branch works (the a >= 0 branch 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 f and 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 f four times per iteration: it is called twice per branch, which is fine, but precomputing the transformed array once is cleaner.
  • Assuming a must be non-zero: a == 0 is allowed and falls into the a >= 0 branch correctly.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Two Pointers Problems