Squares of sorted array

Our task is to create a new array where each element is the square of the corresponding element in the original array, and the resulting array must also be sorted in non-decreasing order.

sample i/p and o/p
Input:
nums = [-4,-1,0,3,10]

Output:
[0,1,9,16,100]

Explanation:
after squaring -> [16,1,0,9,100]
after sorting -> [0,1,9,16,100]

how to approach the solution

I first thought ->
"just square all elements and sort the array"
but sorting again takes extra time
so I thought, since the array is already sorted, can we use that?

key observation
-> negative numbers when squared become positive
-> largest square will be from either:

left side (big negative)
right side (big positive)

how it works

use two pointers
left -> start
right -> end

compare square of both
put the larger square at the end of result array

step by step

nums = [-4,-1,0,3,10]

left = -4 -> square = 16  
right = 10 -> square = 100 -> take 100  

left = -4 -> 16  
right = 3 ->9 -> take 16  

left = -1 -> 1  
right = 3 -> 9 -> take 9 

final result:

[0,1,9,16,100]

Approach

use two pointers
compare squares
fill result array from end

Algorithm

  def sortedSquares(self, nums):
        n = len(nums)
        result = [0] * n

        left = 0
        right = n - 1
        pos = n - 1

        while left <= right:
            if nums[left]**2 > nums[right]**2:
                result[pos] = nums[left]**2
                left += 1
            else:
                result[pos] = nums[right]**2
                right -= 1

            pos -= 1

        return result**