Flatten an Array Without Recursion
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
flattenIterative([1, [2, [3, [4]]], 5]);[1, 2, 3, 4, 5]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.
Hints
Flatten an Array Without Recursion (reference solution)
One way to do it. The Editorial tab walks through why it is written this way.
Solution
1function flattenIterative(arr) {
2 const out = [];
3 const stack = arr.slice();
4 while (stack.length > 0) {
5 const item = stack.pop();
6 if (Array.isArray(item)) {
7 for (let i = 0; i < item.length; i += 1) stack.push(item[i]);
8 } else {
9 out.push(item);
10 }
11 }
12 return out.reverse();
13}Editorial: Flatten an Array Without Recursion
Replacing the call stack
The recursive flatten is three lines and correct. The follow-up asks for it without recursion, and the reason is depth: recursion is bounded by the engine's call stack, which gives out somewhere around ten thousand frames and throws RangeError.
Approach
Do the same job with a stack you own.
Implementation
function flattenIterative(arr) { const out = []; const stack = arr.slice(); while (stack.length > 0) { const item = stack.pop(); if (Array.isArray(item)) { for (let i = 0; i < item.length; i += 1) stack.push(item[i]); } else { out.push(item); } } return out.reverse(); }
Worth knowing
Popping from the end visits items in reverse, so the result comes out backwards and needs reversing. Pushing children in reverse and popping from the front is the alternative; say which you chose and why.
The suite includes a twenty-thousand-deep array specifically because a recursive implementation throws on it. The tradeoff is honest rather than free: the recursion limit becomes a memory limit, which is much larger but not infinite.