Перейти к содержимому
JS/TS Interview Tutorial

Array.flat рекурсивный

flattenDeep — разминочная задача на понимание рекурсии, стека и граничных случаев. Интервьюер ожидает: рекурсивную версию с параметром depth, итеративную через стек (без ограничения глубины рекурсии), упоминание нативного Array.prototype.flat(Infinity) и корректную обработку sparse arrays.

Рекурсивная, итеративная и reduce-версии с поддержкой параметра depth:

// ─── 1. Рекурсивная ───────────────────────────────────────────────────────
/**
 * @param {any[]} arr
 * @param {number} [depth=Infinity]
 * @returns {any[]}
 */
function flattenDeep(arr, depth = Infinity) {
  const result = [];
  for (const item of arr) {
    if (Array.isArray(item) && depth > 0) {
      result.push(...flattenDeep(item, depth - 1));
    } else {
      result.push(item);
    }
  }
  return result;
}


// ─── 2. Итеративная через стек — нет ограничения стека вызовов ────────────
function flattenIterative(arr, depth = Infinity) {
  // Стек хранит [value, remainingDepth]; reverse() чтобы pop() = leftmost
  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;
}


// ─── 3. reduce-однострочник (только Infinity-глубина) ─────────────────────
const flattenReduce = arr =>
  arr.reduce(
    (acc, val) => Array.isArray(val) ? acc.concat(flattenReduce(val)) : [...acc, val],
    [],
  );

Нативный flat и сравнение производительности / граничные случаи:

// ─── Нативный API — всегда предпочтительнее в продакшне ──────────────────
[1, [2, [3, [4]]]].flat();          // [1, 2, [3, [4]]]  depth=1 (default)
[1, [2, [3, [4]]]].flat(2);         // [1, 2, 3, [4]]
[1, [2, [3, [4]]]].flat(Infinity);  // [1, 2, 3, 4]


// ─── Граничные случаи ─────────────────────────────────────────────────────
flattenDeep([]);                   // []     — пустой массив
flattenDeep([1, 2, 3]);            // [1, 2, 3] — уже плоский
flattenDeep([[1], [2], [3]]);      // [1, 2, 3]
flattenDeep([1, [2, [3, [4]]]]);   // [1, 2, 3, 4]


// Параметр depth
flattenDeep([1, [2, [3]]], 1);     // [1, 2, [3]] — только 1 уровень
flattenDeep([1, [2, [3]]], 0);     // [1, [2, [3]]] — без разворачивания


// Sparse arrays: нативный flat убирает дыры
[1, , 3].flat();                   // [1, 3] ← дыра удалена (!)
// Итератор for-of тоже пропускает дыры → рукописная версия ведёт себя так же


// ─── Производительность ───────────────────────────────────────────────────
// flat(Infinity) — C++ реализация в V8, оптимальная
// Рекурсивная JS — ограничена ~10k уровнями вложенности (стек вызовов)
// Итеративная JS — нет ограничения глубины, чуть многословнее
// ...concat(...items) — не подходит для больших массивов: spread ограничен


const veryDeep = JSON.parse('['.repeat(5000) + '1' + ']'.repeat(5000));
// flattenDeep(veryDeep) → RangeError: Maximum call stack size exceeded!
// flattenIterative(veryDeep) → [1] ✓
console.assert(flattenIterative(veryDeep)[0] === 1);

Сложность

  • Время: O(n) где n = суммарное количество элементов на всех уровнях
  • Память: O(n) для результата + O(d) стек где d = глубина вложенности

Итог: flattenDeep: рекурсия с depth; итеративная через стек [item, depth] без ограничения стека вызовов. Нативный flat(Infinity) — лучший выбор в продакшне.