LeetCode 360: Sort Transformed Array Solution in Python – A Step-by-Step Guide

What Is LeetCode 360: Sort Transformed Array?

LeetCode 360: Sort Transformed Array gives you a sorted array of integers and coefficients a, b, and c for a quadratic function f(x) = ax² + bx + c. You apply this function to each element, then return the resulting array in sorted order. Since the input is sorted, we can leverage that for efficiency—making it a fun mix of math and optimization!

Problem Statement

• Input:
• nums: Sorted array of integers (ascending).
• a, b, c: Integers for the quadratic function ax² + bx + c.
• Output: Array of integers - Transformed values sorted in ascending order.
• Rules:
• Apply f(x) = ax² + bx + c to each x in nums.
• Return the transformed array sorted.

Constraints

• 1 <= nums.length <= 100
• -100 <= nums[i], a, b, c <= 100

Examples

• Input: nums = [-4,-2,2,4], a = 1, b = 3, c = 5
• Output: [3,9,15,33]
• f(-4) = 1*(-4)² + 3*(-4) + 5 = 16 - 12 + 5 = 9
• f(-2) = 1*(-2)² + 3*(-2) + 5 = 4 - 6 + 5 = 3
• f(2) = 1*2² + 3*2 + 5 = 4 + 6 + 5 = 15
• f(4) = 1*4² + 3*4 + 5 = 16 + 12 + 5 = 33
• Sorted: [3, 9, 15, 33]
• Input: nums = [-4,-2,2,4], a = -1, b = 3, c = 5
• Output: [-23,-5,1,7]
• f(-4) = -1*(-4)² + 3*(-4) + 5 = -16 - 12 + 5 = -23
• f(-2) = -1*(-2)² + 3*(-2) + 5 = -4 - 6 + 5 = -5
• f(2) = -1*2² + 3*2 + 5 = -4 + 6 + 5 = 7
• f(4) = -1*4² + 3*4 + 5 = -16 + 12 + 5 = 1
• Sorted: [-23, -5, 1, 7]

These show how the function shapes the output—let’s solve it!

Understanding the Problem: Transforming and Sorting

To tackle LeetCode 360 in Python, we need to: 1. Apply the quadratic function f(x) = ax² + bx + c to each element in the sorted array. 2. Sort the transformed values in ascending order. 3. Use the input’s sorted nature for optimization.

A basic approach might transform and sort directly, but we can do better since nums is sorted. We’ll use:

• Best Solution: Two pointers—O(n) time, O(1) space—leverages the quadratic’s shape.
• Alternative Solution: Simple sorting—O(n log n) time, O(n) space—straightforward but slower.

Let’s transform with the best solution!

Best Solution: Two Pointers

Why This Is the Best Solution

The two-pointer approach runs in O(n) time by exploiting the fact that nums is sorted and f(x) is a quadratic function, which is either a parabola opening up (a > 0), down (a < 0), or linear (a = 0). This means the transformed values form a U-shape or line, with extremes at the ends or middle. Two pointers let us build the sorted array directly—making it the fastest solution!

How It Works

Think of the quadratic’s shape:

• a > 0: Parabola opens up, max values at ends (e.g., -4 and 4), min near middle.
• a < 0: Parabola opens down, min values at ends, max near middle.
• a = 0: Linear, monotonic increase or decrease.
• Process:
• Use two pointers (left, right) on nums.
• Compare transformed values at ends, place largest/smallest in result based on a’s sign.
• Build result in correct order (ascending).

It’s like picking the edges of a curve and working inward!

Step-by-Step Example

For nums = [-4,-2,2,4], a = 1, b = 3, c = 5:

• Transform: f(x) = x² + 3x + 5.
• Shape: a=1 > 0, parabola opens up, max at ends.
• Pointers: left=0 (-4), right=3 (4), result=[0,0,0,0], index=3 (fill from right).
• Step 1:
• f(-4)=9, f(4)=33, 33 > 9, place 33 at index 3.
• Result: [0,0,0,33], right -= 1 (2), index -= 1 (2).
• Step 2:
• f(-4)=9, f(2)=15, 15 > 9, place 15 at index 2.
• Result: [0,0,15,33], right -= 1 (1), index -= 1 (1).
• Step 3:
• f(-4)=9, f(-2)=3, 9 > 3, place 9 at index 1.
• Result: [0,9,15,33], left += 1 (1), index -= 1 (0).
• Step 4:
• f(-2)=3, place 3 at index 0.
• Result: [3,9,15,33].

For nums = [-4,-2,2,4], a = -1, b = 3, c = 5:

• Shape: a=-1 < 0, parabola opens down, min at ends.
• Pointers: left=0, right=3, result=[0,0,0,0], index=0 (fill from left).
• Step 1:
• f(-4)=-23, f(4)=1, -23 < 1, place -23 at index 0.
• Result: [-23,0,0,0], left += 1 (1), index += 1 (1).
• Step 2:
• f(-2)=-5, f(4)=1, -5 < 1, place -5 at index 1.
• Result: [-23,-5,0,0], left += 1 (2), index += 1 (2).
• Step 3:
• f(2)=7, f(4)=1, 7 > 1, place 1 at index 2.
• Result: [-23,-5,1,0], right -= 1 (2), index += 1 (3).
• Step 4:
• f(2)=7, place 7 at index 3.
• Result: [-23,-5,1,7].

Code with Explanation

Here’s the Python code using two pointers:

Copy codeclass Solution:
    def sortTransformedArray(self, nums: List[int], a: int, b: int, c: int) -> List[int]:
        # Helper function to apply quadratic transformation
        def quad(x):
            return a * x * x + b * x + c

        n = len(nums)
        result = [0] * n
        left, right = 0, n - 1
        index = n - 1 if a >= 0 else 0  # Fill from right if a >= 0, left if a < 0

        while left <= right:
            left_val = quad(nums[left])
            right_val = quad(nums[right])

            if a >= 0:  # Parabola up or linear increasing
                if left_val >= right_val:
                    result[index] = left_val
                    left += 1
                else:
                    result[index] = right_val
                    right -= 1
                index -= 1
            else:  # Parabola down or linear decreasing
                if left_val <= right_val:
                    result[index] = left_val
                    left += 1
                else:
                    result[index] = right_val
                    right -= 1
                index += 1

        return result

Explanation

• Lines 3-5: quad: Helper function to compute ax² + bx + c for a given x.
• Lines 7-10: Setup:
• Create result array of size n.
• Set pointers: left at start, right at end.
• Set index: n-1 (end) if a≥0 (max at ends), 0 (start) if a<0 (min at ends).
• Lines 12-26: Two-pointer loop:
• Compute transformed values at left and right.
• a ≥ 0: Place larger value at end (descending index).
• a < 0: Place smaller value at start (ascending index).
• Update pointers and index accordingly.
• Line 28: Return sorted result.

• Time Complexity: O(n)—single pass through the array.
• Space Complexity: O(1)—result array is output, no extra space.

This is like shaping a parabola and picking extremes—super efficient!

Alternative Solution: Simple Sorting

Why an Alternative Approach?

The simple sorting solution is O(n log n) and easier to understand—transform each element and sort the result. It doesn’t leverage the input’s sorted nature but is a clear baseline approach—perfect for learning!

How It Works

• Transform: Apply f(x) to each element.
• Sort: Use Python’s built-in sort.
• Result: Return the sorted array.

Step-by-Step Example

For nums = [-4,-2,2,4], a = 1, b = 3, c = 5:

• Transform:
• f(-4)=9, f(-2)=3, f(2)=15, f(4)=33.
• Result: [9, 3, 15, 33].
• Sort: [3, 9, 15, 33].

For nums = [-4,-2,2,4], a = -1, b = 3, c = 5:

• Transform: [-23, -5, 7, 1].
• Sort: [-23, -5, 1, 7].

Code with Explanation

Copy codeclass Solution:
    def sortTransformedArray(self, nums: List[int], a: int, b: int, c: int) -> List[int]:
        # Transform each element
        result = [a * x * x + b * x + c for x in nums]
        # Sort the result
        return sorted(result)

Explanation

• Line 4: List comprehension applies the quadratic function to each x in nums.
• Line 6: sorted() returns the transformed array in ascending order.
• Time: O(n log n)—sorting dominates.
• Space: O(n)—new array for result.

It’s like a quick math-and-sort combo!

Comparing the Two Solutions

• Two Pointers (Best):
• Time: O(n)—linear pass.
• Space: O(1)—in-place result.
• Pros: Fast, leverages sorted input.
• Cons: Requires understanding parabola shape.
• Simple Sorting (Alternative):
• Time: O(n log n)—sorting.
• Space: O(n)—new array.
• Pros: Simple, no math insight needed.
• Cons: Slower, ignores input order.

Two pointers win for efficiency!

Additional Examples and Edge Cases

• nums=[1], a=0, b=1, c=0: [1] (linear).
• nums=[-1,1], a=0, b=0, c=5: [5,5] (constant).
• Large arrays: Two pointers scale better.

Both handle these, but pointers are faster.

Complexity Breakdown

• Two Pointers:
• Time: O(n).
• Space: O(1).
• Sorting:
• Time: O(n log n).
• Space: O(n).

Pointers excel for performance.

Key Takeaways

• Two Pointers: Use sorted input—fast and smart!
• Sorting: Simple transformation—easy to grasp!
• Quadratics: Math shapes solutions.
• Python Tip: List comprehensions rock—see [Python Basics](/python/basics).

Final Thoughts: Transform and Sort

LeetCode 360: Sort Transformed Array in Python is a math-meets-sorting challenge. The two-pointer solution is the efficiency champ, while sorting builds a solid base. Want more? Try LeetCode 75: Sort Colors or LeetCode 88: Merge Sorted Array. Ready to transform? Visit Solve LeetCode 360 on LeetCode and sort those numbers today!