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) = ax2 + 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]

Solution:

We have two pointers points to the two sides of the sorted array.

If a > 0, it is an open-upward parabola. The two sides are the largest. We insert from the end of the result array.

If a < 0, it is an open-downward parabola. The two sides are the smallest. We insert from the start of the result array.

If a == 0, it is monotonic increasing or decreasing. We merge it with the a < 0 case.

Thus, the time complexity is O(n) and the space complexity is O(n) as well.



Code:

public class Solution {
    public int[] sortTransformedArray(int[] nums, int a, int b, int c) {
        int[] result = new int[nums.length];
        int index = a > 0 ? nums.length - 1 : 0;
        int i = 0;
        int j = nums.length - 1;
        while (i <= j) {
            if (a > 0) {
                result[index--] = cal(nums[i], a, b, c) >= cal(nums[j], a, b, c) ? 
                                  cal(nums[i++], a, b, c) : cal(nums[j--], a, b, c);
            }
            else {
                result[index++] = cal(nums[i], a, b, c) <= cal(nums[j], a, b, c) ? 
                                  cal(nums[i++], a, b, c) : cal(nums[j--], a, b, c);
            }
        }
        return result;
    }
    
    public int cal(int x, int a, int b, int c) {
        return a * x * x + b * x + c;
    }
}