3.implement-Array.prototype.flat.md

3. implement Array.prototype.flat()

Problem

https://bigfrontend.dev/problem/implement-Array-prototype.flat

Problem Description

There is already Array.prototype.flat() in JavaScript (ES2019), which reduces the nesting of Array.

Could you manage to implement your own one?

Here is an example to illustrate

console.log(flat([1, [2, [3, [4, [5]]]]], 1)); // [1, 2, [3, [4, [5]]]
console.log(flat([1, [2, [3, [4, [5]]]]], 2)); // [1, 2, 3, [4, [5]]
console.log(flat([1, [2, [3, [4, [5]]]]], 3)); // [1, 2, 3, 4, [5]
console.log(flat([1, [2, [3, [4, [5]]]]], 4)); // [1, 2, 3, 4, 5]
console.log(flat([1, 2, 3, [4, 5, [6, 7, 8, [9, 10]]]], Infinity)) // [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

follow up

Are you able to solve it both recursively and iteratively?

Recursive Solution

/**
 * @param { Array } arr
 * @param { number } depth
 */
const flat = (array, depth = 1) => {
  let flatArray = [];
  array.forEach((element) => {
    if (Array.isArray(element) && depth > 0) {
      flatArray.push(...flat(element, depth - 1));
    } else {
      flatArray.push(element);
    }
  });
  return flatArray;
};

Recursive Solution with Reduce

/**
 * @param { Array } arr
 * @param { number } depth
 */
function flat(arr, depth = 1) {
  return arr.reduce(
    (acc, item) =>
      Array.isArray(item) && depth > 0
        ? acc.concat(flat(item, depth - 1))
        : [...acc, item],
    []
  );
}

Iterative Solution with Stack

/**
 * @param { Array } arr
 * @param { number } depth
 */
function flat(arr, depth = 1) {
  const flatArray = [];
  let stack = [...arr.map((item) => [item, depth])];

  while (stack.length > 0) {
    const [item, depth] = stack.pop();
    if (Array.isArray(item) && depth > 0) {
      stack.push(...item.map((el) => [el, depth - 1]));
    } else {
      flatArray.push(item);
    }
  }

  return flatArray.reverse();
}

Reference

Problem Discuss