DSA Tracker

Visualize

Squares of a Sorted Array

time O(n)space O(n)

The key insight: given a sorted array that may contain negative numbers, the square of a negative number is positive and large in magnitude when the number has large absolute value. Since the array is sorted, the largest square could come from either end (the most negative or the most positive). Use two pointers starting at both ends, compare the squared magnitudes, and fill the result array from the back (largest square first) since either end could hold the largest absolute value.

Details

Animated on: Given nums = [-4, -1, 0, 3, 10], return the squares of each number sorted in non-decreasing order. Answer: [0, 1, 9, 16, 100].

Problem:Squares of a Sorted ArrayEasy

Two Pointers

step 1 / 12

-4
[0]
-1
[1]
0
[2]
3
[3]
10
[4]

left = 0, right = n - 1 = 4, pos = n - 1 = 4: initialize two pointers at both ends and a result array position at the back. The squared magnitudes are 16 and 100 respectively.

  • left=0· arr[0] = -4
  • right=4· arr[4] = 10
Pseudocode
1FUNCTION sortedSquares(nums):
2  n = length of nums
3  result = a new array of length n
4  left = 0, right = n - 1
5  pos = n - 1
6  WHILE left <= right:
7    leftSquare = nums[left] * nums[left]
8    rightSquare = nums[right] * nums[right]
9    IF leftSquare > rightSquare:
10      result[pos] = leftSquare
11      left = left + 1
12    ELSE:
13      result[pos] = rightSquare
14      right = right - 1
15    pos = pos - 1

← / → step · space play · Home restart

Every step in words

Show all 12 steps
  1. left = 0, right = n - 1 = 4, pos = n - 1 = 4: initialize two pointers at both ends and a result array position at the back. The squared magnitudes are 16 and 100 respectively.
  2. leftSquare = nums[left]^2 = (-4)^2 = 16, rightSquare = nums[right]^2 = 10^2 = 100. Compare: 16 < 100, so the larger square is at the right end.
  3. result[pos=4] = rightSquare = 100: place the larger square at the back of the result array. Decrease right to 3 and pos to 3. Result so far: [_, _, _, _, 100].
  4. leftSquare = (-4)^2 = 16, rightSquare = 3^2 = 9. Compare: 16 > 9, so the larger square is at the left end.
  5. result[pos=3] = leftSquare = 16: place the left square at the current back position. Increase left to 1 and decrease pos to 2. Result so far: [_, _, _, 16, 100].
  6. leftSquare = (-1)^2 = 1, rightSquare = 3^2 = 9. Compare: 1 < 9, so the larger square is at the right end.
  7. result[pos=2] = rightSquare = 9: place the right square at position 2. Decrease right to 2 and pos to 1. Result so far: [_, _, 9, 16, 100].
  8. leftSquare = (-1)^2 = 1, rightSquare = 0^2 = 0. Compare: 1 > 0, so the larger square is at the left end.
  9. result[pos=1] = leftSquare = 1: place the left square at position 1. Increase left to 2 and decrease pos to 0. Result so far: [_, 1, 9, 16, 100].
  10. leftSquare = 0^2 = 0, rightSquare = 0^2 = 0. Compare: 0 > 0 is false, so the else branch runs — the right square is taken.
  11. result[pos=0] = rightSquare = 0: place the final square. right decreases to 1; left stays at 2. Now left(2) > right(1), so the loop terminates.
  12. Final result: [0, 1, 9, 16, 100]. All squares are placed in non-decreasing order. Return the result.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Squares of a Sorted Array in the editorAll Two Pointers problemsBack to roadmap