Squares of a Sorted Array

Hi everyone!
Today I solved a nice problem where we need to return the squares of a sorted array in sorted order. At first it looks simple, but there’s a small twist!

Problem
Given a sorted array (can include negative numbers), return a new array of squares in sorted order.

Example:
Input: [-4, -1, 0, 3, 10]

Output: [0, 1, 9, 16, 100]

My Approach

At first, I thought:

Just square all elements and sort

But that would take O(n log n) time.

Then I noticed:
Negative numbers can become large after squaring
The largest square will be either at the start or end

So I used a two-pointer approach.

Logic

Use two pointers:
l at start
r at end
Compare squares of both ends
Place the larger square at the end of result array
Move pointers accordingly

Code (Python)
class Solution:
def sortedSquares(self, nums):
n = len(nums)
res = [0] * n
l, r = 0, n - 1

    for i in range(n - 1, -1, -1):
        if nums[l] * nums[l] > nums[r] * nums[r]:
            res[i] = nums[l] * nums[l]
            l += 1
        else:
            res[i] = nums[r] * nums[r]
            r -= 1

    return res

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

Key Insight
Even though the array is sorted, squaring changes the order.
Using two pointers helps us avoid sorting again.

What I Learned
Two-pointer technique is very powerful
Always think about optimizing sorting problems
Edge values can be important in arrays

Thanks for reading!
Feel free to share your thoughts or other approaches.