Problem description:

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:

1
2
Input: nums = [-4,-2,2,4], a = 1, b = 3, c = 5
Output: [3,9,15,33]

Example 2:

1
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.

Solution:

1
2
3
4
5
6
7
8
9
class Solution:
    def sortTransformedArray(self, nums: List[int], a: int, b: int, c: int) -> List[int]:
        res = []
        for i in range(len(nums)):
            n = a*nums[i]*nums[i] + b* nums[i] + c
            # print(n)
            index = bisect_left(res, n)
            res.insert(index, n)
        return res

time complexity: $O()$
space complexity: $O()$
reference:
related problem: