Iterative solution for flattening n-th nested arrays in Javascript

Can anyone show me an iterative solution for the following problem? I solved it recursively but struggled with an iterative solution. (Facebook Technical Interview Question)

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

Solution must work with n-th nested array elements (i.e. it must still work if someone modifies the array values/placement in the example above)

Recursive solution:

var flatten = function(input) {
    var result = [];

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

    return result;
}

Answer

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 iterating over a nested structure, you just have to remember where you were before by saving the current array and position before moving into the nested array (this is usually taken care of via the stack for recursive solutions).

Note: If you reuse the arrays placeHolder and lastIndex you won’t need to keep recreating them every time. Perhaps 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 again (for flat iteration that is), and less garbage collector issues calling it many times. The speed is very close to that of recursive function calling in Chrome, and many times faster than recursion in FireFox and IE.

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