Python solution with detailed explanation


  • 0
    G

    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
    

Log in to reply
 

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