leet-code/Java/360. Sort Transformed Array.java at master · awangdev/leet-code · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
M
tags: Math, TwoPointers
time: O(n)
space: O(n) storeresult

#### TwoPointers, Math
- Beingabletoanalysthea*x^2 + b*xgraphandfindthe `peak` or `valley`
- Mathbasics: x^2dominatestheoverallcurvesoitisuptoatodetermine:
 - `valley`: ifa < 0, bothsideswillbesmallandcenterwillbelarge. Prioritizelargervalue.
 - `peak`: ifa > 0, centerwillbesmallandbothsideswillbelarge. Prioritizesmallervalue.
 - startingindexbeing0orn-1, isdrivenby `a`

```
/*
Given a sorted array of integers nums and integer values a, b and c. Apply a quadratic function of the form f(x) = ax2 + bx + c to each element x in the array.

The returned array must be in sorted order.

Expected time complexity: O(n)

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]
*/

/*
- Math basics: x^2 dominates the overall curve so it is up to a to determine:
 - if a < 0, both sides will be small and center will be large. Prioritize larger value.
 - if a > 0, center will be small and both sides will be large. Prioritize smaller value.
 - starting index being 0 or n-1, is driven by a
*/
classSolution {
inta, b, c;
publicint[] sortTransformedArray(int[] nums, inta, intb, intc) {
this.a = a;
this.b = b;
this.c = c;
intn = nums.length, i = 0, j = n - 1;
int[] rst = newint[n];
intindex = a >= 0 ? n - 1 : 0;

while (i <= j) {
intleft = calc(nums[i]), right = calc(nums[j]);
if (a >= 0) {
rst[index--] = left >= right ? calc(nums[i++]) : calc(nums[j--]);
 } else { // a < 0
rst[index++] = left >= right ? calc(nums[j--]) : calc(nums[i++]);
 }
 }

returnrst;
 }

privateintcalc(intx) {
returna * x * x + b * x + c;
 }
}
```