Flatten a nested array (recursion)

Medium TimeO(n) total elements SpaceO(d) depth

An array can hold plain values or other arrays, nested to any depth. Given one, return a single flat array holding every value in its original left-to-right order, so [1, [2, [3, 4]], 5] becomes [1, 2, 3, 4, 5]. Empty arrays contribute nothing.

Examples

Example 1

Input
arr = [1, [2, [3, 4]], 5]
Output
[1,2,3,4,5]
The same five values in the same order, with the brackets gone.

Example 2

Input
arr = [[], [1, []], 2]
Output
[1,2]
Only 1 and 2 are values; the two empty arrays add nothing.

The Code

function flatten(arr) {
  const out = [];
  for (const item of arr) {
    if (Array.isArray(item)) {
      for (const x of flatten(item)) out.push(x);
    } else {
      out.push(item);
    }
  }
  return out;
}
flatten([1, [2, [3, 4]], 5]);
Done
Step through flatten([1, [2, [3, 4]], 5]) call by call

More like this

All recursion examples (13) →