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 $$ 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.

Core Insight for Squares of a Sorted Array

The key intuition for the optimal LeetCode 977 solution is recognizing the geometric structure of the squared values. If we plot the values of the sorted input array, the squares form a parabola. The smallest squared value (0 or close to 0) is somewhere in the middle (or at one end if all numbers are positive/negative), while the largest squared values are always at the far left (large negatives) or the far right (large positives).

Because the largest potential squares are guaranteed to be at the edges of the array, we can determine the final position of elements without re-sorting the entire dataset. We can construct the result array in reverse order, from the largest square to the smallest.

Visual Description: Imagine the input array as a horizontal line of numbers. The magnitude (absolute value) is high at both ends and decreases towards the center. By placing one pointer at the far left (left) and one at the far right (right), we compare the absolute values at these pointers. The pointer with the larger absolute value will produce the larger square. We place this square at the end of our result array and move that specific pointer inward. This effectively "peels" the largest values from the outside in, merging the two sorted halves (negative and positive) into a single sorted output.

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.

Reference Implementation

C++ Solution for LeetCode 977

cpp
class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int n = nums.size();
        vector<int> result(n);
        int left = 0;
        int right = n - 1;
        int index = n - 1;

        while (left <= right) {
            int leftVal = abs(nums[left]);
            int rightVal = abs(nums[right]);

            if (leftVal > rightVal) {
                result[index] = leftVal * leftVal;
                left++;
            } else {
                result[index] = rightVal * rightVal;
                right--;
            }
            index--;
        }

        return result;
    }
};

Java Solution for LeetCode 977

java
class Solution {
    public int[] sortedSquares(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
        int left = 0;
        int right = n - 1;
        int index = n - 1;

        while (left <= right) {
            int leftVal = Math.abs(nums[left]);
            int rightVal = Math.abs(nums[right]);

            if (leftVal > rightVal) {
                result[index] = leftVal * leftVal;
                left++;
            } else {
                result[index] = rightVal * rightVal;
                right--;
            }
            index--;
        }

        return result;
    }
}

Python Solution for LeetCode 977

python
class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        n = len(nums)
        result = [0] * n
        left = 0
        right = n - 1
        index = n - 1
        
        while left <= right:
            left_val = abs(nums[left])
            right_val = abs(nums[right])
            
            if left_val > right_val:
                result[index] = left_val * left_val
                left += 1
            else:
                result[index] = right_val * right_val
                right -= 1
            index -= 1
            
        return result