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.

Code:

def sortedSquares(self, nums: List[int]) -> List[int]:
        n = len(nums)
        res = [0] * n
        left, right = 0, n - 1
        i = n - 1  # Fill from end

        while left <= right:
            if abs(nums[left]) > abs(nums[right]):
                res[i] = nums[left] ** 2
                left += 1
            else:
                res[i] = nums[right] ** 2
                right -= 1
            i -= 1

        return res

Efficiency:

Time Complexity: O(n)

Space Complexity: O(n)

Test:

nums = [-4,-1,0,3,10]
print(sortedSquares(nums))#[0,1,9,16,100]

nums = [-7,-3,2,3,11]
print(sortedSquares(nums))#[4,9,9,49,121]