Squares of a Sorted Array

LeetCode 977: Squares of a Sorted Array Solution & Explanation

Problem Overview

TL;DR: The optimal solution utilizes two pointers starting at the array's extremities to populate a new result array from back to front, leveraging the fact that the largest squares are always at the ends.

The problem asks us to take an integer array nums, which is sorted in non-decreasing order, square every element, and return a new array containing these squared values, also sorted in non-decreasing order. The challenge lies in the presence of negative numbers; while the input is sorted (e.g., -5, -3, 2), squaring them disrupts the order because the square of a large negative number (25) is greater than the square of a small positive number (4).

This is a fundamental array manipulation problem often referred to as "Squares of a Sorted Array" in interview contexts. It serves as an excellent introduction to optimizing space and time trade-offs using pointer logic.

Brute Force Approach for Squares of a Sorted Array

The most intuitive approach is to process the data in two distinct steps: squaring and sorting. Since the requirement is to return a sorted array of squares, one can simply iterate through the input array, square each number, and then apply a standard sorting algorithm to the resulting collection.

Pseudo-code:

function sortedSquares(nums):
    create empty list result
    for x in nums:
        append (x * x) to result
    sort(result)
    return result

Complexity Analysis:

• Time Complexity: $O(N \log N)$. While squaring the elements takes $O(N)$ time, the dominant operation is the sorting step, which typically requires $O(N \log N)$ time.
• Space Complexity: $O(N)$ or $O(\log N)$, depending on the sorting implementation (e.g., Timsort in Python uses $O(N)$, while some QuickSort implementations use $O(\log N)$ stack space).

Why it fails: While this solution is correct and passes the basic tests, it is not optimal. The problem statement includes a follow-up asking for an $O(N)$ solution. The brute force approach ignores the valuable property that the input is already sorted, leading to redundant computational effort during the re-sorting phase.

Algorithm Strategy: Two Pointer Patterns

1. Initialization: Create a result array of the same length as the input nums. Initialize two pointers: left pointing to index 0 and right pointing to index n-1.
2. Reverse Filling: Initialize a position marker index at n-1. This marker indicates where the next largest square should be placed in the result array.
3. Converging Iteration: Loop while left is less than or equal to right:
   • Compare the absolute value of nums[left] with nums[right].
   • If |nums[left]| is greater, the square of nums[left] is the largest remaining value. Place it at result[index] and increment left.
   • Otherwise, the square of nums[right] is the largest (or equal). Place it at result[index] and decrement right.
   • Decrement the index marker to move to the next available slot in the result array.
4. Termination: The loop finishes when all positions in the result array are filled. Return the result.

Execution Flow

Consider the input nums = [-4, -1, 0, 3, 10]. Length is 5. Result array res = [?, ?, ?, ?, ?].

1. State: left = 0 (val -4), right = 4 (val 10), index = 4.

   • Compare abs(-4) vs abs(10) -> 4 vs 10.
   • 10 is larger. 10*10 = 100.
   • res[4] = 100. Decrement right. Decrement index.

2. State: left = 0 (val -4), right = 3 (val 3), index = 3.

   • Compare abs(-4) vs abs(3) -> 4 vs 3.
   • 4 is larger. -4*-4 = 16.
   • res[3] = 16. Increment left. Decrement index.

3. State: left = 1 (val -1), right = 3 (val 3), index = 2.

   • Compare abs(-1) vs abs(3) -> 1 vs 3.
   • 3 is larger. 3*3 = 9.
   • res[2] = 9. Decrement right. Decrement index.

4. State: left = 1 (val -1), right = 2 (val 0), index = 1.

   • Compare abs(-1) vs abs(0) -> 1 vs 0.
   • 1 is larger. -1*-1 = 1.
   • res[1] = 1. Increment left. Decrement index.

5. State: left = 2 (val 0), right = 2 (val 0), index = 0.

   • left == right. Compare abs(0) vs abs(0).
   • Values equal. 0*0 = 0.
   • res[0] = 0. Decrement right. Decrement index.

6. Termination: left > right. Return [0, 1, 9, 16, 100].

Proof of Correctness

The correctness of this algorithm relies on the invariant that at any step of the iteration, the largest square among all unvisited elements resides at either the left pointer or the right pointer.

Since the input array is sorted, negative numbers are on the left (increasing in magnitude as we go further left) and positive numbers are on the right (increasing in magnitude as we go further right). Therefore, the global maximum square must be one of the two endpoints. By consistently picking the larger of the two endpoints and placing it at the current last position of the result array, we guarantee that the result array is populated in strictly non-decreasing order from back to front.

Pattern Reuse Notes

The Two Pointers - Converging pattern is a versatile strategy used in many optimal solutions for sorted arrays.

• LeetCode 11: Container With Most Water - Uses converging pointers to maximize area by narrowing the width.
• LeetCode 15: 3Sum - Uses converging pointers to find pairs that sum to a target within a sorted array.
• LeetCode 16: 3Sum Closest - Similar to 3Sum, adjusting pointers based on distance to a target sum.
• LeetCode 18: 4Sum - Extends the logic of 3Sum with an additional loop, relying on the same pointer convergence for the inner optimization.

In all these problems, the sorted nature of the input (or the sorting step performed initially) allows us to discard invalid candidates efficiently by moving pointers inward.

Reference Implementation

C++ Solution for LeetCode 977

1class Solution {
2public:
3    vector<int> sortedSquares(vector<int>& nums) {
4        int n = nums.size();
5        vector<int> result(n);
6        int left = 0;
7        int right = n - 1;
8        int index = n - 1;
9
10        while (left <= right) {
11            int leftVal = abs(nums[left]);
12            int rightVal = abs(nums[right]);
13
14            if (leftVal > rightVal) {
15                result[index] = leftVal * leftVal;
16                left++;
17            } else {
18                result[index] = rightVal * rightVal;
19                right--;
20            }
21            index--;
22        }
23
24        return result;
25    }
26};

Java Solution for LeetCode 977

1class Solution {
2    public int[] sortedSquares(int[] nums) {
3        int n = nums.length;
4        int[] result = new int[n];
5        int left = 0;
6        int right = n - 1;
7        int index = n - 1;
8
9        while (left <= right) {
10            int leftVal = Math.abs(nums[left]);
11            int rightVal = Math.abs(nums[right]);
12
13            if (leftVal > rightVal) {
14                result[index] = leftVal * leftVal;
15                left++;
16            } else {
17                result[index] = rightVal * rightVal;
18                right--;
19            }
20            index--;
21        }
22
23        return result;
24    }
25}

Python Solution for LeetCode 977

1class Solution:
2    def sortedSquares(self, nums: List[int]) -> List[int]:
3        n = len(nums)
4        result = [0] * n
5        left = 0
6        right = n - 1
7        index = n - 1
8        
9        while left <= right:
10            left_val = abs(nums[left])
11            right_val = abs(nums[right])
12            
13            if left_val > right_val:
14                result[index] = left_val * left_val
15                left += 1
16            else:
17                result[index] = right_val * right_val
18                right -= 1
19            index -= 1
20            
21        return result