Задача: 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.