Квадратирование отсортированного массива за один проход

Условие

Дан массив целых чисел, упорядоченный по возрастанию. Требуется получить массив, в котором каждый элемент заменён на свой квадрат, при этом полученный массив также должен оставаться отсортированным по возрастанию. Решение должно быть выполнено за один проход по исходному массиву.

Ответ

Наибольший квадрат находится на одном из концов отсортированного массива. Сравнивайте модули крайних значений и заполняйте результат с конца.

function sortedSquares(numbers) {
  const result = Array(numbers.length);
  let left = 0, right = numbers.length - 1;
  for (let index = result.length - 1; index >= 0; index--) {
    if (Math.abs(numbers[left]) > Math.abs(numbers[right])) {
      result[index] = numbers[left] ** 2; left++;
    } else { result[index] = numbers[right] ** 2; right--; }
  }
  return result;
}

Для [-4,-1,0,3] результат [0,1,9,16]. Каждый элемент обрабатывается один раз: время O(n), память O(n) для ответа. Исходный массив не меняется. Простое map(x => x*x) не сохраняет сортировку при наличии отрицательных чисел.