Leetcode

360. Sort Transformed Array

Given a sorted integer array nums and three integers a, b and c, apply a quadratic function of the form f(x) = ax2 + bx + c to each element nums[i] in the array, and return the array in a sorted order.

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]

Constraints:

• 1 <= nums.length <= 200
• -100 <= nums[i], a, b, c <= 100
• nums is sorted in ascending order.

Follow up: Could you solve it in O(n) time?

Solution(Python3):

# two pointers
class Solution:
  def sortTransformedArray(self, nums: List[int], a: int, b: int, c: int) -> List[int]:
          nums = [x*x*a + x* b + c for x in nums]
          ret = [0] * len(nums)
          p1, p2 = 0, len(nums) - 1
          i, d = (p1, 1) if a < 0 else (p2, -1) # coefficients 
          while p1 <= p2:
              if nums[p1] * -d > nums[p2] * -d: # return a sorted
                  ret[i] = nums[p1]
                  p1 += 1
              else:
                  ret[i] = nums[p2]
                  p2 -= 1
              i += d
          return ret

Complexity Analysis:

Time: O(n), because two pointers traverse the array once

Space: O(n)

Link