LeetCode 360 - Sort Transformed Array

The problem gives us a sorted integer array nums and a quadratic transformation function: We must apply this function to every element in the array and return the transformed values in sorted order.

leetcodemediumarraymathtwo-pointerssorting

LeetCode Problem 360

Difficulty: 🟡 Medium
Topics: Array, Math, Two Pointers, Sorting

Solution

Problem Understanding

The problem gives us a sorted integer array nums and a quadratic transformation function:

$$f(x) = ax^2 + bx + c$$

We must apply this function to every element in the array and return the transformed values in sorted order.

The important detail is that the original array is already sorted in ascending order, but after applying a quadratic function, the resulting values are not guaranteed to remain sorted. A quadratic function can bend upward or downward depending on the value of a, so the transformed sequence may become unordered even if the input was ordered.

For example, consider:

$$f(x) = x^2$$

Applying this to:

[-4, -2, 2, 4]

produces:

[16, 4, 4, 16]

which is not sorted.

The task is therefore not just to transform the numbers, but also to efficiently produce the transformed values in sorted order.

The constraints are relatively small:

  • 1 <= nums.length <= 200
  • Values range from -100 to 100

A brute force solution would easily pass because the array size is small. However, the follow up explicitly asks for an O(n) solution, which means we should exploit properties of the quadratic function and the fact that the input array is already sorted.

Several edge cases are important:

  • a > 0, the parabola opens upward, meaning large values appear near the ends of the input range.
  • a < 0, the parabola opens downward, meaning small values appear near the ends.
  • a == 0, the function becomes linear.
  • Duplicate transformed values may occur.
  • Negative and positive inputs may map to the same transformed value because quadratic functions are symmetric around their vertex.

Understanding the shape of the parabola is the key insight that enables the optimal solution.

Approaches

Brute Force Approach

The most direct solution is:

  1. Apply the quadratic function to every number.
  2. Store all transformed values in a new array.
  3. Sort the resulting array.
  4. Return the sorted result.

This works because sorting guarantees the final order is correct regardless of how the transformation changes the sequence.

For example:

nums = [-4, -2, 2, 4]
f(x) = x^2 + 3x + 5

Transforming gives:

[9, 3, 15, 33]

Sorting produces:

[3, 9, 15, 33]

The main drawback is the sorting step, which costs O(n log n) time.

Optimal Two Pointer Approach

The key observation is that a quadratic function forms a parabola.

When a > 0, the parabola opens upward:

  • The largest transformed values occur at the ends of the sorted input array.
  • The smallest transformed values occur near the vertex.

When a < 0, the parabola opens downward:

  • The smallest transformed values occur at the ends.
  • The largest values occur near the vertex.

Since the input array is already sorted, the transformed values at the left and right ends can be compared directly. This allows us to use a two pointer technique similar to merging sorted arrays.

The strategy is:

  • Use one pointer at the beginning.
  • Use another pointer at the end.
  • Compare transformed values from both sides.
  • Place the appropriate value into the result array.
  • Move inward.

If a > 0, we fill the result from the back because the largest values appear first.

If a < 0, we fill from the front because the smallest values appear first.

This avoids sorting entirely and achieves linear time complexity.

Approach Time Complexity Space Complexity Notes
Brute Force O(n log n) O(n) Transform all values, then sort
Optimal O(n) O(n) Uses parabola properties and two pointers

Algorithm Walkthrough

Optimal Two Pointer Algorithm

  1. Define a helper function to compute the quadratic transformation.

For any value x, compute:

$f(x)=ax^2+bx+c$$a$$b$$c$ .graphable-function-chartjs { position: relative; overflow: hidden; touch-action: none; } .graphable-function-chartjs-tooltip { position: absolute; z-index: 1; border-radius: 9px; background: rgb(0 0 0 / 90%); color: white; font-size: 11px; font-weight: 600; line-height: 14px; padding: 6px 12px; text-align: center; white-space: nowrap; pointer-events: none; } .graphable-function-chartjs-guide { position: absolute; top: 0; bottom: 0; border-left: 1px dashed var(--border-heavy); pointer-events: none; } .graphable-function-chartjs-hover-point { position: absolute; width: 8px; height: 8px; margin-left: -4px; margin-top: -4px; border: 1.5px solid white; border-radius: 9999px; background: black; pointer-events: none; } .graphable-function-chartjs-reset { position: absolute; left: 12px; bottom: 12px; display: inline-flex; align-items: center; justify-content: center; z-index: 2; width: 32px; height: 32px; border: 1px solid var(--border-light); border-radius: 9999px; background: var(--bg-primary); color: var(--text-primary); box-shadow: 0 2px 8px rgb(0 0 0 / 8%); padding: 0; transition: opacity 160ms ease, transform 160ms ease; } This isolates the transformation logic and avoids repeated code. 1. Initialize the result array. Create an array result of size n, where n is the length of nums. 2. Initialize two pointers. Set: - left = 0 - right = n - 1 These pointers examine the smallest and largest original values. 3. Decide fill direction based on the parabola shape. If a >= 0: - Larger transformed values appear at the ends. - Fill the result array from the back toward the front. If a < 0: - Smaller transformed values appear at the ends. - Fill the result array from the front toward the back. 4. Compare transformed values from both ends. Compute: - left_value = f(nums[left]) - right_value = f(nums[right]) Compare them. 5. Place the appropriate value into the result. For upward opening parabolas (a >= 0): - Place the larger value into the current back position. For downward opening parabolas (a < 0): - Place the smaller value into the current front position. 6. Move pointers inward. If the left value was used: - Increment left Otherwise: - Decrement right 7. Continue until all positions are filled. The process ends when left > right. ### Why it works A quadratic function produces values that are monotonic on either side of its vertex. Since the input array is sorted, the extreme transformed values must appear at one of the ends of the current interval. For upward opening parabolas, the largest values are always at the ends, so repeatedly selecting the larger transformed endpoint and filling from the back preserves sorted order. For downward opening parabolas, the smallest values are always at the ends, so repeatedly selecting the smaller transformed endpoint and filling from the front preserves sorted order. Because every element is processed exactly once and inserted into its correct position, the final array is sorted. ## Python Solution python from typing import List class Solution: def sortTransformedArray( self, nums: List[int], a: int, b: int, c: int ) -> List[int]: def transform(x: int) -> int: return a * x * x + b * x + c n = len(nums) result = [0] * n left = 0 right = n - 1 if a >= 0: index = n - 1 while left <= right: left_value = transform(nums[left]) right_value = transform(nums[right]) if left_value > right_value: result[index] = left_value left += 1 else: result[index] = right_value right -= 1 index -= 1 else: index = 0 while left <= right: left_value = transform(nums[left]) right_value = transform(nums[right]) if left_value < right_value: result[index] = left_value left += 1 else: result[index] = right_value right -= 1 index += 1 return result The implementation begins by defining a helper function called transform. This computes the quadratic expression for a single input value. Next, the algorithm creates a result array of the same size as the input. This avoids repeated appends and allows direct placement into the correct sorted position. Two pointers are initialized: - left starts at the beginning - right starts at the end The code then branches based on whether a is nonnegative or negative. When a >= 0, the parabola opens upward. The largest transformed values appear near the edges of the input interval, so the algorithm fills the result array from right to left. When a < 0, the parabola opens downward. The smallest transformed values appear near the edges, so the algorithm fills from left to right. At each iteration, the transformed values from both ends are compared. The correct value is inserted into the current result position, and the corresponding pointer moves inward. Because every element is processed exactly once, the algorithm runs in linear time. ## Go Solution go func sortTransformedArray(nums []int, a int, b int, c int) []int { transform := func(x int) int { return a*x*x + b*x + c } n := len(nums) result := make([]int, n) left := 0 right := n - 1 if a >= 0 { index := n - 1 for left <= right { leftValue := transform(nums[left]) rightValue := transform(nums[right]) if leftValue > rightValue { result[index] = leftValue left++ } else { result[index] = rightValue right-- } index-- } } else { index := 0 for left <= right { leftValue := transform(nums[left]) rightValue := transform(nums[right]) if leftValue < rightValue { result[index] = leftValue left++ } else { result[index] = rightValue right-- } index++ } } return result } The Go implementation follows exactly the same logic as the Python version. A closure named transform computes the quadratic expression. Slices in Go already behave like dynamic array views, so the result is created using make([]int, n). Since the problem constraints are small, integer overflow is not a concern. The largest possible transformed value remains well within Go's integer range. The implementation uses explicit index variables rather than appending because the result must be filled from either the front or back depending on the parabola orientation. ## Worked Examples ### Example 1 Input: nums = [-4, -2, 2, 4] a = 1 b = 3 c = 5 Transformation:$$f(x)=x^2+3x+5$$ Since a > 0, the parabola opens upward, so we fill from the back.

Step left right f(left) f(right) Chosen Result
1 -4 4 9 33 33 [0,0,0,33]
2 -4 2 9 15 15 [0,0,15,33]
3 -4 -2 9 3 9 [0,9,15,33]
4 -2 -2 3 3 3 [3,9,15,33]
Final output: 
[3, 9, 15, 33]

Example 2

Input:

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

Transformation: $$f(x)=-x^2+3x+5$$ Since a < 0, the parabola opens downward, so we fill from the front.

Step left right f(left) f(right) Chosen Result
1 -4 4 -23 1 -23 [-23,0,0,0]
2 -2 4 -5 1 -5 [-23,-5,0,0]
3 2 4 7 1 1 [-23,-5,1,0]
4 2 2 7 7 7 [-23,-5,1,7]
Final output: 
[-23, -5, 1, 7]

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each element is processed exactly once
Space O(n) A separate result array is required
The algorithm performs a constant amount of work for each element in the input array. The two pointers move inward without revisiting elements, so the total runtime is linear.
The extra space comes from the output array. Aside from that, only a few variables are used.

Test Cases

from typing import List
class Solution:
    def sortTransformedArray(
        self,
        nums: List[int],
        a: int,
        b: int,
        c: int
    ) -> List[int]:
        def transform(x: int) -> int:
            return a * x * x + b * x + c
        n = len(nums)
        result = [0] * n
        left = 0
        right = n - 1
        if a >= 0:
            index = n - 1
            while left <= right:
                left_value = transform(nums[left])
                right_value = transform(nums[right])
                if left_value > right_value:
                    result[index] = left_value
                    left += 1
                else:
                    result[index] = right_value
                    right -= 1
                index -= 1
        else:
            index = 0
            while left <= right:
                left_value = transform(nums[left])
                right_value = transform(nums[right])
                if left_value < right_value:
                    result[index] = left_value
                    left += 1
                else:
                    result[index] = right_value
                    right -= 1
                index += 1
        return result
solution = Solution()
# Provided example with upward parabola
assert solution.sortTransformedArray(
    [-4, -2, 2, 4], 1, 3, 5
) == [3, 9, 15, 33]
# Provided example with downward parabola
assert solution.sortTransformedArray(
    [-4, -2, 2, 4], -1, 3, 5
) == [-23, -5, 1, 7]
# Linear increasing function
assert solution.sortTransformedArray(
    [1, 2, 3], 0, 2, 1
) == [3, 5, 7]
# Linear decreasing function
assert solution.sortTransformedArray(
    [1, 2, 3], 0, -2, 1
) == [-5, -3, -1]
# Single element array
assert solution.sortTransformedArray(
    [5], 1, 0, 0
) == [25]
# Duplicate transformed values
assert solution.sortTransformedArray(
    [-2, 0, 2], 1, 0, 0
) == [0, 4, 4]
# All negative inputs
assert solution.sortTransformedArray(
    [-5, -4, -3], 1, 0, 0
) == [9, 16, 25]
# Constant function
assert solution.sortTransformedArray(
    [-3, -1, 2], 0, 0, 7
) == [7, 7, 7]
# Mixed negative and positive values
assert solution.sortTransformedArray(
    [-3, -1, 0, 2, 5], 2, -1, 1
) == [1, 3, 3, 15, 46]
# Downward parabola with symmetric values
assert solution.sortTransformedArray(
    [-3, -1, 1, 3], -1, 0, 0
) == [-9, -9, -1, -1]
Test Why
Upward parabola example Validates filling from the back
Downward parabola example Validates filling from the front
Linear increasing function Tests a == 0 with positive slope
Linear decreasing function Tests a == 0 with negative slope
Single element array Smallest valid input
Duplicate transformed values Ensures duplicates are handled correctly
All negative inputs Verifies correctness with only negative numbers
Constant function Tests when every transformed value is identical
Mixed negative and positive values Validates general correctness
Symmetric downward parabola Tests mirrored quadratic outputs

Edge Cases

One important edge case occurs when a == 0. In this situation, the quadratic function becomes linear: $$f(x)=bx+c$$ A naive implementation that assumes a true parabola may behave incorrectly. The current solution handles this naturally because the two pointer logic still works. When b >= 0, transformed values increase with x. When b < 0, they decrease. Since the algorithm groups a == 0 together with a >= 0, the correct ordering is still produced. Another important edge case involves duplicate transformed values. Quadratic functions are symmetric around their vertex, so different inputs may produce the same output. For example:

f(-2) = f(2)

An incorrect implementation might mishandle equality comparisons or accidentally skip values. The current solution always inserts exactly one element per iteration and advances exactly one pointer, so duplicates are preserved correctly. A third edge case occurs when the array contains only one element. Some two pointer implementations accidentally assume at least two elements exist and may process the same element twice or terminate incorrectly. This solution uses the condition:

while left <= right

which guarantees the single remaining element is processed exactly once. Another subtle case occurs when all transformed values are identical, such as: $$f(x)=7$$ In this scenario, every comparison produces equality. The implementation still behaves correctly because either branch produces the same valid value, and the pointers continue progressing until completion.