Problem Description

You are given an integer array nums that is sorted in non-decreasing order (from smallest to largest). Your task is to create a new array containing the squares of each number from the original array, and this new array must also be sorted in non-decreasing order.

For example, if you have nums = [-4, -1, 0, 3, 10], after squaring each element you get [16, 1, 0, 9, 100]. The final answer should be these squares arranged in non-decreasing order: [0, 1, 9, 16, 100].

The challenge here is that negative numbers, when squared, become positive and can be larger than the squares of positive numbers. Since the original array contains both negative and positive numbers sorted in order, the smallest original numbers (which may be negative) could produce the largest squares. This means you can't simply square each element in place and keep the same order - you need to rearrange them.

The solution uses a two-pointer technique. Since the original array is sorted, the largest squares will come from either the leftmost elements (large negative numbers) or the rightmost elements (large positive numbers). By placing pointers at both ends and comparing the squares, we can build the result array by always taking the larger square and moving the corresponding pointer inward. The squares are collected from largest to smallest, so the final step reverses the array to get the required non-decreasing order.

Intuition

When we square numbers, negative values become positive. This creates an interesting pattern in a sorted array. Consider the array [-4, -1, 0, 3, 10]. The squares are [16, 1, 0, 9, 100]. Notice how the squared values form a "valley" shape - they decrease from the left side (negative numbers) toward the middle, then increase toward the right side (positive numbers).

The key insight is that in a sorted array, the largest squared values must come from the extremes - either from the most negative numbers on the left or the most positive numbers on the right. The smallest squared values will be somewhere in the middle, near zero.

This observation leads us to think about using two pointers. If we place one pointer at the beginning and one at the end of the array, we can always identify which element produces the next largest square by comparing nums[left]² with nums[right]².

Why build from largest to smallest? Because we can deterministically find the largest square at each step by comparing the extremes. Finding the smallest square would be harder - it could be anywhere in the middle of the array, and we'd need to search for it.

By repeatedly taking the larger square between the two extremes and moving that pointer inward, we gradually work our way toward the smaller squares in the middle. This gives us all squares in descending order. A simple reversal at the end gives us the required ascending order.

This approach elegantly handles all cases - arrays with only negative numbers, only positive numbers, or a mix of both - because the logic of "largest squares come from extremes" always holds true for sorted arrays.

Learn more about Two Pointers and Sorting patterns.

Solution Approach

The solution implements a two-pointer technique to efficiently build the sorted squares array. Here's how the algorithm works:

Initialize the pointers and result array:

• Create an empty list ans to store the squared values
• Set pointer i at index 0 (leftmost element)
• Set pointer j at index len(nums) - 1 (rightmost element)

Main processing loop: The algorithm continues while i <= j, ensuring we process all elements:

1. Calculate squares of both extremes:

   • a = nums[i] * nums[i] - square of the left element
   • b = nums[j] * nums[j] - square of the right element

2. Compare and select the larger square:

   • If a > b: The left element produces the larger square
     • Append a to the result array
     • Move the left pointer right: i += 1
   • Otherwise: The right element produces the larger (or equal) square
     • Append b to the result array
     • Move the right pointer left: j -= 1

3. Build from largest to smallest: Each iteration adds the next largest square to ans. Since we're always choosing between the two extremes and moving inward, we're guaranteed to get all squares in descending order.

Final reversal:

• Return ans[::-1] to reverse the array from descending to ascending order

Time and Space Complexity:

• Time: O(n) where n is the length of the input array - we visit each element exactly once
• Space: O(n) for the result array (not counting this as extra space since it's required for the output)

The elegance of this approach lies in its simplicity - by recognizing that the largest values must come from the extremes of a sorted array, we can build our result in a single pass without needing to sort the squared values.

Example Walkthrough

Let's walk through the algorithm with nums = [-4, -1, 0, 3, 10].

Initial Setup:

• ans = [] (empty result array)
• i = 0 (pointing to -4)
• j = 4 (pointing to 10)

Iteration 1: i = 0, j = 4

• Calculate squares: a = (-4)² = 16, b = (10)² = 100
• Compare: 16 < 100, so we take b = 100
• Add 100 to ans: ans = [100]
• Move right pointer left: j = 3

Iteration 2: i = 0, j = 3

• Calculate squares: a = (-4)² = 16, b = (3)² = 9
• Compare: 16 > 9, so we take a = 16
• Add 16 to ans: ans = [100, 16]
• Move left pointer right: i = 1

Iteration 3: i = 1, j = 3

• Calculate squares: a = (-1)² = 1, b = (3)² = 9
• Compare: 1 < 9, so we take b = 9
• Add 9 to ans: ans = [100, 16, 9]
• Move right pointer left: j = 2

Iteration 4: i = 1, j = 2

• Calculate squares: a = (-1)² = 1, b = (0)² = 0
• Compare: 1 > 0, so we take a = 1
• Add 1 to ans: ans = [100, 16, 9, 1]
• Move left pointer right: i = 2

Iteration 5: i = 2, j = 2

• Both pointers point to the same element (0)
• Calculate squares: a = (0)² = 0, b = (0)² = 0
• Compare: 0 = 0, so we take b = 0
• Add 0 to ans: ans = [100, 16, 9, 1, 0]
• Move right pointer left: j = 1

Termination: i = 2, j = 1 (i > j, loop ends)

Final Step:

• Reverse the array: ans[::-1] = [0, 1, 9, 16, 100]

The algorithm successfully builds the sorted squares array by always selecting the larger square from the extremes and working inward, then reversing to get ascending order.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the length of the array nums. The algorithm uses a two-pointer approach that traverses the array exactly once. In each iteration, either pointer i moves forward or pointer j moves backward, and the loop continues until they meet. Since we visit each element exactly once and perform constant-time operations (multiplication and comparison) for each element, the total time complexity is linear. The final reversal operation ans[::-1] also takes O(n) time, resulting in an overall time complexity of O(n) + O(n) = O(n).

Space Complexity: O(1) if we ignore the space consumption of the answer array ans. The algorithm only uses two pointers i and j, and two temporary variables a and b to store the squared values, all of which require constant extra space. The answer array ans stores n elements, but as mentioned in the reference answer, this is typically not counted as extra space since it's required for the output. Therefore, the auxiliary space complexity is O(1).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Handle the Case When Pointers Meet

A common mistake is using while left_pointer < right_pointer instead of while left_pointer <= right_pointer. This would miss processing the middle element when the pointers converge.

Incorrect:

while left_pointer < right_pointer:  # Missing the case when left_pointer == right_pointer
    # ... rest of the logic

Correct:

while left_pointer <= right_pointer:  # Ensures the last element is processed
    # ... rest of the logic

2. Directly Comparing Original Values Instead of Squares

Some might mistakenly compare the absolute values or original values to determine which square is larger, forgetting that the comparison should be between the actual squared values.

Incorrect:

if abs(nums[left_pointer]) > abs(nums[right_pointer]):
    result.append(nums[left_pointer] ** 2)
    left_pointer += 1

Correct:

left_square = nums[left_pointer] * nums[left_pointer]
right_square = nums[right_pointer] * nums[right_pointer]
if left_square > right_square:
    result.append(left_square)
    left_pointer += 1

3. Building the Array in Ascending Order with Wrong Pointer Movement

Attempting to build the array directly in ascending order by taking the smaller square can lead to incorrect pointer movement logic and missed elements.

Incorrect Approach:

# Trying to build in ascending order
if left_square < right_square:
    result.append(left_square)
    left_pointer += 1  # This won't correctly process all elements

The issue here is that you can't determine which pointer to move just by comparing squares when building in ascending order. The smaller square could come from either end depending on the values.

Solution: Stick to building in descending order (taking the larger square each time) and reverse at the end, as this guarantees correct pointer movement.

4. Not Handling Edge Cases

Failing to consider edge cases like:

• Empty array
• Array with single element
• Array with all negative numbers
• Array with all positive numbers

Robust Solution:

def sortedSquares(self, nums: List[int]) -> List[int]:
    if not nums:  # Handle empty array
        return []
  
    result = []
    left_pointer = 0
    right_pointer = len(nums) - 1
  
    while left_pointer <= right_pointer:
        left_square = nums[left_pointer] * nums[left_pointer]
        right_square = nums[right_pointer] * nums[right_pointer]
      
        if left_square > right_square:
            result.append(left_square)
            left_pointer += 1
        else:
            result.append(right_square)
            right_pointer -= 1
  
    return result[::-1]