Iterative solution for flattening n-th nested arrays in Javascript

Question

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 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 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

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

Works, but not recommended:

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

Answer 4

Here's a solution that flattens 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, flattening each element one level of nesting at a time until it cannot be flattened any more.

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 in-place solution is faster than Lupe's, now that I've removed all of the inner curly brackets (I inlined the i-- in the concat parameter to do that).

Answer 6

A different 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 elements on a stack.
• While the stack is not empty, remove the first element.
  • If that element is a scalar, add it to the output.
  • If that element is an array, split it into head (first element) and tail (remaining elements) and add both to the stack.

As Tomalak's JSPerf shows, this is pretty slow.

JSBin

Answer 7

A fairly 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 performs better than my other answer, but is still significantly slower than James Wilkins' answer.

JSBin

Tomalak's JSPerf

Answer 8

Here are two approaches, recursive and iterative and their comparison to Array.flat. Maybe it'll help someone

const arrayToFlatten = [[1], [2, [3]], null, [[{}]], undefined];

// takes an array and flattens it recursively, default depth is 1 (just like Array.flat())
function flattenRecursive(arr, depth = 1) {
  let myArray = [];

  if (depth === 0){ // if you've reached the depth don't continue
    myArray = arr;
  } else if(!Array.isArray(arr)) { // add item to array if not an array
    myArray.push(arr);
  } else { // flatten each item in the array then concatenate
    arr.forEach(item => {
      const someNewArray = flattenRecursive(item, depth - 1);
      myArray = myArray.concat(someNewArray);
    });
  }
  
  return myArray;
}

// takes an array and flattens it using a loop, default depth is 1 (just like Array.flat())
function flattenIterative(arr, depth = 1) {
  let result = arr;

  // if an element is an array
  while(result.some(Array.isArray) && depth) {
    // flatten the array by one level by concating an empty array and result using apply
    result = [].concat.apply([], result);
    depth--; // track depth
  }

  return result;
}

console.log(arrayToFlatten.flat(2)); // ES^
console.log(flattenRecursive(arrayToFlatten, 2));
console.log(flattenIterative(arrayToFlatten, 2));

Answer 9

Here's my solution to this:

function flattenList(A) {
  let result = []
  for (let i=0; i < A.length; i++) {
    if (typeof A[i] == "object"){
      let item = reduceArray(A[i])
      result.push(...item)
    }else {
      result.push(A[i])
    }
  }
  return result
}

function reduceArray(arr){
  while(arr.some(Array.isArray)) {
    let item = arr.find(Array.isArray)
    let index = arr.indexOf(item)
    arr[index] = item[0]
  }
  return arr
}

Answer 10

Not sure if the "stack" approach was used properly in previous answers. I think it could be simpler, like this:

function flatten(arr) {

  const result = [];
  const stack = [arr];

  while (stack.length) {
    const curr = stack.pop();
    if (Array.isArray(curr)) {
      for (let i = curr.length - 1; i >= 0; i--) {
        stack.push(curr[i]);
      }
    } else {
      result.push(curr);
    }
  }

  return result;
}

Answer 11

Not sure why the other answers are so complicated, this can easily be achieved by looping through the array and flattening each entry until it's no longer an array.

const flatten = (arr) => {
  for (let i = 0; i < arr.length; i++) {
    while (Array.isArray(arr[i])) {
      arr.splice(i, 1, ...arr[i]);
    }
  }
  return arr;
}