Produce the Sorted List of Squared Values

Easy10–15 min

Topics

ArrayTwo Pointer

Companies

AmazonGoogleMicrosoftMeta

Given an integer array nums sorted in non-decreasing order (it may contain negative values), return a new array holding the square of every element, with the result itself sorted in non-decreasing order. Squaring can scramble the order — a large negative number produces a large positive square. Since the input is already sorted, you can rebuild the sorted result in a single O(n) pass with two pointers instead of squaring and re-sorting from scratch.

Test Case 1:

Input:nums = [-6, -3, -1, 2, 5]

Output:[1, 4, 9, 25, 36]

Explanation:Squaring removes the sign, so the ordering can shift completely — the two most negative values (-6 and -3) produce the two largest squares here.

Test Case 2:

Input:nums = [-2, 0, 3]

Output:[0, 4, 9]

Explanation:0 squares to 0, and stays the smallest.

Test Case 3:

Input:nums = [1, 2, 4]

Output:[1, 4, 16]

Explanation:All values are already non-negative, so squaring keeps the same relative order.

Constraints

◆1 ≤ nums.length ≤ 10⁴
◆-10⁴ ≤ nums[i] ≤ 10⁴
◆nums is sorted in non-decreasing order

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

🧪Try your own test case

nums (sorted, comma-separated) — 1-12 integers, sorted ascending (negatives allowed)

1	class Solution {
2	public int[] sortedSquaredValues(int[] nums) {
3	int n = nums.length;
4	int[] result = new int[n];
5	int left = 0, right = n - 1;
6	int pos = n - 1;
7	while (left <= right) {
8	int leftSq = nums[left] * nums[left];
9	int rightSq = nums[right] * nums[right];
10	if (leftSq > rightSq) {
11	result[pos--] = leftSq;
12	left++;
13	} else {
14	result[pos--] = rightSq;
15	right--;
16	}
17	}
18	return result;
19	}
20	}
21

Array

-6

-3

-1

↑left

↑right

Array

Variables

left0

right4

pos4

INITIALIZE

Set left and right at the two ends, and pos at the last slot of the result array — we'll fill result from the back with the larger square each round.

Step 1 / 12

Approach & Solutions

Brute Force

Brute

Square every element in a single pass, then sort the resulting array. Simple and correct, but it throws away the fact that the input was already sorted, paying for a full sort we don't strictly need.

TimeO(n log n)

SpaceO(n)

Java

Try it out

class Solution {
    public int[] sortedSquaredValues(int[] nums) {
        int[] result = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            result[i] = nums[i] * nums[i];
        }
        Arrays.sort(result);
        return result;
    }
}

Optimal — Two Pointers

Optimal

Because nums is sorted, the largest square always sits at one of the two ends — either the most negative value or the most positive one. Walk left and right inward, comparing the two candidate squares, and drop the bigger one into the back of a result array. This fills the output from largest to smallest in a single pass, with no sorting needed.

TimeO(n)