Squares of a Sorted Array

Squares of a Sorted Array

Problem

You’re given a sorted array (in non-decreasing order), which may include negative numbers.
The task is to return a new array of the squares of each number, also sorted.

---

Strategy

The first idea is simple: square each number and sort the result.

But that adds extra work.

What actually matters here is this:

• The array is sorted, but negative numbers become large when squared
• So the largest values after squaring will come from either end of the array

Because of that, I used two pointers:

• One at the beginning
• One at the end

At each step, I compare their absolute values and place the larger square at the end of the result array.

---

Code

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

        left, right = 0, n - 1
        pos = n - 1

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

        return result

---

Key Lines Explained

• abs(nums[left]) > abs(nums[right])
  This helps decide which number will produce the larger square.

• result[pos] = ...
  We place the largest square at the current position.

• left += 1 / right -= 1
  Move the pointer after using that value.

• pos -= 1
  Fill the result array from the end so it stays sorted.

---

Why This Works

Even though the original array is sorted, squaring changes the order because of negative values.

By comparing both ends, we always pick the largest square and place it correctly without needing to sort again.

---

Complexity

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

---

Final Note

This problem looks straightforward, but the real idea is noticing how the order changes after squaring.

Once that’s clear, the solution becomes more about using the structure of the array than doing extra work.