Sorted Squares

L3 Easy Two Pointers

Concept

For an already-sorted array that may contain negatives, the squares grow from the outside in — the biggest magnitude is always at one of the two ends.

Given an array of integers nums sorted in non-decreasing order, return a new array holding the square of every element, arranged in non-decreasing order. Solve it in O(n) time.

Examples

▸ nums = [-4, -1, 0, 3, 10]

→ [0, 1, 9, 16, 100]

▸ nums = [-7, -3, 2, 3, 11]

→ [4, 9, 9, 49, 121]

▸ nums = [-3, -1]

→ [1, 9]

Progressive Hints

Hint 1 · Nudge

The extremes hold the biggest squares. Which end do you lay down next?

Hint 2 · Plan

Put one pointer at each end. Compare the squares of the two end values; the larger one is the largest remaining square, so place it at the back of the answer and move that end inward. Keep going until the pointers meet.

Hint 3 · Approach

result of the same size as nums. left = 0, right = last index. Fill from the back: if square(nums[left]) > square(nums[right]), place square(left) and advance left; otherwise place square(right) and retreat right. Return result.

Output

// Run your code to see the output here.