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

--

--

--

My homepage to record my thought processes for solving SQL and Algorithm questions

Recommended from Medium

A Guide to creating an API Endpoint with Django Rest Framework and Django Filters with PostgreSQL

TryHackMe: GLITCH — Beginner Friendly (detailed)

REST and Spring Boot: Automating and Simplifying Web Development: Part 1

Vera x Galaxy Guide攻略

What is coming with Dotty?

Flattening the IT expense curves and saving your business from peaks in CapEx costs

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Jen-Li Chen

Jen-Li Chen

In love with telling stories with data

More from Medium

Leetcode Q227. Basic Calculator II (Q219)

LeetCode 238 — Product of Array Except Self

Search in Rotated Sorted Array — Leetcode Python

Solving The Coding Question From Amazon Interview