CA 18 - Squares of a Sorted Array

Problem
Squares of a Sorted Array
You are given a sorted array nums[] in non-decreasing order.
Your task is to return a new array containing the squares of each number, also sorted in non-decreasing order.

Input: [-4, -1, 0, 3, 10] → Output: [0, 1, 9, 16, 100]
Input: [-7, -3, 2, 3, 11] → Output: [4, 9, 9, 49, 121]

Approach

Even though the array is sorted, squaring negative numbers can disturb the order.
So instead of sorting again, we use a two-pointer approach.

Steps:

• Initialize two pointers:
• left at the start
• right at the end
• Compare squares of both ends
• Place the larger square at the end of a result array
• Move pointers accordingly and repeat

This works because the largest square will always come from either end.

Complexity:
Time Complexity: O(n)
Space Complexity: O(n)

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] ** 2
            left += 1
        else:
            result[pos] = nums[right] ** 2
            right -= 1
        pos -= 1
    return result
nums = [-4, -1, 0, 3, 10]
print(sortedSquares(nums))