Squares of a Sorted Array

Squares of a Sorted Array

Problem

You’re given a sorted array that can include negative numbers.
The task is to return a new array of the squares of each number, also sorted.

---

Strategy

The straightforward way is to square every element and then sort the array.

But that takes extra time.

What made this problem interesting is noticing this:

• The array is sorted, but squaring negative numbers makes them large
• So the largest values after squaring will be at 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 decides which number will give the larger square.

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

• left += 1 / right -= 1
  Move the pointer depending on which value was used.

• pos -= 1
  Fill the result array from the end.

---

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 simple at first, but the follow-up changes how you approach it.

Instead of doing extra work, it becomes about using the structure of the array in a smarter way.