> For the complete documentation index, see [llms.txt](https://protegejj.gitbook.io/algorithm-practice/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://protegejj.gitbook.io/algorithm-practice/leetcode/two-pointers/360-sort-transformed-array.md).

# 360 Sort Transformed Array

## 360. [Sort Transformed Array](https://leetcode.com/problems/sort-transformed-array/description/)

## 1. Question

Given a **sorted** array of integersnumsand integer valuesa,bandc. Apply a quadratic function of the form f(x) =ax2+bx+c to each elementxin 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]
```

## 2. Implementation

**(1) Two Pointers**

```java
class Solution {
    public int[] sortTransformedArray(int[] nums, int a, int b, int c) {
        int[] res = new int[nums.length];
        int index = a >= 0 ? nums.length - 1 : 0;
        int start = 0, end = nums.length - 1;

        while (start <= end) {
            int startNum = getNum(nums[start], a, b , c);
            int endNum = getNum(nums[end], a, b, c);

            if (a >= 0) {
                if (startNum > endNum) {
                    res[index] = startNum;
                    ++start;
                }
                else {
                    res[index] = endNum;
                    --end;
                }
                --index;
            }
            else {
                if (startNum < endNum) {
                    res[index] = startNum;
                    ++start;
                }
                else {
                    res[index] = endNum;
                    --end;
                }
                ++index;
            }
        }
        return res;
    }

    public int getNum(int x, int a, int b, int c) {
        return a * x * x + b * x + c;
    }
}
```

## 3. Time & Space Complexity

**Two Pointers**: 时间复杂度O(n), 空间复杂度O(n)