You are given an integer array, nums, sorted in non-decreasing order. Your task is to return a new array containing the squares of each number, also sorted in non-decreasing order.

Constraints:

• $1 \leq$ nums.length $\leq 10^3$

• $-10^4 \leq$ nums[i] $\leq 10^4$

• nums is sorted in non-decreasing order.

As the input array is already sorted in non-decreasing order, we can solve this problem more efficiently than simply squaring all elements and sorting again (which would take $O(nlog⁡n)$). The key observation is that the largest square will always come from either the most negative number (at the far left) or the largest positive number (at the far right).

To take advantage of this, we use a two pointer technique: one pointer starts at the beginning of the array and the other at the end. At each step, we compare the absolute values at these two positions. The larger absolute value produces the larger square, which we place at the current last available position in the result array. We then move the pointer corresponding to the chosen value inward and continue the process.

By filling the result array from right to left, we ensure all elements are squared and placed in sorted order in a single pass, giving an optimal solution.

The steps of the algorithm are as follows:

1. Initialize two pointers: left = 0 at the start and right = n - 1 at the end of the array.

2. Create a result array res of the same size to store the sorted squares.

3. Set a position marker pos = n - 1 to fill res from the back.

4. While left <= right:

   1. Compare abs(nums[left]) and abs(nums[right]).

   2. Square the larger one and place it at res[pos].

   3. Move the corresponding pointer inward (left++ or right--).

   4. Decrement pos to move leftward in the result array.

5. Once the iteration finishes, res contains all squares in sorted non-decreasing order.

Let’s look at the following illustration to get a better understanding of the solution: