Two pointers

Two pointers means two indices moving through the same array according to a rule. You use them when the array is sorted, or when the two ends know something the middle does not.

Sorted squares are the clean picture. A sorted array of negatives and positives does not have sorted squares, because a large negative becomes a large positive. The biggest squares sit at the ends. Square the left value and the right value, write the larger one into the back of the result, and move the pointer that produced it inward. Each step is O(1). Together the pointers cross the array once, so the whole walk is O(n).

Sorting the squares afterwards would work and would cost O(n log n). The sorted input is what makes the linear solution possible. If the input were unsorted, you would not have this trick. The shape to remember is a left index, a right index, and a reason to move exactly one of them.