977. Squares of a Sorted Array - Explanation

Problem Link

Description

You are 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 <= 10,000
• -10,000 <= nums[i] <= 10,000
• nums is sorted in non-decreasing order.

Follow up: Squaring each element and sorting the new array is very trivial, could you find an O(n) solution using a different approach?

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Sorting

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

Time & Space Complexity

• Time complexity: $O(n \log n)$
• Space complexity: $O(1)$ or $O(n)$ depending on the sorting algorithm.

---

2. Two Pointers - I

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        l, r, res = 0, len(nums) - 1, []

        while l <= r:
            if (nums[l] * nums[l]) > (nums[r] * nums[r]):
                res.append(nums[l] * nums[l])
                l += 1
            else:
                res.append(nums[r] * nums[r])
                r -= 1

        return res[::-1]

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(n)$ for the output array.

---

3. Two Pointers - II

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        n = len(nums)
        res = [0] * n
        l, r = 0, n - 1
        res_index = n - 1

        while l <= r:
            if abs(nums[l]) > abs(nums[r]):
                res[res_index] = nums[l] * nums[l]
                l += 1
            else:
                res[res_index] = nums[r] * nums[r]
                r -= 1
            res_index -= 1

        return res

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(n)$ for the output array.