Frontend Beauty
ESC

Type to search the knowledge base.

Flatten a Nested Array

Interview flatten: stack vs recursion, depth cap, and treating only real arrays as nestable. Different problem from Array.flat polyfill details.

beginner6 min read
  • javascript
  • arrays
  • interview
  • recursion

A recursive flatten that push(...flatten(item)) works on the toy fixture [1, [2, [3]]] and then dies in two different ways. Deep nesting blows the call stack. A wide nested list blows the argument list on that spread. Interviewers are not asking you to reimplement Array.prototype.flat. They want a function you control: a result array, a heap stack, a depth cap, and a clear rule for what counts as nested.

Keep Array.flat Polyfill for species, generic this, and hole-for-hole spec tracing. This page is the other prompt.

Key takeaways

  • Drive the walk with an explicit stack (or index frames), not the JavaScript call stack.
  • Unwrap only Array.isArray values. Objects with length stay leaves.
  • Take a depth cap (Infinity by default). Depth 0 is identity for arrays you still treat as values.
  • push(...child) and recursion are both capacity bombs. Push elements one at a time.

A stack of leftovers beats a call-stack bomb

The recursive version is short, which is why people reach for it:

function flattenRecursive(value) {
  const out = [];
  for (const item of value) {
    if (Array.isArray(item)) out.push(...flattenRecursive(item));
    else out.push(item);
  }
  return out;
}

Two failure modes:

  1. Depth. Each nested array is a new stack frame. A few thousand wrappers ([0], then [ [0] ], and so on) throw RangeError: Maximum call stack size exceeded.
  2. Width. push(...flattenRecursive(item)) expands the whole child into arguments. A child with hundreds of thousands of leaves hits the same engine argument cap that makes [].concat(...huge) illegal.

The fix is to keep your stack on the heap and append one value at a time.

function flatten(input, depth = Infinity) {
  if (!Array.isArray(input)) {
    throw new TypeError('flatten: expected an array');
  }

  const depthNum = depth === Infinity ? Infinity : Math.trunc(Number(depth));
  const cap = Number.isNaN(depthNum) || depthNum < 0 ? 0 : depthNum;

  const out = [];
  const stack = [{ list: input, index: 0, depth: cap }];

  while (stack.length) {
    const frame = stack[stack.length - 1];
    if (frame.index >= frame.list.length) {
      stack.pop();
      continue;
    }

    const i = frame.index++;
    if (!(i in frame.list)) continue; // skip holes; see below

    const value = frame.list[i];
    if (Array.isArray(value) && frame.depth > 0) {
      stack.push({ list: value, index: 0, depth: frame.depth - 1 });
    } else {
      out.push(value);
    }
  }

  return out;
}

Frames remember the current index, so order stays left to right without reversing the child. That is easier to explain than “push indexes from the end.”

flatten([1, [2, [3, 4], 5]]);           // [1, 2, 3, 4, 5]
flatten([1, [2, [3]]], 1);              // [1, 2, [3]]
flatten([1, { 0: 2, length: 1 }]);      // [1, { 0: 2, length: 1 }]

Only real arrays nest

Array.isArray is the gate. It is realm-safe (an array from an iframe still unwraps) and it rejects:

  • { 0: 'a', 1: 'b', length: 2 }
  • arguments
  • NodeList, HTMLCollection
  • TypedArray views

If the interviewer hands you mixed trees (“also flatten array-likes”), switch the predicate on purpose and say so. The default prompt is lists of lists, not DOM collections.

for...of on an array skips holes and would also skip custom array-likes that are not iterable. The index loop above is honest about length.

Depth cap

Treat depth as “how many array wrappers you are still allowed to peel.”

Call Meaning
flatten(arr) Peel until no arrays remain (Infinity)
flatten(arr, 1) One level, same idea as default flat()
flatten(arr, 0) Copy one level of values, leave nested arrays intact

Infinity - 1 === Infinity, so the countdown does not need a branch. Non-numbers become 0 via NaN handling, which matches “do not unwrap” better than throwing. If the prompt wants a thrown TypeError on bad depth, throw.

Holes, as a follow-up, not the main plot

This is not the flat polyfill page, but you will be asked. Pick a rule and stick to it.

const sparse = [1, , [2, , 3]];

flatten(sparse);
// with `i in list`: [1, 2, 3]

// numeric loop without `in`:
// [1, undefined, 2, undefined, 3]

Spec flat skips holes. Many interview flatteners emit undefined. Say which one you wrote. for...of and forEach skip holes; a raw for does not.

null is not an array. It is a leaf. Same for undefined that is actually stored.

Reverse-stack variant (if they want less state)

Some solutions dump the input onto a stack and pop. To keep order you push children right to left:

function flattenPushPop(input, depth = Infinity) {
  const out = [];
  const stack = [{ value: input, depth }];

  while (stack.length) {
    const { value, depth: d } = stack.pop();
    if (Array.isArray(value) && d > 0) {
      for (let i = value.length - 1; i >= 0; i--) {
        if (i in value) stack.push({ value: value[i], depth: d - 1 });
      }
    } else {
      out.push(value);
    }
  }

  return out;
}

Same answers. The index-frame version is easier to pause and inspect (“I am in this array, at this i”). The push/pop version is fewer fields. Either is fine if you can trace [1, [2, 3], 4] without skipping 4.

Procedure

  1. Confirm input is an array. Decide depth (default Infinity).
  2. Allocate out and a stack of { list, index, depth }.
  3. While the stack is not empty, read the next index.
  4. If the value is an array and depth remains, push a new frame. Else append to out.
  5. Do not spread. Do not recurse on user data.
  6. State the hole rule and the Array.isArray rule out loud.

Complexity: each element is pushed and popped a constant number of times. Time is O(n) in the number of nested cells. Extra space is O(d) for depth d of the tree (index frames) plus the output.

Interview out-loud answer

I would not recurse. I keep a stack of the arrays I still have to walk, with an index and a remaining depth, and I append leaves to a result. Only Array.isArray values are nestable, so a { length } object stays a leaf. Default depth is Infinity; 1 matches a single unwrap. I skip holes with in unless you want them as undefined. I will not push(...child) because a wide nested list is a RangeError waiting to happen. Spec flat extras (species, generic this) are a different problem.

Further reading

Related guides