#Arrays#Stack

Flatten an Array Without Recursion

The same result as the recursive flatten, with your own stack instead of the call stack.

By Pratik RaiMedium
Open Code Editor

Write flattenIterative(arr) returning every value from a deeply nested array in order.

The function must not call itself. This is the follow-up an interviewer asks once you have written the recursive version, and the point is the depth limit: recursion runs out of stack, an explicit stack runs out of memory.

Examples

Input:

JSfile.javascript
1flattenIterative([1, [2, [3, [4]]], 5]);

Output:

[1, 2, 3, 4, 5]

Order is preserved, however deep the nesting goes.

Constraints

  • Nesting may be tens of thousands deep
  • Values are numbers

Notes

  • Popping from the end visits items in reverse, so the result needs reversing — or push in the other order.

Goal: Flatten completely using an explicit stack, with no recursive call.

Sources

Frequently asked questions

How do you flatten an array without recursion?
Use an explicit stack. Pop an item; if it is an array push its contents back on, otherwise collect it. Repeat until the stack is empty.
Why would an interviewer ask for the non-recursive version?
Because recursion is bounded by the call stack, which gives out around ten thousand frames and throws `RangeError`. Your own stack lives in the heap, so the depth limit becomes memory instead.
Why does the result come out backwards?
Popping takes from the end, so items are visited in reverse. Either reverse the result at the end, or push children in reverse order so they pop in the original one.
Is Array.prototype.flat recursive?
Its behaviour is specified rather than its implementation, and engines implement it natively without consuming your JavaScript call stack. `flat(Infinity)` handles very deep arrays that a hand-written recursion would not.

Related Challenges

Continue learning with these related challenges

View All
JavaScript

Resolve Promises Sequentially

Run promises one after another and collect the results in order — built with .then chaining, no async/await.

JavaScript · ES6 — Pratik Rai ·

JavaScript

Array.prototype.groupBy

Group an array into buckets by a key function — now a real language feature as Object.groupBy.

JavaScript · ES6 — Pratik Rai ·

JavaScript

Flat List to Tree

Turn a flat array of nodes with parentId into a nested tree — the shape behind every file explorer and nested menu.

JavaScript · ES6 — Pratik Rai ·