Squares of a Sorted Array

You are given an array of n integers sorted in non-decreasing order (values may be negative, zero, or positive). Produce a new array containing the squares of every element, also sorted in non-decreasing order - computed without a general-purpose sort, using two pointers starting from both ends of the original array, since the largest squared values can only come from the most negative or most positive numbers.

Input: The first line contains the integer n. The second line contains n space-separated integers representing the sorted array. Output: Print the n squared values in non-decreasing order, space-separated, on a single line.

1 <= n <= 10^5 -10^4 <= arr[i] <= 10^4 arr is sorted in non-decreasing order

This is a clever twist on the standard two-pointer pattern: instead of moving pointers to search for a target, here they're used to CONSTRUCT a new sorted array by repeatedly picking whichever end currently has the larger contribution - a good example of two pointers used for a BUILD operation, not just a search.

Produce the squares of a sorted array's values, also in sorted order, without using a general-purpose sort. Brute force: Square every element directly, then sort the resulting array with a general-purpose sort - this costs O(n log n), unnecessary given that the ORIGINAL array's sorted structure already tells you where the largest squares will come from. Optimised: Since the array is sorted (potentially spanning negative to positive), the LARGEST squares always come from the OUTER ends (furthest from zero) - comparing the two ends' squares and filling the result array from the BACK (largest to smallest) lets a single two-pointer pass produce the fully sorted squared result in linear time, no general sort needed.

1. Recognize that the LARGEST squared value always comes from whichever END (leftmost or rightmost) has the GREATER ABSOLUTE VALUE. 2. Use two pointers at the start and end of the array, and a WRITE pointer starting at the LAST position of the result array, filling from the LARGEST square down to the smallest. 3. At each step, compare the squares at the two pointers, place the LARGER one at the write pointer, and move that pointer inward.

Time: O(n) - a single two-pointer pass, filling the result array from the back. Space: O(n), for the result array (though this could be considered O(1) extra if the result is allowed to overwrite the input, which typically isn't done here since input and output serve different purposes).

Handle an array of all non-negative values (squares are already in sorted order) and an array of all non-positive values (squares come out in reverse order); fill the result from the back using two pointers to stay within O(n) at n = 10^5.

Be ready to explain WHY filling the result array from the BACK (largest first) rather than the front is the natural direction here - since you're comparing which END has the bigger absolute value at each step, and that comparison directly identifies the LARGEST remaining square, not the smallest.