Squares of a Sorted Array

In this task, I worked on converting a sorted array into another sorted array of their squares.

The tricky part is that even though the input array is sorted, squaring negative numbers can mess up the order. For example, -4² = 16 which is bigger than 3² = 9.

What I Did

I created a function sortedSquares that takes a sorted array nums and returns a new sorted array of squared values.

How I Solved It

Instead of squaring everything and sorting again, I used a two-pointer approach.

I used three variables:

• left starting from the beginning (index 0)
• right starting from the end (index n-1)
• pos to fill the result array from the back

At each step:

• I compare the absolute values of nums[left] and nums[right]
• The larger absolute value will give the larger square
• I place that square at the current pos in the result array
• Then move the corresponding pointer (left or right)
• Decrease pos to fill the next position

This way, I build the sorted squared array from the back.

Code

class Solution:
    def sortedSquares(self, nums):
        n = len(nums)
        result = [0] * n

        left = 0
        right = n - 1
        pos = n - 1

        while left <= right:
            if abs(nums[left]) > abs(nums[right]):
                result[pos] = nums[left] ** 2
                left += 1
            else:
                result[pos] = nums[right] ** 2
                right -= 1
            pos -= 1

        return result

How It Works

The function avoids re-sorting by intelligently comparing values from both ends. Since the largest square will always come from either the most negative or most positive number, we place it at the end and move inward.

This reduces time complexity to O(n) instead of O(n log n).