Squares of a Sorted Array

Difficulty: Easy

Problem

The integer array nums is already sorted from smallest to largest and may include negative values. Build and return an array containing the square of every element, also ordered from smallest to largest.

Example

Input: nums = [-6, -2, 1, 4, 5]
Output: [1, 4, 16, 25, 36]
Explanation: Squaring each value gives [36, 4, 1, 16, 25], which sorts to [1, 4, 16, 25, 36].

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)

Pseudocode

function sortedSquares(nums):
    n = len(nums)
    result = array of size n
    left = 0
    right = n - 1
    pos = n - 1
    
    while left <= right:
        if abs(nums[left]) > abs(nums[right]):
            result[pos] = nums[left] * nums[left]
            left += 1
        else:
            result[pos] = nums[right] * nums[right]
            right -= 1
        pos -= 1
    
    return result

Hints

  • The largest square must come from either the leftmost or rightmost element
  • Use two pointers from both ends, filling the result array from the back
  • Compare absolute values to determine which square is larger

Check your understanding of Squares of a Sorted Array

Why can't we just square each element and return the array?

Negative numbers when squared may produce larger values than positive numbers, breaking the sorted order. For example, (-4)² = 16 which is larger than 3² = 9. Simply squaring in place doesn't preserve sorted order when negatives are present.

Why do we fill the result array from the back (largest to smallest)?

The largest squared value comes from either end of the sorted input, making it easy to place the biggest first. Since the input is sorted, the largest absolute values are at the two ends. By comparing these and placing the larger square at the back of the result, we build the answer correctly in O(n).

Related problems

Keep practising