Solutions

1. Sorting

O(nlogn) time | O(1) space

Intuition

We can square every element and sort the array afterwards.

Algorithm

Iterate through the loop from the first element to the last element, replacing every element with its square.
Sort the array.
Return the array.

-4

-1

01234

-4 × -4 = 16

1 / 7

Code

def sortedSquares(nums: list[int]) -> list[int]:
    for i in range(len(nums)):
        nums[i] *= nums[i]
    nums.sort()
    return nums

/**
 * @param {number[]} nums
 * @returns {number[]}
 */
var sortedSquares = function (nums) {
  for (let i = 0; i < nums.length; i++) nums[i] *= nums[i]
  nums.sort((a, b) => a - b)
  return nums
}

import java.util.Arrays;

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

2. Two Pointers

O(n) time | O(1) space

Intuition

The input is sorted, so the greatest square is always at one of the two ends of the array, either the most negative element or the greatest positive one.

So we can compare the squares at both ends with two indexes, taking the greater one and moving the indexes towards each other.

Algorithm

Create a result array of the same length as the input.
Create left and right integer variables with the start and end indexes of the array as initial values.
Iterate through the loop from the last position of result to the first with i index.
- If the square at left is greater than the square at right, put it into result at i and move left one step to the right.
- Otherwise put the square at right into result at i and move right one step to the left.
Return result.

-4

-1

left right

16 < 100, put 100

1 / 6

Code

def sortedSquares(nums: list[int]) -> list[int]:
    result = [0] * len(nums)
    left, right = 0, len(nums) - 1
    for i in range(len(nums) - 1, -1, -1):
        left_square = nums[left] * nums[left]
        right_square = nums[right] * nums[right]
        if left_square > right_square:
            result[i] = left_square
            left += 1
        else:
            result[i] = right_square
            right -= 1
    return result

/**
 * @param {number[]} nums
 * @returns {number[]}
 */
var sortedSquares = function (nums) {
  const result = new Array(nums.length).fill(0)
  let left = 0
  let right = nums.length - 1
  for (let i = nums.length - 1; i >= 0; i--) {
    const leftSquare = nums[left] * nums[left]
    const rightSquare = nums[right] * nums[right]
    if (leftSquare > rightSquare) {
      result[i] = leftSquare
      left++
    } else {
      result[i] = rightSquare
      right--
    }
  }
  return result
}

class Solution {
    public int[] sortedSquares(int[] nums) {
        int[] result = new int[nums.length];
        int left = 0;
        int right = nums.length - 1;
        for (int i = nums.length - 1; i >= 0; i--) {
            int leftSquare = nums[left] * nums[left];
            int rightSquare = nums[right] * nums[right];
            if (leftSquare > rightSquare) {
                result[i] = leftSquare;
                left++;
            } else {
                result[i] = rightSquare;
                right--;
            }
        }
        return result;
    }
}