Question

Formatted question description: https://leetcode.ca/all/360.html

 360	Sort Transformed Array

 Given a sorted array of integers nums and integer values a, b and c.
 Apply a function of the form f(x) = ax^2 + bx + c to each element x in the array.

 The returned array must be in sorted order.

 Expected time complexity: O(n)

 Example:

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

 Result: [3, 9, 15, 33]

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

 Result: [-23, -5, 1, 7]

Algorithm

This question uses a lot of high school mathematical knowledge about parabola. We know that for an equation f(x) = ax2 + bx + c,

If a>0, the opening of the parabola is upward, and the value at both ends is greater than the middle,
If a<0, the opening of the parabola faces downward, and the values at both ends are smaller than the middle.
When a=0, it is a straight line method, which is monotonically increasing or decreasing.

Then we can use this property to solve the problem. The title shows that the given array nums is ordered. If it is not ordered, I think it is difficult to have an O(n) solution. Because the input array is in order, we can discuss the situation according to a:

When a>0, it means that the value at both ends is greater than the value in the middle. At this time, we fill in from the result after res, and use two pointers to point to the beginning and end of the nums array respectively. The two numbers pointed to are parabolic At the end of the number, the larger of them is stored at the end of res, and then the pointer is moved to the middle, and the comparison process is repeated until the res is filled.
When a<0, it means that the value at both ends is smaller than the middle, then we fill in from the front of res and use two pointers to point to the beginning and the end of the nums array respectively. The two numbers pointed to are the numbers at both ends of the parabola. The smaller number among them is first stored at the beginning of res, and then the pointer moves to the middle, and the comparison process is repeated until all res is filled.
When a=0, the function is monotonically increasing or decreasing, then fill in from front to back and fill in from back to front can be done, we can combine this situation with a>0

Code

Java

public class Sort_Transformed_Array {

    public class Solution {

        private int calculate(int x, int a, int b, int c){
            return a*x*x + b*x + c;
        }

        public int[] sortTransformedArray(int[] nums, int a, int b, int c) {

            int result[] = new int[nums.length];
            int i = 0;
            int j = nums.length - 1;
            int index;

            if (a > 0) {
                index = nums.length - 1;
                while (i <= j) {
                    result[index--] = calculate(nums[i], a, b, c) > calculate(nums[j], a, b, c)
                                        ? calculate(nums[i++], a, b, c)
                                        : calculate(nums[j--], a, b, c);
                }
            } else {
                index = 0;
                while (i <= j) {
                    result[index++] = calculate(nums[i], a, b, c) < calculate(nums[j], a, b, c)
                                        ? calculate(nums[i++], a, b, c)
                                        : calculate(nums[j--], a, b, c);
                }
            }

            return result;
        }
    }
}

// OJ: https://leetcode.com/problems/sort-transformed-array/
// Time: O(N)
// Space: O(1)
class Solution {
private:
    int eval(int x, int a, int b, int c) {
        return a * x * x + b * x + c;
    }
public:
    vector<int> sortTransformedArray(vector<int>& nums, int a, int b, int c) {
        float mid = (float)-b / (2 * a);
        int j = lower_bound(nums.begin(), nums.end(), mid) - nums.begin();
        int i = j - 1, N = nums.size(), nil = a > 0 ? INT_MAX : INT_MIN;
        vector<int> ans(N);
        for (int k = 0; k < N; ++k) {
            int m = i >= 0 ? eval(nums[i], a, b, c) : nil;
            int n = j < N ? eval(nums[j], a, b, c) : nil;
            if (a > 0 ? m < n : n < m) {
                ans[k] = m;
                --i;
            } else {
                ans[k] = n;
                ++j;
            }
        }
        if (a < 0) reverse(ans.begin(), ans.end());
        return ans;
    }
};

# reverse() will not work: if (a < 0) reverse(ans.begin(), ans.end());
class Solution:
    def sortTransformedArray(
        self, nums: List[int], a: int, b: int, c: int
    ) -> List[int]:
        def f(x):
            return a * x * x + b * x + c

        n = len(nums)
        i, j, k = 0, n - 1, 0 if a < 0 else n - 1
        res = [0] * n
        while i <= j:
            v1, v2 = f(nums[i]), f(nums[j])
            if a < 0:
                if v1 <= v2:
                    res[k] = v1
                    i += 1
                else:
                    res[k] = v2
                    j -= 1
                k += 1
            else:
                if v1 >= v2:
                    res[k] = v1
                    i += 1
                else:
                    res[k] = v2
                    j -= 1
                k -= 1
        return res

############

class Solution(object):
  def sortTransformedArray(self, nums, a, b, c):
    """
    :type nums: List[int]
    :type a: int
    :type b: int
    :type c: int
    :rtype: List[int]
    """

    def f(x):
      return a * (x ** 2) + b * x + c

    if a == 0:
      if b >= 0:
        return [f(x) for x in nums]
      else:
        return [f(x) for x in reversed(nums)]

    mid = (-1.0) * b / (2.0 * a)
    up, down = [], []

    if a >= 0:
      for num in nums:
        if num >= mid:
          up.append(f(num))
        else:
          down.append(f(num))
      down.reverse()
    else:
      for num in nums:
        if num >= mid:
          down.append(f(num))
        else:
          up.append(f(num))
      down.reverse()

    res = []
    upIdx = 0
    downIdx = 0
    while upIdx < len(up) and downIdx < len(down):
      upTop = up[upIdx]
      downTop = down[downIdx]

      if upTop < downTop:
        res.append(upTop)
        upIdx += 1
      else:
        res.append(downTop)
        downIdx += 1
    if upIdx < len(up):
      res.extend(up[upIdx:len(up)])
    if downIdx < len(down):
      res.extend(down[downIdx:len(down)])
    return res

360 - Sort Transformed Array

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions