Leetcode 977 - Squares of a Sorted Array

Problem

Leetcode 977 - Squares of a Sorted Array

Example:

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].

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

Approach

O(n log n) time complexity approach:

1. Square each element in the array.
2. Sort the array. But this approach is not efficient, and we can do better by using two pointers.

O(n) time complexity approach:

1. Use two pointers(one in the beginning and one in the end) to find the largest square value.
2. Use a result array to store the sorted squares.

Visual representation of the approach:

nums = [-4,-1,0,3,10]
result = [0,0,0,0,0]

left = 0, right = 4
Since nums[left]**2 = 16 and nums[right]**2 = 100, we put 100 in the n of the result array.
Then, we move the right pointer to the left by 1.
result = [0,0,0,0,100]

left = 0, right = 3
Since nums[left]**2 = 16 and nums[right]**2 = 9, we put 16 in the n-1 of the result array.
Then, we move the left pointer to the right by 1.
result = [0,0,0,16,100]

left = 1, right = 3
Since nums[left]**2 = 1 and nums[right]**2 = 9, we put 9 in the n-2 of the result array.
Then, we move the right pointer to the left by 1.
result = [0,0,9,16,100]

left = 1, right = 2
Since nums[left]**2 = 1 and nums[right]**2 = 0, we put 1 in the n-3 of the result array.
Then, we move the left pointer to the right by 1.
result = [0,1,9,16,100]

left = 2, right = 2
Since nums[left]**2 = 0 and nums[right]**2 = 0, we put 0 in the n-4 of the result array.
Then, we move the left pointer to the right by 1.

result = [0,1,9,16,100]

Here’s the code implementation of the approach:

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        # initialize result array
        result = [0] * len(nums)
        # initialize two pointers
        left, right = 0, len(nums) - 1
        # initialize the index of the result array
        n = len(nums)-1

        # iterate through the array
        while left <= right:
            if nums[left]**2 < nums[right]**2:
                result[n] = nums[right]**2
                right -= 1
            else:
                result[n] = nums[left]**2
                left += 1
            n -= 1
        return result

Time Complexity and Space Complexity

The time complexity is $ O(n) $ since we’re iterating through the array once.

The space complexity is $ O(n) $ since we’re using a result array to store the sorted squares.