Coding problem · Easy · Basics

Squares of a Sorted Array

Easy Algorithms & data structures

nums is sorted in ascending order and may contain negative numbers. Return the squares of each number, sorted ascending.

Example 1

Input: nums = [-4,-1,0,3,10]
Output: [0,1,9,16,100]

Example 2

Input: nums = [-7,-3,2,3,11]
Output: [4,9,9,49,121]

Hints

Hint 1

Squaring then sorting works in O(n log n).

Hint 2

The largest squares are at the two ends of the array. Two pointers can fill the answer from the back in O(n).

Write and run your solution

Loading the editor… (JavaScript is required to run code in your browser.)

Solution and explanation

Show the solution

Time O(n) · Space O(n)

Compare the absolute values at the left and right ends, place the bigger square at the end of the output, and move that pointer inward.

Reference solution

function sortedSquares(nums) {
  const out = new Array(nums.length);
  let l = 0, r = nums.length - 1;
  for (let k = nums.length - 1; k >= 0; k--) {
    if (Math.abs(nums[l]) > Math.abs(nums[r])) out[k] = nums[l] * nums[l++];
    else out[k] = nums[r] * nums[r--];
  }
  return out;
}

function sortedSquares(nums: number[]): number[] {
  const out = new Array<number>(nums.length);
  let l = 0, r = nums.length - 1;
  for (let k = nums.length - 1; k >= 0; k--) {
    if (Math.abs(nums[l]) > Math.abs(nums[r])) { out[k] = nums[l] * nums[l]; l++; }
    else { out[k] = nums[r] * nums[r]; r--; }
  }
  return out;
}

def sorted_squares(nums: list[int]) -> list[int]:
    out = [0] * len(nums)
    l, r = 0, len(nums) - 1
    for k in range(len(nums) - 1, -1, -1):
        if abs(nums[l]) > abs(nums[r]):
            out[k] = nums[l] ** 2
            l += 1
        else:
            out[k] = nums[r] ** 2
            r -= 1
    return out

<?php

function sortedSquares(array $nums): array
{
    $out = array_map(fn ($n) => $n * $n, $nums);
    sort($out);
    return $out;
}

class Solution {
    public int[] sortedSquares(int[] nums) {
        int[] out = new int[nums.length];
        int l = 0, r = nums.length - 1;
        for (int k = nums.length - 1; k >= 0; k--) {
            if (Math.abs(nums[l]) > Math.abs(nums[r])) { out[k] = nums[l] * nums[l]; l++; }
            else { out[k] = nums[r] * nums[r]; r--; }
        }
        return out;
    }
}

Was this page helpful?