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(nlog⁡n).
  • Overall: O(n+nlog⁡n), which simplifies to O(nlog⁡n)

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.