Sort Transformed Array

LintCode Q 906 - Sort Transformed Array

Given a sorted array of integers nums and integer values a, b and c. Apply a quadratic 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.

Example1
Input: nums = [-4, -2, 2, 4], a = 1, b = 3, c = 5 ; Output: [3, 9, 15, 33]

Example2
Input: nums = [-4, -2, 2, 4], a = -1, b = 3, c = 5 ; Output: [-23, -5, 1, 7]

Notice: Expected time complexity: O(n)

Solution

Solution : Two Pointers

Code:

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

	int left = 0, right = nums.length - 1;
	int index = 0;
	int[] res = new int[nums.length];

	if (a >= 0) index = right;

	while (right < nums.length) {
		int l = getNumber(nums[left], a, b, c);
		int r = getNumber(nums[right], a, b, c);

		if (a >= 0) {
			if (l >= r) {
				res[index--] = l; left++;
			} else {
				res[index--] = r; right--;
			}
		} else {
			if (l <= r) {
				res[index++] = l; left++;
			} else {
				res[index++] = r; right--;
			}
		}
	}

	return res;
}

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