Problem: 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.
Expected time complexity: O(n)
Example:
Input: nums = [-4,-2,2,4], a = 1, b = 3, c = 5 Output: [3,9,15,33]
Input: nums = [-4,-2,2,4], a = -1, b = 3, c = 5 Output: [-23,-5,1,7]
Approach: If you see ax^2 + bx + c forms a parabola. We know that ax 2 + bx + c, if a>0, the parabola opens up, that means The value at both ends is larger than the middle which indicates that we will get max value with either x = nums[0] or x = nums[n-1] and if a<0, the parabola opens downward, and the value at both ends is smaller than the middle which gives us hind that we will get minimum value at x = nums[0] or x = nums[n-1].
When a=0, it is a straight-line method, which is monotonically increasing or decreasing which in our case is increasing.
That's all!
Implementation in C#:
public int[] SortTransformedArray(int[] nums, int a, int b, int c)
{
int length = nums?.Length ?? 0;
if (length == 0)
{
return new int[] {};
}
if (length == 1)
{
return new int[] { this.ParabolaFunction(nums[0], a, b, c) };
}
int low = 0, high = length - 1;
int writeIndex = a >= 0 ? length - 1 : 0;
int[] result = new int[length];
while (low <= high)
{
int lowValue = this.ParabolaFunction(nums[low], a, b, c);
int highValue = this.ParabolaFunction(nums[high], a, b, c);
if (a >= 0)
{
if (lowValue < highValue)
{
result[writeIndex] = highValue;
--high;
}
else
{
result[writeIndex] = lowValue;
++low;
}
--writeIndex;
}
else
{
if (lowValue < highValue)
{
result[writeIndex] = lowValue;
++low;
}
else
{
result[writeIndex] = highValue;
--high;
}
++writeIndex;
}
}
return result;
}
private int ParabolaFunction(int x, int a, int b, int c)
{
return a * x * x + b * x + c;
}
Complexity: O(n)
No comments:
Post a Comment