Squares of a Sorted Array

Introduction

Given a sorted array, squaring each element may disturb the order because negative numbers become positive.

The challenge is to return the squared values in sorted order efficiently, without using an extra sorting step.

Problem Statement

Given an integer array nums sorted in non-decreasing order,
return an array of the squares of each number, also sorted in non-decreasing order.

Examples

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

Example 2:
Input: [-7, -3, 2, 3, 11]
Output: [4, 9, 9, 49, 121]

Intuition

• The largest square comes from either:

  • The most negative number (left side)
  • The largest positive number (right side)

So we compare both ends.

Approach

Algorithm Steps

• Initialize:

  • left = 0
  • right = n - 1
  • Create result array of size n

• Fill result from end:

  • Compare nums[left]^2 and nums[right]^2
  • Place larger value at end

• Move pointers accordingly:

  • If left square is bigger → left++
  • Else → right--

Code (Python)

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

Step-by-Step Explanation

For [-4, -1, 0, 3, 10]:

• Compare |-4| and |10| → 100
• Compare |-4| and |3| → 16
• Compare |-1| and |3| → 9
• Continue…

Final → [0, 1, 9, 16, 100]

Complexity Analysis

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

Conclusion

This problem demonstrates the power of the two-pointer technique for optimizing problems involving sorted arrays.