977. Squares of a Sorted Array

• python3

Problem

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.

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

Pseudocode

First solution

1. Replace each element with its square.
2. Sort the array.

O(n) solution

1. Since this is non-decreasing array, the squares of either the first or the last element could be become the largest element in the new array.
2. Set two pointers:one starting from the left and the other from the right. Also, set a write pointer starting from the end of the result array.
3. Compare the left and right elements. If the left element is larger than the right, put the squares of the left element into the current index of result array, then increment the left pointer by 1.
4. Repeat step 3 until all elemnets are processed.

Code

First Solution

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:

        for i in range(len(nums)):
            nums[i] = abs( nums[i] **2 )
        
        nums.sort()
        return nums

O(n) solution

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:

        result = [0] * len(nums)
        writePointer = len(nums) - 1

        left = 0
        right = len(nums) - 1

        while left <= right:
            if nums[left] * nums[left] > nums[right] * nums[right]:
                result[writePointer] = nums[left]*nums[left]
                left +=1
            else:
                result[writePointer] = nums[right]*nums[right]
                right -=1
            writePointer -=1
        
        return result

Result

Fisrt solution

• Time Complexity : O(nlogn) cause sorted methods
• Space Complexity : O(1) as we are not using any extra space.

O(n) solution

• Time Complexity : O(n) as we are traveling the array only once
• Space Complexity : O(n) as we use new array

Review

• I find non-decreasing condition late. I should always start solving problems with the conditions in mind.