SQUARES OF SORTED ARRAY

How I Understood Squares of a Sorted Array (LeetCode 977)
When I first saw this problem, it looked straightforward: square all numbers and sort them.
But I realized that we can do it more efficiently because the array is already sorted, even if it contains negative numbers.

Problem
Given a sorted array, return a new array containing the squares of each number, also sorted in non-decreasing order.
Example:
Python
nums = [-4, -1, 0, 3, 10]

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

Python
nums = [-7, -3, 2, 3, 11]

Output: [4, 9, 9, 49, 121]

** What I Noticed**
Squaring negative numbers can make them larger than positive numbers, so a simple map-and-sort approach works but is not optimal.
Instead, I noticed:
The largest squared number will be either at the start or the end of the array.
Using two pointers, we can fill the result array from back to front.

What Helped Me
Using two pointers made this problem very clear:
Initialize pointers: left = 0, right = n - 1
Compare absolute values of nums[left] and nums[right]
Place the larger square at the end of the result array
Move the corresponding pointer (left or right)
Repeat until the array is filled
This avoids sorting and keeps O(n) time complexity.

** Code (Python)**
Python
from typing import List

class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
n = len(nums)
res = [0] * n # Result array to store squared values

    left = 0
    right = n - 1

    # Fill the result array from back to front
    for i in range(n - 1, -1, -1):
        if abs(nums[left]) > abs(nums[right]):
            res[i] = nums[left] ** 2
            left += 1
        else:
            res[i] = nums[right] ** 2
            right -= 1

    return res

Example Usage
Python
nums = [-4, -1, 0, 3, 10]
solution = Solution()
print(solution.sortedSquares(nums))
Output:
Plain text
[0, 1, 9, 16, 100]

Complexity

Time: O(n) — iterate through the array once
Space: O(n) — result array of same size

** What I Learned**
This problem is less about squaring numbers and more about clever use of pointers:
Compare absolute values at both ends
Place the largest squares at the end
Fill the array efficiently without sorting
Two pointers are very powerful for sorted arrays.

** Final Thought**
At first, squaring and sorting seemed simple but inefficient.
Once I realized:
“The largest square is at either end; use two pointers to fill from back”
…it became a clean O(n) solution.
This is a great example of optimizing for sorted arrays.