Skip to content

360. Sort Transformed Array

  • Time: $O(n)$
  • Space: $O(n)$
 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
class Solution {
 public:
  vector<int> sortTransformedArray(vector<int>& nums, int a, int b, int c) {
    const int n = nums.size();
    const bool upward = a > 0;
    vector<int> ans(n);
    vector<int> quad;

    for (const int num : nums)
      quad.push_back(f(num, a, b, c));

    int i = upward ? n - 1 : 0;
    for (int l = 0, r = n - 1; l <= r;)
      if (upward)  // is the maximum in the both ends
        ans[i--] = quad[l] > quad[r] ? quad[l++] : quad[r--];
      else  // is the minimum in the both ends
        ans[i++] = quad[l] < quad[r] ? quad[l++] : quad[r--];

    return ans;
  }

 private:
  // The concavity of f only depends on a's sign.
  int f(int x, int a, int b, int c) {
    return (a * x + b) * x + c;
  }
};

 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
class Solution {
  public int[] sortTransformedArray(int[] nums, int a, int b, int c) {
    final int n = nums.length;
    final boolean upward = a > 0;
    int[] ans = new int[n];
    int[] quad = new int[n];

    for (int i = 0; i < nums.length; ++i)
      quad[i] = f(nums[i], a, b, c);

    int i = upward ? n - 1 : 0;
    for (int l = 0, r = n - 1; l <= r;)
      if (upward) // is the maximum in the both ends
        ans[i--] = quad[l] > quad[r] ? quad[l++] : quad[r--];
      else // is the minimum in the both ends
        ans[i++] = quad[l] < quad[r] ? quad[l++] : quad[r--];

    return ans;
  }

  // The concavity of f only depends on a's sign.
  private int f(int x, int a, int b, int c) {
    return (a * x + b) * x + c;
  }
}

 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
class Solution:
  def sortTransformedArray(
      self,
      nums: list[int],
      a: int,
      b: int,
      c: int,
  ) -> list[int]:
    n = len(nums)
    upward = a > 0
    ans = [0] * n

    # The concavity of f only depends on a's sign.
    def f(x: int, a: int, b: int, c: int) -> int:
      return (a * x + b) * x + c

    quad = [f(num, a, b, c) for num in nums]

    i = n - 1 if upward else 0
    l = 0
    r = n - 1
    while l <= r:
      if upward:  # is the maximum in the both ends
        if quad[l] > quad[r]:
          ans[i] = quad[l]
          l += 1
        else:
          ans[i] = quad[r]
          r -= 1
        i -= 1
      else:  # is the minimum in the both ends
        if quad[l] < quad[r]:
          ans[i] = quad[l]
          l += 1
        else:
          ans[i] = quad[r]
          r -= 1
        i += 1

    return ans