Python O(n) Two-Pointers Solution


  • 6

    d is the increment of i.

    def sortTransformedArray(self, nums, a, b, c):
        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)
        while p1 <= p2:
            if nums[p1] * -d > nums[p2] * -d:
                ret[i] = nums[p1]
                p1 += 1
            else:
                ret[i] = nums[p2]
                p2 -=1
            i += d
        return ret

  • 0
    L

    @waigx Can you explain your reasoning for using d?


  • 0
    J

    @waigx This is a very succinct solution. I think it should receive a lot more votes. For those who wonder what it does, here is an explanation:

    If we plot the transformed array, it would form a parabola. If a > 0, the two ends will be higher than the center. So do a merge sort - move from both ends of the transformed array towards the center and if a > 0, choose the bigger element and put it at the end of the resulting array, i.e. fill the array from right to left. If a < 0, merge the elements from left to right.


Log in to reply
 

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