Pattern visualizer

Squares of a Sorted Array

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

Two Pointers

time O(n)space O(n)step 1 / 12

-4

[0]

-1

[1]

[2]

[3]

[4]

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

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

Where to practice Two Pointers

Practice Two Pointers problems All Two Pointers problems Back to roadmap