# Python solution with detailed explanation

• Solutions

Math Properties

1. Review properties of a parabola. What is the shape of the parabola when a > 0 and a = 0 and a < 0? Local minima x = -b/2a for a > 0 and local maxima x = -b/2a for a < 0. Straight line for a = 0. Using these ideas, split the array into two sorted halves and merge them.
https://discuss.leetcode.com/topic/128/sort-transformed-array/3
``````class Solution(object):
def merge(self, a1, a2):
result = []
N,M = len(a1), len(a2)
i,j = 0,0
while i < N or j < M:
if i == N:
result.append(a2[j])
j += 1
elif j == M:
result.append(a1[i])
i += 1
elif a1[i] < a2[j]:
result.append(a1[i])
i += 1
else:
result.append(a2[j])
j += 1
return result

def evaluate(self, x, a, b, c):
return a*x*x + b*x + c

def sortTransformedArray(self, nums, a, b, c):
"""
:type nums: List[int]
:type a: int
:type b: int
:type c: int
:rtype: List[int]
"""
if a != 0:
a1, a2, pt = [], [], (b*-1.0)/(2*a)
for n in nums:
if n < pt:
a1.append(self.evaluate(n, a, b, c))
else:
a2.append(self.evaluate(n, a, b, c))
if a > 0:
a1.reverse()
return self.merge(a1, a2)
elif a < 0:
a2.reverse()
return self.merge(a1, a2)
else:
transformed = [self.evaluate(n, a, b, c) for n in nums]
if b < 0:
transformed.reverse()
return transformed
``````

Two Pointer

1. Use 2 pointers start and end.
2. If a > 0, then largest number is at end point. If a < 0, then smallest number is at end points.
https://discuss.leetcode.com/topic/48424/java-o-n-incredibly-short-yet-easy-to-understand-ac-solution/2
``````class Solution(object):
def evaluate(self, x, a, b, c):
return a*x*x + b*x + c

def sortTransformedArray(self, nums, a, b, c):
"""
:type nums: List[int]
:type a: int
:type b: int
:type c: int
:rtype: List[int]
"""
result = [None]*len(nums)
if a > 0:
s,e = 0, len(nums)-1
i = len(nums)-1
while s <= e:
snum, enum = self.evaluate(nums[s], a, b, c), self.evaluate(nums[e], a, b, c)
if snum >= enum:
s, result[i] = s + 1, snum
else:
e, result[i] = e-1, enum
i -= 1
else:
s,e = 0, len(nums)-1
i = 0
while s <= e:
snum, enum = self.evaluate(nums[s], a, b, c), self.evaluate(nums[e], a, b, c)
if snum <= enum:
s, result[i] = s + 1, snum
else:
e, result[i] = e-1, enum
i += 1
return result
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.