# 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;
}
};
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]
, thenresult[k--] = A[j] * A[j];
. - If
A[i] * A[i] >= A[j] * A[j]
, thenresult[k--] = A[i] * A[i];
.
The following animation illustrates the process:
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;
}
};
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;
}
}
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;
}
}
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
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
2
3
4
5
6