Squares of a Sorted Array

1. Squares of a Sorted Array Problem Statement

We are given a sorted array in non-decreasing order (may contain negative numbers).
We need to return an array of the squares of each number, also sorted in non-decreasing order.

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

If we simply square the numbers:

[-4, -1, 0, 3, 10]
→ [16, 1, 0, 9, 100]

This is not sorted anymore because negative numbers become large after squaring.

So we must return a sorted squared array.

Approach 1: Square and Sort (Simple Method)
Steps

Square each element

Sort the array

Return result

Python Code
def sortedSquares(nums):
result = []

for num in nums:
    result.append(num * num)

result.sort()
return result

print(sortedSquares([-4,-1,0,3,10]))
Complexity
Type Complexity
Time O(n log n)
Space O(n)

This works but is not optimal.

Approach 2: Two Pointer Method (Optimal O(n))
Idea

Since the array is already sorted:

The largest square will come from either:

Leftmost negative number

Rightmost positive number

So we:

Use two pointers

Compare squares

Fill result array from the end

Steps

Create result array

Left pointer at start

Right pointer at end

Compare squares

Place larger square at end of result

Move pointer

Repeat

Python Code
def sortedSquares(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

print(sortedSquares([-4,-1,0,3,10]))
Example Walkthrough
nums = [-4, -1, 0, 3, 10]

Compare:
16 vs 100 → put 100
16 vs 9 → put 16
1 vs 9 → put 9
1 vs 0 → put 1
0 → put 0

Result = [0,1,9,16,100]
Complexity Comparison
Approach Time Space
Square + Sort O(n log n) O(n)
Two Pointer O(n) O(n)

Best Approach → Two Pointer Method

Conclusion

This problem teaches an important concept:

When array is sorted

Use Two Pointer Technique

Compare from both ends

Fill result from back

This reduces time complexity from O(n log n) → O(n).

Key Concepts Learned

Two pointer technique

Sorted array manipulation

Square transformation logic

Time complexity optimization