Squares of a Sorted Array

Intuition

The biggest square must sit at one of the two extremes, because the array is sorted and the most negative and most positive numbers are farthest from zero. By keeping one pointer at each end and always taking whichever end has the larger square, we can fill the output array from the back toward the front. This produces a fully sorted result in one pass without ever calling a sort routine.

Algorithm walkthrough

1. 1Allocate a result array of the same length and set a write position at its last index.
2. 2Place left at the start and right at the end of the input.
3. 3Compare the squares of nums[left] and nums[right].
4. 4Write the larger square at the current write position and move the pointer it came from inward.
5. 5Decrement the write position and repeat until the two pointers cross.

Implementation

from typing import List

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        n = len(nums)
        result = [0] * n
        left, right = 0, n - 1
        pos = n - 1
        while left <= right:
            left_sq = nums[left] * nums[left]
            right_sq = nums[right] * nums[right]
            if left_sq > right_sq:
                result[pos] = left_sq
                left += 1
            else:
                result[pos] = right_sq
                right -= 1
            pos -= 1
        return result