Given an array sorted in increasing order, which may include negative numbers, return the squares of every number, also sorted in increasing order.
DSA Animator › DSA Revision › Arrays › Squares of a Sorted Array
Remember: in a sorted array with negatives, the largest squares sit at the two ends. Fill the result from the back with two pointers. The video solves Squares of a Sorted Array (LeetCode 977, Easy) with the Two Pointers pattern from the Arrays topic, and you can replay every step in the interactive Squares of a Sorted Array animation.
Given an array sorted in increasing order, which may include negative numbers, return the squares of every number, also sorted in increasing order.
For minus 4, minus 1, 0, 3 and 10, the squares sorted are 0, 1, 9, 16, 100.
Squaring everything and then sorting costs O of n log n. Negative numbers break the order: minus 4 squared is bigger than 3 squared.
The biggest square always comes from one of the two ends, because those have the largest absolute values. So use two pointers at both ends, and fill the answer from the back. Each time, place the bigger square, and move that pointer inward.
Compare minus 4 and 10: 10 squared, 100, is bigger, so it goes last. Compare minus 4 and 3: 16 is bigger than 9, so 16 goes next. Compare minus 1 and 3: 9 is bigger, so 9 goes in. Compare minus 1 and 0: 1 is bigger, so 1 goes in. Only 0 is left, and it takes the first slot. The answer is 0, 1, 9, 16, 100.
In code, put left at 0, right at the end, and fill position p from the back. Compare the absolute values at both ends. Write the larger square at p, and move that pointer inward. One pass, so it's O of n time, and O of n for the answer.
Remember: in a sorted array with negatives, the largest squares sit at the two ends. Fill the result from the back with two pointers.