Square Of Sorted Array

Description

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: Squares are [16, 1, 0, 9, 100]. After sorting: [0, 1, 9, 16, 100].

Example 2:
Input: nums = [-7, -3, 2, 3, 11]
Output: [4, 9, 9, 49, 121]
Explanation: Squares are [49, 9, 4, 9, 121]. After sorting: [4, 9, 9, 49, 121].

Example 3:
Input: nums = [1, 2, 3]
Output: [1, 4, 9]
Explanation: All positive, so squares are already sorted.

Constraints

1 <= nums.length <= 10^4
-10^4 <= nums[i] <= 10^4
nums is sorted in non-decreasing order

Signature

def solution(nums: list[int]) -> list[int]: ...

Complexity

Time: O(n)
Space: O(n)

Hints

Pattern: Use two pointers at both ends of the array
Approach: Compare absolute values at both ends, place larger square at the end of result, move that pointer inward
Complexity: The largest squares are at the ends (negative or positive extremes)

Solutions

Python

def solution(nums):
    left = 0
    right = len(nums) - 1

    results = [0] * len(nums)
    for i in range(len(nums), 0, -1):
        a = nums[left]
        b = nums[right]

        aa = a * a
        bb = b * b

        if aa < bb:
            results[i - 1] = bb
            right -= 1
        else:
            results[i - 1] = aa
            left += 1

    return results