Squares of a Sorted Array

Difficulty: Easy

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

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].

Brute-force approach

Square every element, then sort the resulting array.

Steps

  1. Square each element in the array
  2. Sort the squared array

Time complexity: O(n log n) · Space complexity: O(n)

Trade-offs

  • Sorting costs O(n log n) when O(n) is achievable
  • Doesn't exploit the sorted property of the input

Optimal approach

Key insight: In a sorted array with negatives, the largest squares are at the two extremes. Compare |left| vs |right| and place the winner at the back.

Two pointers from both ends. Compare absolute values and fill result array from the back with the larger square.

Steps

  1. Initialize left=0, right=n-1, pos=n-1
  2. Compare |nums[left]| and |nums[right]|
  3. Place the larger square at result[pos], move that pointer inward
  4. Decrement pos, repeat until left > right

Time complexity: O(n) · Space complexity: O(n)