Sorted Squared Array

Tags

Sorted Squared Array

Category

Arrays

Difficulty

Easy

Problem Statement

Given a sorted array of integers (which may include negative numbers), return a new array of the squares of each number, also sorted in non-decreasing order.

Intuition

When you square negative numbers, they become positive and their relative order can flip. For example, [-3, -1, 2] becomes [9, 1, 4] when squared naively. However, in a sorted array, the largest squared values must come from either the leftmost (most negative) or rightmost (most positive) elements. A two-pointer technique exploits this by comparing absolute values from both ends and filling the result array from the back.

Approach

  1. Create a result array of the same length.
  2. Place a left pointer at index 0 and a right pointer at the last index.
  3. Iterate from the last position of the result array down to 0.
  4. Compare the absolute values at left and right pointers.
  5. Whichever is larger, square it and place it at the current result position, then move that pointer inward.
  6. Return the result array.

Pseudocode

function sortedSquaredArray(array):
    result = new array of size length(array)
    left = 0
    right = length(array) - 1
    for idx from length(array) - 1 down to 0:
        if abs(array[left]) > abs(array[right]):
            result[idx] = array[left] * array[left]
            left += 1
        else:
            result[idx] = array[right] * array[right]
            right -= 1
    return result

Time & Space Complexity

  • Time: O(n) — Each element is visited exactly once via the two pointers.
  • Space: O(n) — For the output array. No additional auxiliary space is used.

Key Insights

  • The naive approach of squaring then sorting is O(n log n). The two-pointer approach achieves O(n).
  • The key observation is that the largest squared value is always at one of the two ends of the sorted input.
  • Filling the result from the back avoids the need for reversing.

Edge Cases

  • All non-negative numbers — the squared array is simply the element-wise square.
  • All non-positive numbers — the squared array is the reverse of the element-wise square.
  • Array contains zeros — zero squared is zero, handled naturally.
  • Single-element array — return that element squared.

Linked mentions