Squares of a Sorted Array - Leetcode Solution

Problem Link

Step-by-Step Thought Process

Brute Force

Understand the problem: Given a sorted array of integers, return a new array containing the squares of each number in non-decreasing order.
Get the length n of the input array nums.
Iterate through each index i from 0 to n-1.
Replace nums[i] with its square (nums[i] ** 2).
Sort the modified array nums in non-decreasing order.
Return nums as the sorted array of squares.

Code Solution (Brute Force)

# Brute Force Solution
class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        n = len(nums)
        for i in range(n):
            nums[i] = nums[i] ** 2
        
        nums.sort()

        return nums

# Time: O(n log n)
# Space: O(1)

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            nums[i] = nums[i] * nums[i];
        }
        sort(nums.begin(), nums.end());
        return nums;
    }
};
// Time: O(n log n)
// Space: O(1) (not counting output space)

import java.util.Arrays;

class Solution {
    public int[] sortedSquares(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; ++i) {
            nums[i] = nums[i] * nums[i];
        }
        Arrays.sort(nums);
        return nums;
    }
}
// Time: O(n log n)
// Space: O(1) (not counting output space)

var sortedSquares = function(nums) {
    for (let i = 0; i < nums.length; i++) {
        nums[i] = nums[i] * nums[i];
    }
    nums.sort((a, b) => a - b);
    return nums;
};
// Time: O(n log n)
// Space: O(1) (not counting output space)

Why the Brute-Force Solution is Inefficient

The brute-force solution squares each element and then sorts the entire array, leading to:

Time Complexity: O(n log n), where n is the length of the array, due to the sorting step.
Space Complexity: O(1), as it modifies the array in-place (assuming the sorting algorithm uses constant extra space).
Performance Issue: The sorting step is unnecessary since the input array is already sorted, and the squares can be arranged in order more efficiently by leveraging the sorted property.

Optimal Solution

The optimal solution uses two pointers to build the result in O(n) time by comparing absolute values from both ends:

Initialize two pointers: left to 0 and right to the last index of nums.
Initialize an empty list result to store the squared values.
While left is less than or equal to right, compare the absolute values of nums[left] and nums[right].
If abs(nums[left]) is greater than abs(nums[right]), append nums[left] ** 2 to result and increment left.
Otherwise, append nums[right] ** 2 to result and decrement right.
Reverse the result list to get the squares in non-decreasing order.
Return result as the sorted array of squares.

Code Solution (Optimal)

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        left = 0
        right = len(nums) - 1
        result = []

        while left <= right:
            if abs(nums[left]) > abs(nums[right]):
                result.append(nums[left] ** 2)
                left += 1
            else:
                result.append(nums[right] ** 2)
                right -= 1

        result.reverse()

        return result

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

#include <vector>
#include <algorithm>

using namespace std;

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

        while (left <= right) {
            if (abs(nums[left]) > abs(nums[right])) {
                result[index--] = nums[left] * nums[left];
                left++;
            } else {
                result[index--] = nums[right] * nums[right];
                right--;
            }
        }

        return result;
    }
};

import java.util.Arrays;

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

        while (left <= right) {
            if (Math.abs(nums[left]) > Math.abs(nums[right])) {
                result[index--] = nums[left] * nums[left];
                left++;
            } else {
                result[index--] = nums[right] * nums[right];
                right--;
            }
        }

        return result;
    }
}

var sortedSquares = function(nums) {
    let left = 0, right = nums.length - 1;
    let result = new Array(nums.length);
    let index = nums.length - 1;

    while (left <= right) {
        if (Math.abs(nums[left]) > Math.abs(nums[right])) {
            result[index--] = nums[left] * nums[left];
            left++;
        } else {
            result[index--] = nums[right] * nums[right];
            right--;
        }
    }

    return result;
};

Detailed Explanation

Understanding the Problem: Squares of a Sorted Array

The “Squares of a Sorted Array” problem asks you to return an array of the squares of each number in a given sorted array, with the result sorted in non-decreasing order.

For example:

Input: [-4, -1, 0, 3, 10] → Output: [0, 1, 9, 16, 100]
Input: [-7, -3, 2, 3, 11] → Output: [4, 9, 9, 49, 121]

Why This Problem Matters

This problem helps reinforce understanding of array traversal and two-pointer strategies. It's especially valuable because it teaches how to exploit the structure of a sorted array to avoid unnecessary sorting operations.

Brute Force Approach: Square and Sort

A naive approach is to square each element in the array and then sort the entire array.

Steps:

Iterate through the array and replace each element with its square.
Sort the resulting array in non-decreasing order.
Return the sorted array.

While simple, this method does not make use of the fact that the input array is already sorted, and sorting introduces unnecessary computational overhead.

Optimal Solution: Two-Pointer Technique

Since the array is sorted, negative numbers appear on the left and positive numbers on the right. Squaring both can disrupt the order — for example, -4 becomes 16, which is larger than 3 ** 2 = 9.

We can use two pointers — one at the start and one at the end — to compare the absolute values and insert the larger square at the end of the result array, moving inward.

Steps:

Initialize two pointers: left = 0, right = nums.length - 1.
Create a result array of the same size, filled with zeroes.
Initialize a pointer pos = nums.length - 1 to fill the result array from the end.
While left <= right:
- If Math.abs(nums[left]) > Math.abs(nums[right]), set result[pos] = nums[left] ** 2 and increment left.
- Else, set result[pos] = nums[right] ** 2 and decrement right.
- Decrement pos.
Return the result array.

Example Walkthrough

Input: [-4, -1, 0, 3, 10]

left = -4 → 16, right = 10 → 100
Compare and place the larger square at the end → 100 goes in last position
Repeat until left > right
Final result: [0, 1, 9, 16, 100]

Time and Space Complexity

Time Complexity: O(n), where n is the number of elements in the array. Each element is processed once.
Space Complexity: O(n) for the result array. (If in-place modification is required and allowed, space can be improved depending on constraints.)

Edge Cases to Consider

All non-negative values → output is simply the squares
All non-positive values → reverse the squared values
Zeros only → return all zeros
Mixed positive and negative numbers → two-pointer logic is essential

Conclusion

The “Squares of a Sorted Array” problem is a great demonstration of how to leverage sorted data to improve performance. By using a two-pointer approach, you can solve the problem in linear time without relying on sorting — making your solution both efficient and elegant.

Get Personalized Support at AlgoMap Bootcamp 💡