CA 18 - Squares of an Sorted Array

#algorithms #beginners #coding #tutorial

Problem Statement

Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number also sorted in non-decreasing order.

Examples:

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]

My Goal

For this problem, my goal was to:

Handle both negative and positive numbers correctly
Avoid unnecessary sorting after squaring
Use an efficient approach instead of brute force
Understand how two-pointer techniques work

Solution

I used a two-pointer approach to solve this efficiently.

Idea:

The largest square will come from either:
The most negative number (left side)
The most positive number (right side)
Compare squares from both ends
Place the larger square at the end of result array
Move pointers accordingly

Solution Code (Python)

a = [-4, -1, 0, 3, 10]

n = len(a)
r = [0] * n

l = 0
h = n - 1
i = n - 1

while l <= h:
    if abs(a[l]) > abs(a[h]):
        r[i] = a[l] * a[l]
        l += 1
    else:
        r[i] = a[h] * a[h]
        h -= 1
    i -= 1

print(r)