Squares of a Sorted Array

#algorithms #beginners #tutorial #programming

Hi everyone!
Today I solved a nice problem where we need to return the squares of a sorted array in sorted order. At first it looks simple, but there’s a small twist!

Problem
Given a sorted array (can include negative numbers), return a new array of squares in sorted order.

Example:
Input: [-4, -1, 0, 3, 10]

Output: [0, 1, 9, 16, 100]

My Approach

At first, I thought:

Just square all elements and sort

But that would take O(n log n) time.

Then I noticed:

Negative numbers can become large after squaring
The largest square will be either at the start or end

So I used a two-pointer approach.

Logic

Use two pointers:
- l at start
- r at end
Compare squares of both ends
Place the larger square at the end of result array
Move pointers accordingly

Code (Python)
class Solution:
def sortedSquares(self, nums):
n = len(nums)
res = [0] * n
l, r = 0, n - 1

    for i in range(n - 1, -1, -1):
        if nums[l] * nums[l] > nums[r] * nums[r]:
            res[i] = nums[l] * nums[l]
            l += 1
        else:
            res[i] = nums[r] * nums[r]
            r -= 1

    return res

Time & Space Complexity