Squares of a Sorted Array

Problem Statement

You are given an integer array nums sorted in non-decreasing order.

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

Example 1

Input:

nums = [-4,-1,0,3,10]

Output:

[0,1,9,16,100]

Explanation:

After squaring:

[16,1,0,9,100]

After sorting:

[0,1,9,16,100]
Example 2

Input:

nums = [-7,-3,2,3,11]

Output:

[4,9,9,49,121]
Constraints
1 <= nums.length <= 10^4
-10^4 <= nums[i] <= 10^4
nums is already sorted
Important Observation

Even though the array is sorted, negative numbers become large after squaring.

Example:

-7 → 49
3 → 9

So simply squaring elements will not keep them sorted.

Efficient Approach (O(n) Time) – Two Pointer Technique

Instead of:

Squaring all elements
Sorting again (O(n log n))

We can solve it in O(n) using two pointers.

Key Idea
The largest square will come from either:
The most negative number (left side)
The largest positive number (right side)

So:

Use two pointers:
left = 0
right = n - 1
Compare absolute values
Insert larger square at the end of result array
Move pointers accordingly
Step-by-Step Algorithm
Create result array of size n
Initialize:
left = 0
right = n - 1
position = n - 1
While left <= right:
Compare abs(nums[left]) and abs(nums[right])
Insert larger square at result[position]
Move pointer
Decrease position
Return result
Python Implementation (O(n) Solution)
class Solution:
def sortedSquares(self, nums):
n = len(nums)
result = [0] * n

    left = 0
    right = n - 1
    position = n - 1

    while left <= right:
        if abs(nums[left]) > abs(nums[right]):
            result[position] = nums[left] * nums[left]
            left += 1
        else:
            result[position] = nums[right] * nums[right]
            right -= 1

        position -= 1

    return result

Dry Run Example

For:

nums = [-4,-1,0,3,10]

Step comparisons:

Left Right Larger Insert At
-4 10 100 last
-4 3 16 next
-1 3 9 next
-1 0 1 next
0 0 0 first

Final result:

[0,1,9,16,100]
Time and Space Complexity

Time Complexity: O(n)
Space Complexity: O(n) (for result array)