# LeetCode 977: Squares of a Sorted Array

## Problem Restatement

We are given an integer array `nums` sorted in non-decreasing order.

We need to return a new array containing the square of each number, also sorted in non-decreasing order.

The difficulty comes from negative numbers.

For example:

```python
nums = [-4, -1, 0, 3, 10]
```

If we square each value in the same order, we get:

```python
[16, 1, 0, 9, 100]
```

This result is not sorted.

The official constraints are `1 <= nums.length <= 10^4`, `-10^4 <= nums[i] <= 10^4`, and `nums` is sorted in non-decreasing order. The follow-up asks for an `O(n)` solution.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A sorted integer array `nums` |
| Output | A sorted array of squared values |
| Constraint | `nums` is already sorted in non-decreasing order |
| Goal | Return the squared values in non-decreasing order |

Function shape:

```python
def sortedSquares(nums: list[int]) -> list[int]:
    ...
```

## Examples

Example 1:

```python
nums = [-4, -1, 0, 3, 10]
```

Squaring each value gives:

```python
[16, 1, 0, 9, 100]
```

After sorting:

```python
[0, 1, 9, 16, 100]
```

Answer:

```python
[0, 1, 9, 16, 100]
```

Example 2:

```python
nums = [-7, -3, 2, 3, 11]
```

The squared values are:

```python
[49, 9, 4, 9, 121]
```

Sorted result:

```python
[4, 9, 9, 49, 121]
```

Answer:

```python
[4, 9, 9, 49, 121]
```

## First Thought: Square Then Sort

The simplest solution is to square every number, then sort the result.

```python
class Solution:
    def sortedSquares(self, nums: list[int]) -> list[int]:
        squares = []

        for num in nums:
            squares.append(num * num)

        squares.sort()
        return squares
```

This is easy to write and easy to understand.

It works because sorting fixes the order after squaring.

## Problem With Sorting Again

The array is already sorted.

Sorting the squared values costs:

```python
O(n log n)
```

The follow-up asks for an `O(n)` solution, so we should use the sorted structure of the input instead of sorting again.

## Key Insight

The largest square must come from one of the two ends of the array.

Why?

Because `nums` is sorted.

The left end may contain the most negative number.

The right end contains the largest positive number.

After squaring, a large negative value can become very large.

For example:

```python
-7 * -7 = 49
11 * 11 = 121
```

So at each step, compare the absolute values at both ends:

```python
abs(nums[left]) and abs(nums[right])
```

Whichever side has the larger absolute value produces the larger square.

We can fill the answer array from right to left.

## Algorithm

Create an answer array of the same length as `nums`.

Use three pointers:

| Pointer | Meaning |
|---|---|
| `left` | Start of the array |
| `right` | End of the array |
| `pos` | Current position to fill in the answer |

At each step:

1. Compare `abs(nums[left])` and `abs(nums[right])`.
2. Put the larger square at `answer[pos]`.
3. Move the pointer that was used.
4. Move `pos` one step left.

Because we fill from the end, the largest squares are placed first, and the final array remains sorted.

## Correctness

The input array is sorted in non-decreasing order.

At any point, all unused numbers are between `left` and `right`.

The largest square among the unused numbers must come from either `nums[left]` or `nums[right]`.

This is because the largest absolute value in a sorted interval is always at one of the two ends.

The algorithm compares these two values and writes the larger square into the last unfilled position of the answer array.

So each step places the largest remaining square into its final correct position.

After placing it, the corresponding pointer moves inward, removing that value from future consideration.

By repeating this process until all positions are filled, every squared value is placed in sorted order.

Therefore, the returned array is correct.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | Each element is processed once |
| Space | `O(n)` | The output array stores `n` squared values |

## Implementation

```python
class Solution:
    def sortedSquares(self, nums: list[int]) -> list[int]:
        n = len(nums)
        answer = [0] * n

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

        while left <= right:
            left_square = nums[left] * nums[left]
            right_square = nums[right] * nums[right]

            if left_square > right_square:
                answer[pos] = left_square
                left += 1
            else:
                answer[pos] = right_square
                right -= 1

            pos -= 1

        return answer
```

## Code Explanation

We create an output array:

```python
answer = [0] * n
```

This lets us place values directly into their final position.

We start one pointer at the left end and one pointer at the right end:

```python
left = 0
right = n - 1
```

The next largest square should go at the end of `answer`:

```python
pos = n - 1
```

The loop continues while there are still unused values:

```python
while left <= right:
```

At each step, square both candidates:

```python
left_square = nums[left] * nums[left]
right_square = nums[right] * nums[right]
```

If the left square is larger, place it at `answer[pos]`:

```python
answer[pos] = left_square
left += 1
```

Otherwise, place the right square:

```python
answer[pos] = right_square
right -= 1
```

Then move `pos` left:

```python
pos -= 1
```

When the loop ends, all squares have been placed in sorted order.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.sortedSquares([-4, -1, 0, 3, 10]) == [0, 1, 9, 16, 100]
    assert s.sortedSquares([-7, -3, 2, 3, 11]) == [4, 9, 9, 49, 121]
    assert s.sortedSquares([1, 2, 3]) == [1, 4, 9]
    assert s.sortedSquares([-3, -2, -1]) == [1, 4, 9]
    assert s.sortedSquares([0]) == [0]
    assert s.sortedSquares([-2, 0, 2]) == [0, 4, 4]

    print("all tests passed")

run_tests()
```

| Test | Expected | Why |
|---|---:|---|
| `[-4, -1, 0, 3, 10]` | `[0, 1, 9, 16, 100]` | Mixed negative and positive values |
| `[-7, -3, 2, 3, 11]` | `[4, 9, 9, 49, 121]` | Largest square comes from the right |
| `[1, 2, 3]` | `[1, 4, 9]` | Already non-negative |
| `[-3, -2, -1]` | `[1, 4, 9]` | All values are negative |
| `[0]` | `[0]` | Minimum length |
| `[-2, 0, 2]` | `[0, 4, 4]` | Duplicate square values |