Solution Explanation: Sort Transformed Array

This problem requires sorting an array after applying a quadratic function to each element. A naive approach would involve applying the function to each element and then sorting the resulting array, resulting in O(n log n) time complexity due to the sorting step. However, a more efficient O(n) solution exists using two pointers.

Approach:

The key observation is that the quadratic function f(x) = ax² + bx + c creates a parabola. The parabola opens upwards if 'a' is positive and downwards if 'a' is negative. This allows us to efficiently determine the sorted order without explicitly sorting.

1. Two Pointers: We use two pointers, i and j, pointing to the beginning and end of the input array nums respectively.

2. Parabola Direction:

   • If a is positive (parabola opens upwards), the minimum value of the transformed array will be at either the beginning or the end of the transformed nums. The largest value will be towards the middle. We populate the result array from the end (k starts at n-1).
   • If a is negative (parabola opens downwards), the maximum value of the transformed array will be at either the beginning or the end of the transformed nums. The smallest value will be towards the middle. We populate the result array from the beginning (k starts at 0).

3. Comparison: In each iteration, we compare the transformed values of nums[i] and nums[j], i.e., f(nums[i]) and f(nums[j]). The comparison depends on whether a is positive or negative:

   • If a is positive, we select the larger value and place it in the result array at index k, decrementing k.
   • If a is negative, we select the smaller value and place it in the result array at index k, incrementing k.

4. Pointer Movement: After placing a value in the result array, we increment i or decrement j, depending on which value was chosen.

5. Iteration: We continue this process until i and j cross (i <= j).

Time Complexity: O(n) - We iterate through the input array once.

Space Complexity: O(n) - We use an additional array res to store the result.

Code Examples:

The code examples provided demonstrate this approach in multiple languages. They all follow the same logic:

1. A helper function f(x) calculates the quadratic function.
2. The main function initializes pointers i, j, and k based on the sign of a.
3. The while loop performs the comparison and placement of elements in the result array.

Example Walkthrough (a < 0):

Let's consider nums = [-4, -2, 2, 4], a = -1, b = 3, c = 5.

1. a is negative, so k starts at 0.
2. Iteration 1: f(-4) = -23, f(4) = 7. -23 < 7, so -23 is placed at res[0], i increments.
3. Iteration 2: f(-2) = -5, f(4) = 7. -5 < 7, so -5 is placed at res[1], i increments.
4. Iteration 3: f(2) = 1, f(4) = 7. 1 < 7, so 1 is placed at res[2], i increments.
5. Iteration 4: f(4) = 7. 7 is placed at res[3], j decrements. (i > j now)
6. Result: [-23, -5, 1, 7]

The code efficiently handles both positive and negative 'a' values by adjusting the starting index of k and the comparison operator used.