Squares of a Sorted Array

Problem

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

Examples

The brute-force approach

Square each element in place, then sort the result.

for i in range(len(nums)):
    nums[i] = nums[i] * nums[i]

nums.sort()
return nums

Sorting takes O(n log n). The input is already sorted, you just need to handle the fact that negatives squared can be large. Two pointers can merge the largest squares from both ends in O(n).

Spotting the pattern

This is a Two Pointers problem. The key question to ask yourself:

In a sorted array, where are the largest squares hiding?

Answering that is where it clicks, and it's exactly what the guided walkthrough below builds with you: the pattern reasoning, a progressive hint ladder that never spoils the answer, a row-by-row dry run, the optimized solution, and an in-browser editor to run your code against real test cases.