Squares of a Sorted Array
Explore multiple ways to solve LeetCode 977: Squares of a Sorted Array, including brute force, list comprehension, and the efficient two-pointer method. Improve your coding skills with this clear and concise guide!
Problem Definition
LeetCode Link: 977. Squares of a Sorted Array
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]
Constraints:
1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums
is sorted in non-decreasing order.
Solutions
Brute Force
The most intuitive idea is: square each number, then sort them. The code is as follows:
class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
for i in range(len(nums)):
nums[i] *= nums[i]
nums.sort()
return nums
The time complexity is O(n + nlogn), which can be said to be O(nlogn). However, in order to clearly contrast it with the time complexity of the two-pointer method algorithm below, I denote it as O(n + nlogn).
Double Pointer
The array is actually ordered; it's just that the square of a negative number may become the largest number.
Therefore, the maximum value of the squared array is at both ends of the array, either on the far left or far right, and it cannot be in the middle.
At this point, we can consider using a two-pointer method, with i pointing to the starting position and j pointing to the ending position.
Define a new array called result, which has the same size as array A, and let k point to the end position 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 code is as follows:
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) # define the list in advance to store the results.
while l <= r:
if nums[l] ** 2 < nums[r] ** 2: # Compare the left and right boundaries to find the maximum value.
res[i] = nums[r] ** 2
r -= 1 # The right pointer moves to the left.
else:
res[i] = nums[l] ** 2
l += 1 # The left pointer moves to the right.
i -= 1 # The pointer for storing the result needs to be moved forward by one position.
return res
At this point, the time complexity is O(n), which is a significant improvement compared to the brute force sorting solution of O(n + nlog n).
Brute Force + List Comprehension
This solution uses list comprehension to square each element in the input array and sorts the results directly. This method simplifies the code and achieves the same functionality with a more concise approach.
Here is the code:
class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
return sorted(x * x for x in nums)
Time Complexity:
- Generating the list with list comprehension takes O(n), where nnn is the length of the input array.
- Sorting the list takes O(nlogn).
- Overall: O(n+nlogn), which simplifies to O(nlogn)
This approach is equivalent to the brute force method discussed earlier but has a more elegant and Pythonic implementation. However, like the original brute force solution, it is still less efficient than the two-pointer method, which achieves a time complexity of O(n).
If code simplicity and readability are prioritized, the list comprehension approach is a great alternative. However, for larger inputs, the two-pointer approach will perform better.
Two-Pointer + Reverse List Method
This solution builds on the two-pointer technique, but instead of filling the result list from the end, it appends squared values in descending order and reverses the list at the end. This approach simplifies the logic while achieving the same result as the original two-pointer method.
The code is as follows:
class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
# Initialize an empty list to store the squared values in descending order
new_list = []
left, right = 0, len(nums) - 1 # Initialize two pointers
# Iterate until the two pointers cross each other
while left <= right:
# Compare absolute values of elements at both ends
if abs(nums[left]) <= abs(nums[right]):
new_list.append(nums[right] ** 2) # Add the larger square to new_list
right -= 1 # Move the right pointer left
else:
new_list.append(nums[left] ** 2) # Add the larger square to new_list
left += 1 # Move the left pointer right
# Reverse the list to get non-decreasing order
return new_list[::-1]
Time Complexity:
- Two-pointer traversal: O(n), where nnn is the length of the input array.
- Reversing the list: O(n).
- Overall: O(n).
This two-pointer + reverse list approach offers the same linear time complexity as the original two-pointer method but is more intuitive by appending larger squares first. It trades off a slight overhead for reversing the list but remains very efficient.
This version is an excellent alternative if you prefer to keep logic straightforward by focusing on adding elements in descending order and reversing at the end.
Discussion