re:re:actable
Урок 023 минуты чтения

Задача: flat

На этой странице
Кратко

flat(arr, depth = 1) разворачивает вложенные массивы на заданную глубину: flat([1, [2, [3, [4]]]], 2) → [1, 2, 3, [4]]. Решение рекурсивное (обход элементов, рекурсия для массивов, пока depth > 0) или итеративное со стеком — оно не упирается в лимит стека вызовов. Нужно помнить про depth = Infinity, дырки в массиве и то, что нативный flat их удаляет.

Вопрос

Реализуйте flat(arr, depth = 1) без использования Array.prototype.flat. Сделайте рекурсивную и итеративную версии.

Рекурсивное решение

function flat(arr, depth = 1) {
  const result = [];
 
  for (const item of arr) {
    if (Array.isArray(item) && depth > 0) {
      result.push(...flat(item, depth - 1));
    } else {
      result.push(item);
    }
  }
 
  return result;
}
flat([1, [2, [3, [4]]]]);            // [1, 2, [3, [4]]]
flat([1, [2, [3, [4]]]], 2);         // [1, 2, 3, [4]]
flat([1, [2, [3, [4]]]], Infinity);  // [1, 2, 3, 4]
flat([]);                            // []

for...of по разреженному массиву вернет undefined вместо дыр. Если нужно повторить нативное поведение (дыры удаляются), используйте forEach или проверку i in arr.

Через reduce

const flat = (arr, depth = 1) =>
  depth > 0
    ? arr.reduce((acc, x) => acc.concat(Array.isArray(x) ? flat(x, depth - 1) : [x]), [])
    : arr.slice();

push(...bigArray) может упасть на очень больших массивах (лимит аргументов), concat такой проблемы не имеет.

Итеративное решение со стеком (полное разворачивание)

function flatDeep(arr) {
  const stack = [...arr];
  const result = [];
 
  while (stack.length) {
    const item = stack.pop();
    if (Array.isArray(item)) {
      stack.push(...item);             // развернуть и обработать позже
    } else {
      result.push(item);
    }
  }
 
  return result.reverse();             // pop берет с конца — восстанавливаем порядок
}
 
flatDeep([1, [2, [3, [4, [5]]]]]);     // [1, 2, 3, 4, 5]

Итеративное с глубиной

function flatIterative(arr, depth = 1) {
  const stack = arr.map((item) => [item, depth]).reverse(); // первый элемент — на вершине стека
  const result = [];
 
  while (stack.length) {
    const [item, d] = stack.pop();
    if (Array.isArray(item) && d > 0) {
      for (let i = item.length - 1; i >= 0; i--) stack.push([item[i], d - 1]); // в обратном порядке
    } else {
      result.push(item);
    }
  }
 
  return result;
}

Доп. вопросы интервьюера

  • Сложность? O(n) по общему числу элементов, память — O(n) + глубина рекурсии.
  • Почему итеративная версия? глубина вложенности в тысячи уровней переполнит стек вызовов.
  • Как развернуть объект с вложенными объектами? см. задачу о flatten объекта.
  • Есть ли нативный метод? arr.flat(depth) и arr.flatMap(fn).

Что важно помнить

  • Проверяйте Array.isArray, а не typeof === "object".
  • По умолчанию depth = 1, как у нативного flat.
  • push(...arr) на огромных массивах может выбросить RangeError.
  • Не мутируйте входной массив.

Мини-шпаргалка

Рекурсия: для каждого элемента — если массив и depth > 0, развернуть flat(item, depth - 1), иначе добавить. depth = Infinity — полностью. Итеративно: стек + pop + reverse. O(n).

Документация

MDN: Array.prototype.flat, MDN: Array.isArray, MDN: Array.prototype.flatMap.

Дочитали до конца?
Отметьте урок — прогресс сохранится в браузере.

Поиск

Поиск по урокам