Squares of a Sorted Array

Problem Description

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

Key Insights

• The array is sorted in non-decreasing order, which means negative numbers will be on the left side and positive numbers on the right side.
• Squaring negative numbers results in positive values that can be larger than the squares of the positive numbers.
• A two-pointer approach can be utilized to efficiently build the result array without needing to sort the squared values.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

The problem can be solved using a two-pointer technique. We initialize two pointers: one at the beginning of the array (for the smallest absolute values) and one at the end (for the largest absolute values). We compare the squares of the numbers at both pointers and fill the result array from the back (largest square to smallest) until all elements are processed.

1. Initialize an empty result array of the same length as nums.
2. Set two pointers: left at the start (0) and right at the end (length of nums - 1).
3. Compare the squares of the elements pointed to by the two pointers:
   • If the square at the left pointer is greater than the square at the right pointer, place the square of the left element at the end of the result array and move the left pointer one step to the right.
   • Otherwise, place the square of the right element at the end of the result array and move the right pointer one step to the left.
4. Repeat the process until all elements are squared and added to the result array.
5. Return the result array.

Code Solutions