easy

Squares of a Sorted Array

Square every value in a sorted array and return the result sorted, without re-sorting.

1. Define the problem

Squares of a Sorted Array

Given an integer array nums sorted in non-decreasing order, which may include negative numbers, return an array of the squares of each number, also sorted in non-decreasing order . Because negative numbers square positive too, the largest square is always found at one of the two ends of the array. Use two pointers starting from both ends inward , comparing the absolute values at each end and filling the result array from the back.

Constraints

  • 1 ≤ nums.length ≤ 104
  • -104 ≤ numsi ≤ 104
  • nums is sorted in non-decreasing order

Example

Inputnums = [-4, -1, 0, 3, 10]
Output[0, 1, 9, 16, 100]

Explanation The squares are [16, 1, 0, 9, 100]; sorted in non-decreasing order they become [0, 1, 9, 16, 100].

2. Know the words first

In plain terms

Non-decreasing order
Each value is greater than or equal to the one before it, so repeats are allowed — for example, [1, 2, 2, 5] is in non-decreasing order.
3. Visualize the solution

Compare both ends, fill the result from the back

Compare both ends, fill the result from the back
Statusinit

left=0 (-4, sq 16) vs right=4 (10, sq 100): 100 is larger — write 100 to the last free slot of the result, right moves left.

What happens in this step

left = 0 (value -4, sq 16), right = 4 (value 10, sq 100)
compare 16 vs 100

100 is larger — write 100 into the last free result slot (index 4), and right moves inward to index 3.
Step 1 of 5

Steps to visualize

  1. Place one pointer at the start and one at the end of nums.
  2. Compare the absolute values at both pointers.
  3. Write the larger square into the last free slot of the result array.
  4. Move the pointer with the larger absolute value one step inward.
  5. Repeat until the pointers cross, filling the result from back to front.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Compare both ends, fill the result from the back
Statusinit

left=0 (-4, sq 16) vs right=4 (10, sq 100): 100 is larger — write 100 to the last free slot of the result, right moves left.

What happens in this step

left = 0 (value -4, sq 16), right = 4 (value 10, sq 100)
compare 16 vs 100

100 is larger — write 100 into the last free result slot (index 4), and right moves inward to index 3.
Step 1 of 5
5. Solution

Solution

solution.tsTypeScript
function sortedSquares(nums) {
  const n = nums.length;
  const result = new Array(n);
  let left = 0;
  let right = n - 1;
  let writeIndex = n - 1;

  while (left <= right) {
    const leftSq = nums[left] * nums[left];
    const rightSq = nums[right] * nums[right];

    if (leftSq > rightSq) {
      result[writeIndex] = leftSq;
      left++;
    } else {
      result[writeIndex] = rightSq;
      right--;
    }
    writeIndex--;
  }

  return result;
}
Time
O(n)
Space
O(n)
6. Test cases

Test cases

InputExpectedCovers
nums = [-4, -1, 0, 3, 10][0, 1, 9, 16, 100]example from the docstring
nums = [-7, -3, -1][1, 9, 49]every value is negative
nums = [1, 2, 3][1, 4, 9]every value is already positive
nums = [5][25]smallest valid input, a single positive element
nums = [-5][25]smallest valid input, a single negative element
nums = [0, 0, 0][0, 0, 0]every value is zero, no ordering effect
nums = [-2, 2][4, 4]equal absolute values at both ends produce a tie

Keep reading