Square of Sorted Array

Easy

📘 Problem Statement

Given a sorted array of integers (can include negatives), return a new array of the squares of each number, sorted in non-decreasing order.

---

🔍 Example

Example 1:

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

Output: [0, 1, 9, 16, 100]

---

🧠 Key Insight

• Squaring negative numbers turns them positive.
• So largest square can come from either left end (most negative) or right end (largest positive).
• squaring each number in array and then sorting will work and is a trivial solution.
• We’ll use two pointers from both ends and fill output from back to front

🛠️ Solution

def sorted_squares(nums):
    n = len(nums)
    result = [0] * n  # placeholder for results
    left, right = 0, n - 1
    pos = n - 1  # fill from end

    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

🕒 Time Complexity: \(O(n)\)

📦 Space Complexity: \(O(n)\)

We touch each element once and fill the result array efficiently.