CA 18 - Squares of a Sorted Array

Problem

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

Output

Example 1
Output: [0, 1, 9, 16, 100]
Example 2
Output: [4, 9, 9, 49, 121]

My Approach

To solve this problem, I used the two-pointer technique.

I place one pointer at the beginning and one at the end of the array.

I compare the absolute values of both ends:

The larger absolute value will produce the larger square
I place that square at the end of the result array

Then I move the corresponding pointer inward.

I continue this process until all elements are processed.

This works because the largest squares come from the largest absolute values, which are located at the ends of the array.

This approach is efficient because:

It requires only one traversal
It uses linear extra space for the result
Code

def sorted_squares(nums):
    n = len(nums)
    result = [0] * n
    left = 0
    right = 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