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

Alberta Motor Association’s DevOps Journey

The SIEM and DevOps

Jenkins-SonarQube Integration

Talking with Robots about Architecture

Cloud Migration. How Hard Can It Be?

Blogging is the New Incentive to Learn Hard

Using the Unity Animation System

Arth-Task-7(How to share Storage on fly(Elasticity to DataNode)?)

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
Isabelle

Isabelle

In love with telling stories with data

More from Medium

Leetcode Q152. Maximum Product Subarray

Leetcode 290. Word Pattern

LeetCode 238 — Product of Array Except Self

[Leetcode] Combination Sum