Single pointer solution (in python)


  • 0
    D

    '''
    class Solution(object):
    def sortTransformedArray(self, nums, a, b, c):

        L=len(nums)
        if not L:
        	return None
        
        result=[a*nums[0]*nums[0]+b*nums[0]+c]
        p=0
        for i in xrange(1,L):
        	r = a*nums[i]*nums[i]+b*nums[i]+c
        	while (result[p]>r and p>0):
        		p-=1
        	while ( p<i and result[p]<r ):
        		p+=1
        	result.insert(p,r)
        
        return result
    

    '''
    This is still O(n) run time and it works for more general polynomial cases


Log in to reply
 

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