Sort Transformed Array - Leetcode Solution

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)

Constraints:

1. -10^4 <= nums[i] <= 10^4
2. a, b, c may be integers but the absolute value of a cannot be 0.
3. 1 <= nums.length <= 10^4

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

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

Solution:

This is a pretty straightforward problem. We have to generate a new array whose each element is the result of the quadratic function of the values in the input array.

To solve the problem, we will do the following steps:

1. Iterate over every element in nums and generate the corresponding result for the quadratic function i.e., ax^2 + bx + c and store it in a new array. Let's call this array res.

2. If the value of 'a' is positive, then the elements of the new array will be sorted in a mountain shape i.e., first increasing and then decreasing. In this case, we can use a two-pointer approach starting at the beginning and end of the res array. The idea is to compare the elements pointed by the two pointers and add the largest element to the sorted output array. After adding the element, we move the pointer to the left or right, depending on which element was added to the sorted output array. We continue this process until both pointers meet at a common point i.e., we have added all the elements of the res array to the sorted output array.

3. If the value of 'a' is negative, then the elements of the new array will be sorted in a valley shape i.e., first decreasing and then increasing. In this case, we can also use a two-pointer approach starting at the beginning and end of the res array. The idea is to compare the elements pointed by the two pointers and add the smallest element to the sorted output array. After adding the element, we move the pointer to the left or right, depending on which element was added to the sorted output array. We continue this process until both pointers meet at a common point i.e., we have added all the elements of the res array to the sorted output array.

Let's now go through the code for the same.

The Code will be:

class Solution {
public:
    vector<int> sortTransformedArray(vector<int>& nums, int a, int b, int c) {
        int n = nums.size(), i = 0, j = n - 1, index = (a >= 0 ? n - 1 : 0);
        vector<int> res(n);
        while (i <= j) {
            int x = quadratic(nums[i], a, b, c), y = quadratic(nums[j], a, b, c);
            if (a >= 0) {
                if (x >= y) {
                    res[index--] = x;
                    i++;
                }
                else {
                    res[index--] = y;
                    j--;
                }
            }
            else {
                if (x <= y) {
                    res[index++] = x;
                    i++;
                }
                else {
                    res[index++] = y;
                    j--;
                }
            }
        }
        return res;
    }
    
    int quadratic(int x, int a, int b, int c) {
        return a * x * x + b * x + c;
    }
};

Time Complexity: The time complexity of the solution is O(n) since we are iterating over each element of the input array only once, and we are using a two-pointer technique to compare and add the elements to the new sorted array in a single traversal.

Space Complexity: The space complexity of the solution is O(n) as we are creating an array of size n to store the results of the quadratic function.

1