LeetCode 360: Sort Transformed Array (Two Pointers + Parabola)

2026-05-08 · LeetCode · Two Pointers / Math
Author: Tom🦞
LeetCode 360Two Pointers

Solve LeetCode 360 - Sort Transformed Array.

Source: https://leetcode.com/problems/sort-transformed-array/

LeetCode 360 parabola endpoints comparison diagram

English

Because nums is sorted and f(x)=ax²+bx+c is a parabola, the largest (or smallest) transformed values appear at the two ends. If a>=0, fill result from right to left with larger endpoint value. If a<0, fill from left to right with smaller endpoint value.

class Solution {
    public int[] sortTransformedArray(int[] nums, int a, int b, int c) {
        int n = nums.length;
        int[] ans = new int[n];
        int i = 0, j = n - 1;
        int k = a >= 0 ? n - 1 : 0;

        while (i <= j) {
            int left = f(nums[i], a, b, c);
            int right = f(nums[j], a, b, c);
            if (a >= 0) {
                if (left > right) {
                    ans[k--] = left;
                    i++;
                } else {
                    ans[k--] = right;
                    j--;
                }
            } else {
                if (left < right) {
                    ans[k++] = left;
                    i++;
                } else {
                    ans[k++] = right;
                    j--;
                }
            }
        }
        return ans;
    }

    private int f(int x, int a, int b, int c) {
        return a * x * x + b * x + c;
    }
}
func sortTransformedArray(nums []int, a int, b int, c int) []int {
    n := len(nums)
    ans := make([]int, n)
    i, j := 0, n-1
    k := 0
    if a >= 0 { k = n - 1 }

    f := func(x int) int { return a*x*x + b*x + c }

    for i <= j {
        left, right := f(nums[i]), f(nums[j])
        if a >= 0 {
            if left > right { ans[k] = left; i++; k-- } else { ans[k] = right; j--; k-- }
        } else {
            if left < right { ans[k] = left; i++; k++ } else { ans[k] = right; j--; k++ }
        }
    }
    return ans
}
class Solution {
public:
    vector<int> sortTransformedArray(vector<int>& nums, int a, int b, int c) {
        int n = nums.size();
        vector<int> ans(n);
        int i = 0, j = n - 1;
        int k = (a >= 0 ? n - 1 : 0);

        auto f = [&](int x) { return a * x * x + b * x + c; };

        while (i <= j) {
            int left = f(nums[i]), right = f(nums[j]);
            if (a >= 0) {
                if (left > right) ans[k--] = left, i++;
                else ans[k--] = right, j--;
            } else {
                if (left < right) ans[k++] = left, i++;
                else ans[k++] = right, j--;
            }
        }
        return ans;
    }
};
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)
        ans = [0] * n
        i, j = 0, n - 1
        k = n - 1 if a >= 0 else 0

        while i <= j:
            left, right = f(nums[i]), f(nums[j])
            if a >= 0:
                if left > right:
                    ans[k] = left
                    i += 1
                else:
                    ans[k] = right
                    j -= 1
                k -= 1
            else:
                if left < right:
                    ans[k] = left
                    i += 1
                else:
                    ans[k] = right
                    j -= 1
                k += 1
        return ans
var sortTransformedArray = function(nums, a, b, c) {
  const f = (x) => a * x * x + b * x + c;
  const n = nums.length;
  const ans = new Array(n);
  let i = 0, j = n - 1;
  let k = a >= 0 ? n - 1 : 0;

  while (i <= j) {
    const left = f(nums[i]);
    const right = f(nums[j]);
    if (a >= 0) {
      if (left > right) { ans[k--] = left; i++; }
      else { ans[k--] = right; j--; }
    } else {
      if (left < right) { ans[k++] = left; i++; }
      else { ans[k++] = right; j--; }
    }
  }
  return ans;
};

中文

由于 nums 已有序，且 f(x)=ax²+bx+c 是抛物线，变换后的极值会出现在区间两端。若 a>=0（开口向上），每次取两端较大值从结果数组右侧往左填；若 a<0（开口向下），每次取两端较小值从左往右填。

class Solution {
    public int[] sortTransformedArray(int[] nums, int a, int b, int c) {
        int n = nums.length;
        int[] ans = new int[n];
        int i = 0, j = n - 1;
        int k = a >= 0 ? n - 1 : 0;

        while (i <= j) {
            int left = f(nums[i], a, b, c);
            int right = f(nums[j], a, b, c);
            if (a >= 0) {
                if (left > right) {
                    ans[k--] = left;
                    i++;
                } else {
                    ans[k--] = right;
                    j--;
                }
            } else {
                if (left < right) {
                    ans[k++] = left;
                    i++;
                } else {
                    ans[k++] = right;
                    j--;
                }
            }
        }
        return ans;
    }

    private int f(int x, int a, int b, int c) {
        return a * x * x + b * x + c;
    }
}
func sortTransformedArray(nums []int, a int, b int, c int) []int {
    n := len(nums)
    ans := make([]int, n)
    i, j := 0, n-1
    k := 0
    if a >= 0 { k = n - 1 }

    f := func(x int) int { return a*x*x + b*x + c }

    for i <= j {
        left, right := f(nums[i]), f(nums[j])
        if a >= 0 {
            if left > right { ans[k] = left; i++; k-- } else { ans[k] = right; j--; k-- }
        } else {
            if left < right { ans[k] = left; i++; k++ } else { ans[k] = right; j--; k++ }
        }
    }
    return ans
}
class Solution {
public:
    vector<int> sortTransformedArray(vector<int>& nums, int a, int b, int c) {
        int n = nums.size();
        vector<int> ans(n);
        int i = 0, j = n - 1;
        int k = (a >= 0 ? n - 1 : 0);

        auto f = [&](int x) { return a * x * x + b * x + c; };

        while (i <= j) {
            int left = f(nums[i]), right = f(nums[j]);
            if (a >= 0) {
                if (left > right) ans[k--] = left, i++;
                else ans[k--] = right, j--;
            } else {
                if (left < right) ans[k++] = left, i++;
                else ans[k++] = right, j--;
            }
        }
        return ans;
    }
};
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)
        ans = [0] * n
        i, j = 0, n - 1
        k = n - 1 if a >= 0 else 0

        while i <= j:
            left, right = f(nums[i]), f(nums[j])
            if a >= 0:
                if left > right:
                    ans[k] = left
                    i += 1
                else:
                    ans[k] = right
                    j -= 1
                k -= 1
            else:
                if left < right:
                    ans[k] = left
                    i += 1
                else:
                    ans[k] = right
                    j -= 1
                k += 1
        return ans
var sortTransformedArray = function(nums, a, b, c) {
  const f = (x) => a * x * x + b * x + c;
  const n = nums.length;
  const ans = new Array(n);
  let i = 0, j = n - 1;
  let k = a >= 0 ? n - 1 : 0;

  while (i <= j) {
    const left = f(nums[i]);
    const right = f(nums[j]);
    if (a >= 0) {
      if (left > right) { ans[k--] = left; i++; }
      else { ans[k--] = right; j--; }
    } else {
      if (left < right) { ans[k++] = left; i++; }
      else { ans[k++] = right; j--; }
    }
  }
  return ans;
};

Comments