Рекурсивный flatten массива

Решение

Flattening — преобразование вложенного массива в одномерный. Это классическая задача на рекурсию, которая хорошо показывает понимание рекурсивных алгоритмов.

Подход 1: Классическая рекурсия

function flatten(arr: any[]): any[] {
  const result: any[] = [];
  
  for (const item of arr) {
    if (Array.isArray(item)) {
      // Рекурсивно вызываем flatten и добавляем элементы
      result.push(...flatten(item));
    } else {
      // Если не массив, добавляем элемент напрямую
      result.push(item);
    }
  }
  
  return result;
}

// Примеры:
console.log(flatten([1, [2, [3, [4]], 5]]));
// [1, 2, 3, 4, 5]

console.log(flatten([[1, 2], [3, [4, [5, [6]]]]]]));
// [1, 2, 3, 4, 5, 6]

Как работает:

1. Проходим по каждому элементу массива
2. Если элемент — массив, рекурсивно вызываем flatten и разворачиваем результат
3. Если нет, добавляем элемент в результат

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

Подход 2: С использованием reduce

function flatten(arr: any[]): any[] {
  return arr.reduce((acc, item) => {
    if (Array.isArray(item)) {
      // Объединяем результат рекурсивного вызова с аккумулятором
      return acc.concat(flatten(item));
    } else {
      // Добавляем элемент
      return acc.concat(item);
    }
  }, []);
}

Особенности:

• Функциональный стиль
• concat создаёт новый массив (неэффективнее спреда)
• Более декларативно

Подход 3: С использованием спреда в reduce

function flatten(arr: any[]): any[] {
  return arr.reduce<any[]>((acc, item) => {
    return Array.isArray(item) ? [...acc, ...flatten(item)] : [...acc, item];
  }, []);
}

Примечание: создание новых массивов через спред — менее эффективно, чем push.

Подход 4: С использованием flatMap (встроенный метод)

function flatten(arr: any[]): any[] {
  return arr.flatMap(item => 
    Array.isArray(item) ? flatten(item) : item
  );
}

Преимущества:

• Очень компактная запись
• Встроенный метод оптимизирован
• Прямое назначение flatMap — раскрывать массивы

Подход 5: Итеративная версия со стеком (без рекурсии)

function flatten(arr: any[]): any[] {
  const stack = [...arr].reverse();
  const result: any[] = [];
  
  while (stack.length > 0) {
    const item = stack.pop()!;
    
    if (Array.isArray(item)) {
      // Добавляем элементы массива в стек в обратном порядке
      stack.push(...item.reverse());
    } else {
      result.push(item);
    }
  }
  
  return result;
}

Преимущества:

• Избегаем рекурсии (нет риска переполнения стека)
• Пространственная сложность: O(max_width) вместо O(depth)
• Для очень глубоких структур это решение лучше

Подход 6: Генератор для ленивого вычисления

function* flattenGenerator(arr: any[]): Generator<any> {
  for (const item of arr) {
    if (Array.isArray(item)) {
      yield* flattenGenerator(item);
    } else {
      yield item;
    }
  }
}

function flatten(arr: any[]): any[] {
  return [...flattenGenerator(arr)];
}

Когда использовать:

• Если нужна ленивая оценка
• Если массив очень большой и может потребоваться обработка только части

Подход 7: С ограничением глубины

function flatten(arr: any[], depth: number = Infinity): any[] {
  if (depth === 0) {
    return arr;
  }
  
  const result: any[] = [];
  
  for (const item of arr) {
    if (Array.isArray(item) && depth > 0) {
      result.push(...flatten(item, depth - 1));
    } else {
      result.push(item);
    }
  }
  
  return result;
}

// Примеры:
console.log(flatten([1, [2, [3, [4]], 5]], 1));
// [1, 2, [3, [4]], 5] — flatten одного уровня

console.log(flatten([1, [2, [3, [4]], 5]], 2));
// [1, 2, 3, [4], 5] — flatten двух уровней

Тестирование

// Базовые случаи
console.log(flatten([1, [2, [3, [4]], 5]]));
// [1, 2, 3, 4, 5]

console.log(flatten([[1, 2], [3, [4, [5, [6]]]]]));  
// [1, 2, 3, 4, 5, 6]

// Граничные случаи
console.log(flatten([]));
// []

console.log(flatten([1, 2, 3]));
// [1, 2, 3] — уже плоский

console.log(flatten([[[[[1]]]]]));  
// [1] — очень глубокий

console.log(flatten([1, null, [2, undefined, [3]]]));
// [1, null, 2, undefined, 3] — с null и undefined

console.log(flatten([1, "string", [2, {}, [3]]]));
// [1, "string", 2, {}, 3] — с разными типами

Сравнение подходов

Рекомендация для интервью

Начните с классической рекурсии — она показывает:

• Понимание рекурсивных алгоритмов
• Проверку типов (Array.isArray)
• Простоту и читаемость

Если интервьюер спросит про производительность на глубоких структурах, предложите итеративный вариант со стеком.

Ключевые моменты:

• Array.isArray() — правильный способ проверить, является ли значение массивом
• Спред оператор ... разворачивает результат рекурсивного вызова
• Глубина рекурсии может быть проблемой для очень глубоких массивов
• flatMap — встроенная функция для этой задачи в современном JS