# 977. Squares of a Sorted Array

LeetCode Problem Link (opens new window)

Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.

Example 1:

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

Example 2:

  • Input: nums = [-7,-3,2,3,11]
  • Output: [4,9,9,49,121]

# Thought Process

# Naive Sorting

The most straightforward approach is to square each number, then sort the array, as shown in the following code:

class Solution {
public:
    vector<int> sortedSquares(vector<int>& A) {
        for (int i = 0; i < A.size(); i++) {
            A[i] *= A[i];
        }
        sort(A.begin(), A.end()); // Quick sort
        return A;
    }
};
1
2
3
4
5
6
7
8
9
10

The time complexity for this method is O(n + nlogn), which can be considered O(nlogn), but to clearly contrast with the two-pointer method below, we'll note it as O(n + nlog n).

# Two-Pointer Method

The array is sorted, but squares of negative numbers might be larger than others. Therefore, the largest square could be at either end of the array, not in the middle.

In this case, we can use the two-pointer technique, with i pointing to the start and j pointing to the end.

Define a new array result with the same size as array A, and let k point to the end of the result array.

  • If A[i] * A[i] < A[j] * A[j], then result[k--] = A[j] * A[j];.
  • If A[i] * A[i] >= A[j] * A[j], then result[k--] = A[i] * A[i];.

The following animation illustrates the process:

Two-pointer method

We can write the code as follows:

class Solution {
public:
    vector<int> sortedSquares(vector<int>& A) {
        int k = A.size() - 1;
        vector<int> result(A.size(), 0);
        for (int i = 0, j = A.size() - 1; i <= j;) { // Note the condition i <= j, as the last two elements need handling
            if (A[i] * A[i] < A[j] * A[j])  {
                result[k--] = A[j] * A[j];
                j--;
            }
            else {
                result[k--] = A[i] * A[i];
                i++;
            }
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

Now the time complexity is O(n), which is a notable improvement from the naive sorting approach with O(n + nlog n).

It's worth mentioning that you should not put too much emphasis on the runtime results on LeetCode, as they are somewhat like a toy and not entirely accurate.

While solving problems, focus on analyzing the time complexity yourself, and as long as you reach the optimal time complexity, that's what counts.

The same code can achieve different runtime metrics if submitted multiple times, potentially beating 100% users...

# Other Language Versions

# Java:

Sorting Approach

class Solution {
    public int[] sortedSquares(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            nums[i] = nums[i] * nums[i];
        }
        Arrays.sort(nums);
        return nums;
    }
}
1
2
3
4
5
6
7
8
9

Two-pointer Approach

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

# Python:

Two-pointer Approach

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        l, r, i = 0, len(nums)-1, len(nums)-1
        res = [float('inf')] * len(nums) # Pre-define a result list
        while l <= r:
            if nums[l] ** 2 < nums[r] ** 2: # Compare the boundary values
                res[i] = nums[r] ** 2
                r -= 1 # Move the right pointer leftward
            else:
                res[i] = nums[l] ** 2
                l += 1 # Move the left pointer rightward
            i -= 1 # Move the result pointer forward
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13

Sorting Approach

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        for i in range(len(nums)):
            nums[i] *= nums[i]
        nums.sort()
        return nums
1
2
3
4
5
6
Last updated:: 9/4/2025, 3:19:38 PM
Copyright © 2025 keetcoder