Squares of a Sorted Array Using Two Pointers

Problem Statement:
Given a sorted array of integers, return a new array containing the squares of each number, also sorted in non-decreasing order.

Example:
Input: [-4, -1, 0, 3, 10]
Output: [0, 1, 9, 16, 100]

Approach:
We use the two-pointer technique. Since the largest square can come from either the leftmost or rightmost element, we compare both and place the larger square at the end of the result array.

Code:

def sortedSquares(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] ** 2
        left += 1
    else:
        result[pos] = nums[right] ** 2
        right -= 1
    pos -= 1

return result

Explanation:
The algorithm compares the absolute values from both ends and fills the result array from the back, ensuring sorted order.

Time Complexity:
O(n), single pass

Space Complexity:
O(n), for result array