036. Sorted Squares

Why this mechanism works

Squaring is not monotone across zero, but the largest absolute value of a sorted interval occurs at an endpoint. Compare the two endpoint squares and fill the output from right to left. This turns two monotone magnitude frontiers into a merge in descending consumption order.

State and boundaries

left and right bound unread input. write is the next output index from the right; positions after it are final.

Protocol

1. Allocate an output of the same length.
2. Compare endpoint squares.
3. Write the larger square at write.
4. Consume its source endpoint.
5. Move write left until output is complete.

Visualization

input: [-4,-1,0,3,10]
choose max square: 100,16,9,1,0
write from right: [0,1,9,16,100]

Python implementation

def sorted_squares(nums):
    output = [0] * len(nums)
    left, right = 0, len(nums) - 1
    for write in range(len(nums) - 1, -1, -1):
        if nums[left] ** 2 > nums[right] ** 2:
            output[write] = nums[left] ** 2
            left += 1
        else:
            output[write] = nums[right] ** 2
            right -= 1
    return output

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L2 sorted_squares: output = [0] * len(nums)
nums=[-4, -1, 0, 3, 10]; output=[0, 0, 0, 0, 0]

L3 sorted_squares: left, right = 0, len(nums) - 1
nums=[-4, -1, 0, 3, 10]; output=[0, 0, 0, 0, 0]; left=0; right=4

L4 sorted_squares: for write in range(len(nums) - 1, -1, -1):
nums=[-4, -1, 0, 3, 10]; output=[0, 0, 0, 0, 0]; left=0; right=4; write=4

L9 sorted_squares: output[write] = nums[right] ** 2
nums=[-4, -1, 0, 3, 10]; output=[0, 0, 0, 0, 100]; left=0; right=4; write=4

L10 sorted_squares: right -= 1
nums=[-4, -1, 0, 3, 10]; output=[0, 0, 0, 0, 100]; left=0; right=3; write=4

L4 sorted_squares: for write in range(len(nums) - 1, -1, -1):
nums=[-4, -1, 0, 3, 10]; output=[0, 0, 0, 0, 100]; left=0; right=3; write=3

L6 sorted_squares: output[write] = nums[left] ** 2
nums=[-4, -1, 0, 3, 10]; output=[0, 0, 0, 16, 100]; left=0; right=3; write=3

L7 sorted_squares: left += 1
nums=[-4, -1, 0, 3, 10]; output=[0, 0, 0, 16, 100]; left=1; right=3; write=3

... 4 intermediate state changes omitted ...

L6 sorted_squares: output[write] = nums[left] ** 2
nums=[-4, -1, 0, 3, 10]; output=[0, 1, 9, 16, 100]; left=1; right=2; write=1

L7 sorted_squares: left += 1
nums=[-4, -1, 0, 3, 10]; output=[0, 1, 9, 16, 100]; left=2; right=2; write=1

L4 sorted_squares: for write in range(len(nums) - 1, -1, -1):
nums=[-4, -1, 0, 3, 10]; output=[0, 1, 9, 16, 100]; left=2; right=2; write=0

L10 sorted_squares: right -= 1
nums=[-4, -1, 0, 3, 10]; output=[0, 1, 9, 16, 100]; left=2; right=1; write=0

L2 sorted_squares: output = [0] * len(nums)
nums=[]; output=[]

L3 sorted_squares: left, right = 0, len(nums) - 1
nums=[]; output=[]; left=0; right=-1

Why the solution is correct

The selected endpoint square is maximal among all unread values, so it belongs at the greatest unfilled output index. Consuming it preserves that claim for the smaller interval. Filling every index gives all squares in nondecreasing order.

Time and space

O(n) time and O(n) returned space; O(1) other state.

Common mistakes

Squaring in place without reordering leaves large negative squares at the front. Filling from the left would require the smallest magnitude, which is not generally at an endpoint.

Reasoning card

Transfer exercise

Merge squared values outward from the sign boundary instead; compare which direction each source must move.