Iterative solution for smoothing the nth nested array in Javascript

Question

Can someone show me an iterative solution for the following problem? I solved this recursively, but struggled with an iterative solution. (Question about a technical interview on Facebook)

Input: [1, {a: 2}, [3], [[4, 5], 6], 7] Output: [1, {a: 2}, 3, 4, 5, 6, 7] 

The solution should work with the nth nested elements of the array (i.e. it should work if someone changes the values ​​/ placement of the array in the above example)

Recursive solution:

 var flatten = function(input) { var result = []; input.forEach(function(element) { result = result.concat(Array.isArray(element) ? flatten(element) : element); }); return result; } 

Answer 1

Here is one way:

 var input = [1, {a: 2}, [3], [[4, 5], 6], 7]; function flatten(input) { var i, placeHolder = [input], lastIndex = [-1], out = []; while (placeHolder.length) { input = placeHolder.pop(); i = lastIndex.pop() + 1; for (; i < input.length; ++i) { if (Array.isArray(input[i])) { placeHolder.push(input); lastIndex.push(i); input = input[i]; i = -1; } else out.push(input[i]); } } return out; } flatten(input); 

Explanation:. If you iterate over a nested structure, you just need to remember where you were, keeping the current array and position before moving into the nested array (this is usually taken care of through the stack for recursive solutions).

Note. If you reuse placeHolder and lastIndex arrays, you won’t need to recreate them all the time. Maybe something like this:

 var flatten = function(){ var placeHolder = [], lastIndex = []; placeHolder.count = 0; lastIndex.count = 0; return function flatten(input) { var i, out = []; placeHolder[0] = input; placeHolder.count = 1; lastIndex[0] = -1; lastIndex.count = 1; while (placeHolder.count) { input = placeHolder[--placeHolder.count]; i = lastIndex[--lastIndex.count] + 1; for (; i < input.length; ++i) { if (Array.isArray(input[i])) { placeHolder[placeHolder.count++] = input; lastIndex[lastIndex.count++] = i; input = input[i]; i = -1; } else out.push(input[i]); } } return out; } }(); 

This is even faster (for a flat iteration), and fewer problems with garbage collectors causes it many times. The speed is very close to the speed of calling a recursive function in Chrome and is many times faster than the recursion in FireFox and IE.

I recreated Tomalak tests here, as the old jsPerf is broken for editing: https://jsperf.com/iterative-array-flatten-2

Answer 2

How about this?

 inp = [1, {a: 2}, [3], [[4, 5], 6], 7] out = inp; while(out.some(Array.isArray)) out = [].concat.apply([], out); document.write(JSON.stringify(out)); 

Answer 3

It works, but is not recommended:

 var flatten = function(input) { return eval("[" + JSON.stringify(input). replace(/\[/g,"").replace(/\]/g,"") + "]"); } 

Answer 4

Here is a solution that smoothes in place.

 function flatten(arr) { var i = 0; if (!Array.isArray(arr)) { /* return non-array inputs immediately to avoid errors */ return arr; } while (i < arr.length) { if (Array.isArray(arr[i])) { arr.splice(i, 1, ...arr[i]); } else { i++; } } return arr; } 

This solution iterates through the array, smoothing each element one nesting level at a time, until it can no longer be flattened.

Answer 5

 function flatten(array){ for(var i=0;i<array.length;i++) if(Array.isArray(array[i])) array.splice.apply(array,[i,1].concat(array[i--])); return array; } 

This solution in place is faster than Lupe, now that I have removed all the internal curly braces (I have enclosed - in the concat parameter to do this).

Answer 6

Another iterative algorithm:

 function flatten2(input) { var output = []; var todo = [input]; var current; var head; while(todo.length) { var current = todo.shift(); if(Array.isArray(current)) { current = current.slice(); head = current.shift(); if(current.length) { todo.unshift(current) } todo.unshift(head); } else { output.push(current); } } return output; } 

• Put all the items on the stack.
• While the stack is not empty, delete the first item.
  • If this item is a scalar, add it to the output.
  • If this element is an array, split it into the head (first element) and tail (other elements) and add both to the stack.

As Tomalak JSPerf shows, it's pretty slow.

Jsbin

Answer 7

Pretty concise, readable algorithm:

 function flatten(input) { var output = []; var todo = [input]; var current; while(todo.length) { var current = todo.shift(); if(Array.isArray(current)) { todo.unshift.apply(todo, current) } else { output.push(current); } } return output; } 

This version works better than my other answer , but is still significantly slower than James Wilkins answer .

Jsbin

Tomalak JSPerf