Squares of a Sorted Array

Problem Statement: here

PS Goal:
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:

def sortedSquares(nums):
    n = len(nums)
    result = [0] * n
    left, right = 0, n - 1
    pos = n - 1
    while left <= right:
        if abs(nums[left]) > abs(nums[right]):
            result[pos] = nums[left] * nums[left]
            left += 1
        else:
            result[pos] = nums[right] * nums[right]
            right -= 1
        pos -= 1
    return result

We are given a sorted array, but since it has negative numbers, squaring them can mess up the order. For example, a big negative number becomes a big positive after squaring. So instead of squaring everything and sorting again, we use two pointers. One pointer at the start and one at the end. The largest square will always come from whichever side has the bigger absolute value. So we compare both ends, square the bigger one, and place it at the end of the result array. Then we move that pointer inward. We keep filling the result from the back and move towards the front. This way we get a sorted squared array without doing an extra sort.