Squares of a Sorted Array

Introduction

When working with sorted arrays, problems often require maintaining order after performing operations. One such problem is squaring each element and returning the result in sorted order.

At first glance, it may seem simple, but handling negative numbers makes it interesting.

Problem Statement

Given a sorted array nums in non-decreasing order, return a new array containing 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]

Two-Pointer Approach

We use:

• left → start of array
• right → end of array
• Fill result from the end

Steps

1. Compare absolute values of nums[left] and nums[right]
2. Place the larger square at the end
3. Move the corresponding pointer
4. Repeat until done

Python Implementation

def sorted_squares(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

# Example usage
nums = [-4, -1, 0, 3, 10]
print(sorted_squares(nums))

Step-by-Step Example

For:

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

• Compare |-4| and |10| → 10 → place 100
• Compare |-4| and |3| → -4 → place 16
• Compare |-1| and |3| → 3 → place 9
• Compare |-1| and |0| → -1 → place 1
• Last → 0 → place 0

Final result: [0, 1, 9, 16, 100]

Key Points

• No need for sorting
• Uses two-pointer technique
• Efficient and optimal solution
• Common interview problem

Conclusion

The Squares of a Sorted Array problem shows how understanding the structure of data can lead to optimized solutions. Instead of sorting, we use a two-pointer approach to achieve linear time complexity.

This technique is widely useful in array-based problems and is important for mastering efficient algorithms.