I tried to implement an array flatten function recursively. Here is the code:

function flatten(arr) {
  var flatArr = [];
  for (var i = 0; i < arr.length; i++) {
    if (arr[i] instanceof Array) {
      flatArr.concat(flatten(arr[i]));
    } else {
      flatArr.push(arr[i]);
    }
  }
  return flatArr;
}


console.log(flatten([1, 2, 3, 4, [5]]));
/*
result: [1, 2, 3, 4]
expected: [1, 2, 3, 4, 5]
*/

But I don't know why the result is not correct. Please help me explain it.

I tried to implement an array flatten function recursively. Here is the code:

function flatten(arr) {
  var flatArr = [];
  for (var i = 0; i < arr.length; i++) {
    if (arr[i] instanceof Array) {
      flatArr.concat(flatten(arr[i]));
    } else {
      flatArr.push(arr[i]);
    }
  }
  return flatArr;
}


console.log(flatten([1, 2, 3, 4, [5]]));
/*
result: [1, 2, 3, 4]
expected: [1, 2, 3, 4, 5]
*/

But I don't know why the result is not correct. Please help me explain it.

• javascript
• recursion

• The problem is that you didn't assign the returned array from .concat to your flatArr var. see a working example inside my answer. – Ronen Cypis Commented Feb 28, 2016 at 10:03

7 Answers 7

The concat() method returns a new array prised of the array on which it is called joined with the array(s) and/or value(s) provided as arguments.

flatArr.concat(...) doesn't change flatArr... you need to assign it like so:

flatArr = flatArr.concat('flatten(arr[i]));

Here is a working example with 3 levels deep array:

function flatten(arr) {
  var flatArr = [];
  for (var i = 0; i < arr.length; i++) {
    if (arr[i] instanceof Array) {
      flatArr = flatArr.concat(flatten(arr[i]));
    } else {
      flatArr.push(arr[i]);
    }
  }
  return flatArr;
}

var arr = [1,2,3,4,[5,6,[7,8]]];
var flatten = flatten(arr);

$('#result').html(JSON.stringify(flatten));

<script src="https://ajax.googleapis./ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<div id="result"></div>

You can read more about Array.concat function here

You have to assign the returned array after performing the concat,

 if (arr[i] instanceof Array) {
      flatArr = flatArr.concat(flatten(arr[i]));

concat will not edit the source array. It will give you a new copy. So we have to assign it back to the source array manually.

Maybe you like a real recursive solution:

function flatten(arr) {
    if (!arr.length) {
        return [];
    }
    var a = arr.shift();
    return (Array.isArray(a) ? flatten(a) : [a]).concat(flatten(arr));
}

document.write('<pre>' + JSON.stringify(flatten([1, 2, 3, 4, [5]])) + '</pre>');
document.write('<pre>' + JSON.stringify(flatten([1, [2, 3, [4, 5]], 6, 7, [8]])) + '</pre>');

This worked for me, hope it helps! :)

function flatten(array) {
    let result = [];
    array.forEach(el => {
       if(el instanceof Array){
          result.push(...flatten(el));
        }else result.push(el)
     });
     return result
}
console.log(flatten([1, [2, 3, [4]]]));

I am influenced by the Nina Scholz' answer (https://stackoverflow./a/35681232/5018572) above and made a tail call safe recursive flat array function which avoid using any iteration in it:

'use strict'

function flatten(arr, flatArr = []) {
  if (arr.length === 0) {
    return flatArr;
  }

  var [head, ...rest] = arr;

  if (Array.isArray(head)) {
    head.push(...rest);
    
    return flatten(head, flatArr);
  } else {
    flatArr.push(head);
  }

  return flatten(rest, flatArr);
}

var test = [1,2,[3,4,[5,[[[6,[[[7]]]]]]]]]
console.log(flatten(test));

Loop array until all items get flatten, It's a different solution, not exactly what asked in the question.

// loop until all items are flatten
for (var i = 0, len = data.length; i < len; i++) {
    if (Array.isArray(data[i])) {
        // flatten until there are no more nested
        data = data.concat.apply([], data);
        i--;
        len = data.length;
    }
}

I worked on another (possibly better performant) answer.

I used push, and pop for modifying the arrays (given and final arrays) because they're more performant array operations pare to shift for remove the first element from given array, or spread operator for merging arrays or bining it with destruction to simulate shift method.

I also used push method for merging arrays (credit to this post: https://forum.freecodecamp/t/big-o-plexity-of-concat-vs-push-apply-inside-loops/33513).

There's a catch though: result array is reversed. push and pop adds/removes last item therefore I created the final array in reversed order. For this reason I called .reverse at the end.

reverse is executed after all flattening operations are pleted, so it won't increase the plexity.

Here is the solution:

function flatten(arr, flatArr = []) {
  if (arr.length === 0){
      return flatArr.reverse();
  }
  
  var lastItem = arr.pop();

  if(Array.isArray(lastItem)){
    Array.prototype.push.apply(arr, lastItem);  
    return flatten(arr, flatArr);
  } else {
      flatArr.push(lastItem);
  }
  
  return flatten(arr, flatArr)
}

var array1 = [1,2,[3,4,[5,[[[6,[[[7, [8, 9, [10, [11,[12, [13, [[[[14,[15, [[16,[17]]]]]]]]]]]]]]]]]]]]]];
var array2 = [[[[[[[[[[[[[[[[[[[[[[[[[1],2,3]]]],4],5]]]],6],7],8],9]],10],11],12],13],14],15],16]]],17];


console.log(flatten(array1));
console.log(flatten(array2));