Algorithm|List|Squares of a Sorted Array

From 977. Squares of a Sorted Array

Description

Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.

Solution

Notice that there could be negative values in the list, so it’s possible minimal number in the original list could be the maximal one.

But we could find out that the maximal value is either in the left side or the right side, it cannot be in the middle. So we use two pointers method.

Pointer i point to the initial position, pointer j point to the end position.

 def sortedSquares(self, nums: List[int]) -> List[int]:
        n = len(nums)
        i,j,k = 0,n - 1,n - 1
        ans = [-1] * n
        while i <= j:
            lm = nums[i] ** 2
            rm = nums[j] ** 2
            if lm > rm:
                ans[k] = lm
                i += 1
            else:
                ans[k] = rm
                j -= 1
            k -= 1
        return ans