CODEWITHSUNDEEP
javascriptrecursion
nguyenngoc101
nguyenngoc101

Reputation: 1211

flatten an array recursively

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.

Upvotes: 3

Views: 2144

Answers (7)

kjaer
kjaer

Reputation: 358

I am influenced by the Nina Scholz' answer (https://stackoverflow.com/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));

Upvotes: 2

kjaer
kjaer

Reputation: 358

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 compare to shift for remove the first element from given array, or spread operator for merging arrays or combining it with destruction to simulate shift method.

I also used push method for merging arrays (credit to this post: https://forum.freecodecamp.org/t/big-o-complexity-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 completed, so it won't increase the complexity.

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

Upvotes: 0

Sector88
Sector88

Reputation: 21

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]]]));

Upvotes: 2

rab
rab

Reputation: 4144

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

Upvotes: 0

Ronen Cypis
Ronen Cypis

Reputation: 21470

The concat() method returns a new array comprised 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.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<div id="result"></div>

You can read more about Array.concat function here

Upvotes: 6

Nina Scholz
Nina Scholz

Reputation: 386883

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>');

Upvotes: 3

Rajaprabhu Aravindasamy
Rajaprabhu Aravindasamy

Reputation: 67217

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.

Upvotes: 4

Related Questions