Squares of a Sorted Array in Python: Two Pointer O(n) Solution Explained

Problem Overview

The Squares of a Sorted Array problem provides a sorted integer array that may contain negative and positive numbers. The task is to return a new array consisting of the squares of each number, sorted in non-decreasing order.

Why the Naive Approach Is Not Optimal

A simple solution is to square every element and then sort the resulting array. While this works correctly, it results in a time complexity of O(n log n), which is not optimal for this problem.

Key Insight

Squaring the numbers breaks the original sorted order because large negative values can produce larger squares than positive values. However, the largest squared value will always come from one of the two ends of the array.

Optimal Approach: Two Pointers with Reverse Fill

To achieve an O(n) solution, we use the two-pointer technique along with a reverse write strategy. Two pointers are placed at the beginning and end of the array, and a third pointer is used to fill the result array from right to left.

Algorithm Steps

1. Initialize an output array with the same length as the input.
2. Set a left pointer at the start and a right pointer at the end.
3. Set a write pointer at the last index of the output array.
4. Compare the squares of the values at the left and right pointers. Place the larger square at the write pointer position.
5. Move the pointer that contributed the larger square.
6. Move the write pointer backward and repeat until the array is filled.

Python Implementation

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        n = len(nums)
        result = [0] * n

        l, r = 0, n - 1
        write = n - 1

        while l <= r:
            left_sq = nums[l] * nums[l]
            right_sq = nums[r] * nums[r]

            if right_sq > left_sq:
                result[write] = right_sq
                r -= 1
            else:
                result[write] = left_sq
                l += 1

            write -= 1

        return result
  

Why This Solution Works

At each step, the algorithm selects the largest possible square from the array’s extremes and places it at the correct position in the output array. Since each element is processed exactly once, the solution runs in linear time.

Complexity Analysis

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

Pattern Summary

This problem demonstrates a variation of the two-pointer pattern where decisions are made based on magnitude rather than equality. The reverse-fill technique ensures that the final array remains sorted without requiring an additional sorting step.