Squares of a sorted array

Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.

Example 1:
Input: nums = [-4,-1,0,3,10]
Output: [0,1,9,16,100]
Explanation: After squaring, the array becomes [16,1,0,9,100].
After sorting, it becomes [0,1,9,16,100].

Example 2:
Input: nums = [-7,-3,2,3,11]
Output: [4,9,9,49,121]

Constraints:
1 <= nums.length <= 104
-104 <= nums[i] <= 104

Approach Used

The idea is simple:

1. Traverse the array
2. Square each element
3. Store the results in a new list
4. Sort the final list

Code Implementation

class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
result = []
for i in range(len(nums)):
result.append(nums[i] ** 2)
return sorted(result)

Example Walkthrough
Input
nums = [-4, -1, 0, 3, 10]

**Step 1: **Square each element
[16, 1, 0, 9, 100]

Step 2: Sort the result
[0, 1, 9, 16, 100]

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

Complexity Analysis

Time Complexity: O(n log n)
O(n) for squaring
O(n log n) for sorting
Space Complexity: O(n)
A new list is created to store squared values

Why This Works
Even though the input array is sorted, squaring negative numbers can disrupt the order.
For example:
Negative numbers become positive after squaring
Larger negative values produce larger squares

Sorting ensures the final result is in correct order.

Since the largest square will come from either end, we can fill the result array from the back.

This reduces time complexity to O(n).