977. Squares of a Sorted Array - Detailed Explanation

Problem Statement

Description:
Given an array of integers nums sorted in non-decreasing order, return an array of the squares of each number, also sorted in non-decreasing order.

Constraints:

• 1 ≤ nums.length ≤ 10⁴
• -10⁴ ≤ nums[i] ≤ 10⁴
• The array nums is sorted in non-decreasing order.

Example 1:

• Input: nums = [-4, -1, 0, 3, 10]
• Output: [0, 1, 9, 16, 100]
• Explanation:
  Squaring the numbers gives [16, 1, 0, 9, 100]. After sorting, the array becomes [0, 1, 9, 16, 100].

Example 2:

• Input: nums = [-7, -3, 2, 3, 11]
• Output: [4, 9, 9, 49, 121]
• Explanation:
  Squaring the numbers gives [49, 9, 4, 9, 121]. Sorting them results in [4, 9, 9, 49, 121].

Hints to Approach the Problem

• Hint 1: The input array is already sorted; however, after squaring, the order might not be preserved because negative numbers become positive.
• Hint 2: Notice that the largest square will come from the element with the greatest absolute value, which lies at either end of the array.
• Hint 3: Use a two-pointer technique—one pointer starting at the beginning and one at the end—to compare absolute values and place the larger square at the end of a result array, working backward.

Approaches

Brute Force Approach

Idea:
Square every element and then sort the squared values.

Steps:

1. Iterate over each element in the array, square it, and store it in a new array.
2. Sort the new array.
3. Return the sorted array.

Complexity:

• Time Complexity: O(n log n) due to the sorting step.
• Space Complexity: O(n) for storing the squared values.

Optimal Approach Using Two Pointers

Idea:
Since the array is sorted by value (but may include negatives), the largest squared value comes from either end. Use two pointers—one at the start and one at the end—to compare the absolute values. Place the larger square at the end of the result array and move the corresponding pointer.

Steps:

1. Initialize two pointers: left at index 0 and right at the last index.
2. Create an output array of the same length as nums.
3. Set an index pos at the last position of the output array.
4. While left ≤ right:
   • Compare abs(nums[left]) and abs(nums[right]).
   • If abs(nums[left]) is greater, square nums[left] and place it at output[pos], then increment left.
   • Otherwise, square nums[right] and place it at output[pos], then decrement right.
   • Decrement pos.
5. Return the output array.

Complexity:

• Time Complexity: O(n) since we make a single pass through the array.
• Space Complexity: O(n) for the output array.

Detailed Walkthrough (Using the Two-Pointer Approach)

Consider the array: nums = [-4, -1, 0, 3, 10]

1. Initialization:

   • Set left = 0 and right = 4.
   • Create an output array: result = [0, 0, 0, 0, 0].
   • Set pos = 4 (the last index).

2. Iteration:

   • Step 1:

     • Compare: abs(nums[left]) = 4 vs. abs(nums[right]) = 10.
     • Since 10 is larger, square 10 → 100 and place it at result[4].
     • Update: right becomes 3, pos becomes 3.
     • Output: [0, 0, 0, 0, 100].

   • Step 2:

     • Now, left = 0 (value -4), right = 3 (value 3).
     • Compare: abs(-4) = 4 vs. abs(3) = 3.
     • Since 4 is larger, square -4 → 16 and place it at result[3].
     • Update: left becomes 1, pos becomes 2.
     • Output: [0, 0, 0, 16, 100].

   • Step 3:

     • Now, left = 1 (value -1), right = 3 (value 3).
     • Compare: abs(-1) = 1 vs. abs(3) = 3.
     • Since 3 is larger, square 3 → 9 and place it at result[2].
     • Update: right becomes 2, pos becomes 1.
     • Output: [0, 0, 9, 16, 100].

   • Step 4:

     • Now, left = 1 (value -1), right = 2 (value 0).
     • Compare: abs(-1) = 1 vs. abs(0) = 0.
     • Since 1 is larger, square -1 → 1 and place it at result[1].
     • Update: left becomes 2, pos becomes 0.
     • Output: [0, 1, 9, 16, 100].

   • Step 5:

     • Now, left = 2 and right = 2 (both point to 0).
     • Square 0 → 0 and place it at result[0].
     • Output: [0, 1, 9, 16, 100].

3. Conclusion:
   The final output array is [0, 1, 9, 16, 100].

Code Implementation

Python Code