Flatten array of multiple nested arrays without recursion - javascript

Question

Maybe it's stupid question but I cannot realize is that possible to flatten multidimensional array without recursion?

I have one solution written by me with recursion:

function transform (arr) {
   var result = [];
   arr.forEach(flatten)
   function flatten (el) {
     if (Array.isArray(el)) {
        return el.forEach(flatten);
     }
     return result.push(el);
   }
   return result;
}

Example of an array to flatten:

[1, {a: [2, 3]}, 4, [5, [6]], [[7], 8, 9], 10]

And execution:

var a = [1, {a: [2, 3]}, 4, [5, [6]], [[7], 8, 9], 10];
var r = transform(r);
console.log(r); // [1, {a: [2, 3]}, 4, 5, 6, 7, 8, 9, 10]

Thanks!

Tubule

Why don't you want to use recursion? – Workbook

@JoeEnos it's more about educate myself and curiosity. – Tubule

With only arrays its easy, but including objects not sure – Ellen

@Ellen how easy it is? using [].concat.apply([], arr); won't do the trick for multiple nestings :/ – Tubule

var a = [1, 4, [5, [6]], [[[5],[6],[[7]]], 8, 9], 10];console.log(a.toString().split(',')) – Ellen

@Ellen nice try, but you lose original data types to strings – Tubule

Yeah, its just for some cases, at least with only numbers you can reconvert them to numbers after flatten, but not for objects or other data types – Ellen

Answer 1

You can use a stack. When you discover a nested array, just replace it with its items.

function flatten(arr) {
  var result = [];
  var stack = arr, first;

  while (stack.length > 0) {
    first = stack[0];

    if (Array.isArray(first)) {
      // Replace the nested array with its items
      Array.prototype.splice.apply(stack, [0, 1].concat(first));
    } else {
      result.push(first);
      // Delete the first item
      stack.splice(0, 1);
    }
  }

  return result;
}

Alleged

What is the , first for? – Drunken

May I suggest you only need this one line inside the else clause: result.push(stack.splice(0, 1)[0]) to delete the first item from the stack AND push it to the result array. Cheers – Drunken

Answer 2

I've got exact same question on the interview and came up with this solution:

function flattenNonRecursion(arr) {
  const res = arr.slice();
  let i = 0;

  while (i < res.length) {
    if (Array.isArray(res[i])) {
      res.splice(i, 1, ...res[i]);
    }
    else {
      i++;
    }
  }

  return res;
}

console.log(flattenNonRecursion([1, {a: [2, 3]}, 4, [5, [6]], [[7], 8, 9], 10]));
// [1, {a: [2, 3]}, 4, 5, 6, 7, 8, 9, 10]

So, the main idea is that we are moving forward through our array and if we meet an array we replace it with it's content and keep moving forward... Complexity of this solution is O(n).

Bootstrap

Answer 3

Here O(N) solution, where N is the number of items in the flatten array, without mutating the input array.

Seems more natural to me to use pop and push when we use stack. This solution doesn't use very expensive splice, unshift, shift and other in-place array mutating methods.

Using ES6 spread operator, not a must though, can be replaced with apply.

function flat(input) {
  const stack = [...input];
  const res = [];
  while (stack.length) {
    // pop value from stack
    const next = stack.pop();
    if (Array.isArray(next)) {
      // push back array items, won't modify the original input
      stack.push(...next);
    } else {
      res.push(next);
    }
  }
  return res.reverse();
}

Tevet

Answer 4

You have to manage the state through other means.

Here I do it with an array. It lets us keep track of where we are in the overall scheme of what we're doing. I feel like I've done this rather unattractively, but the job is done.

function transform(arr){
    var state = [];
    var i = 0,
        a = arr;
    var result = [];
    while(true){
        var val = a[i];
        if(Array.isArray(val)){
            state.push({i: i, a: a});
            a = val;
            i = -1;
        } else if (val !== undefined) {
            result.push(val)   
        }
        if(i++ >= a.length - 1){
            if(state.length > 0)
            {
                var s = state.pop();
                a = s.a;
                i = s.i + 1;
            } else {
                break;   
            }
        }
    }
    return result;
}

var a = [1, {a: [2, 3]}, 4, [5, [6]], [[7], 8, 9], 10];
console.log(a); // Chrome Outputs: [1, Object, 4, Array[2], Array[3], 10]
var r = transform(a);
console.log(r); // Chrome Outputs: [1, Object, 4, 5, 6, 7, 8, 9, 10]

Aleishaalejandra

Answer 5

function flat(arr) {

  for (let i= 0; i<arr.length; i++) {
    const element = arr[i];
    if (Array.isArray(element)) {
      arr.splice(i, 1, ...element); // replaces arr[i] with its elements
    }
  }

  return arr;
}

This is non-recursive + in-place array modification (no new array is created)

Aftergrowth

Answer 6

This is a proposal which uses two arrays for flatten another array.

Basically one array keeps the count from a certain level, the other one keeps the reference to the array with the level.

The main advantage over the other two solutions is the single use of Array#push and no other mutating methods of Array.

function transform(array) {
    var result = [],
        level = 0,
        reference = [array],
        counter = [0];

    while (level >= 0) {
        if (counter[level] >= reference[level].length) {
            level--;
            continue;
        }
        if (Array.isArray(reference[level][counter[level]])) {
            reference[level + 1] = reference[level][counter[level]]
            counter[level]++;
            level++;
            counter[level] = 0;
            continue;
        }
        result.push(reference[level][counter[level]]);
        counter[level]++;
    }
    return result;
}

var a = [1, { a: [2, 3] }, 4, [5, [6]], [[7], 8, 9], 10],
    r = transform(a);

console.log(r);

Selfabnegation

Answer 7

I've simplified @Misha's solution a little:

function flatten(array) {
  var result = []; 
  var stack = array
  var item;

  while (stack.length) {
    item = stack.shift();
    if (Array.isArray(item)) [].unshift.apply(stack, item);
    else result.push(item);
  }

  return result;
}

Biz

Answer 8

We can use JS Array flat() method for this, which is currently supported in most of the browsers except IE, as of May 2019.

Syntax

var newArray = arr.flat([depth]);

depth: Optional

The depth level specifying how deep a nested array structure should be flattened. Defaults to 1.

---

Flattening nested arrays

One Level Depth:

const arr1 = [1, 2, [3, 4]]
const flattenArr = arr1.flat()
console.log(flattenArr)
// [1, 2, 3, 4]

---

Two Level Depth:

const arr2 = [1, 2, [3, 4, [5, 6]]];
const flattenArr = arr2.flat(2)   // <== using 2 here
console.log(flattenArr)
// [1, 2, 3, 4, [5, 6]]

Any Level Deep:

const arr3 = [1, {a: [2, 3]}, 4, [5, [6]], [[7], 8, 9], 10]

// Using `Infinity` here to flatten any depth level array
// For this use case we could have also used 3 here
const flattenArr = arr3.flat(Infinity)
console.log(flattenArr)
// [1, {a: [2, 3]}, 4, 5, 6, 7, 8, 9, 10]

.as-console-wrapper { max-height: 100%!important; }

Gaitan

Answer 9

const flatten = (array) => {
  const flattenedArray = []; // an empty array that all flattened elements will be in
  while(array.length) { // while there are still elements in the array
    const ele = array.shift(); // remove the first element 
    if(!Array.isArray(ele)) { // check if this element is not an array
        flattenedArray.push(ele); // since it's not, just push it into the flattened array
        continue; // continue to do this to all non arrays and ignore the rest of the code until...
      };
      array = [...ele,...array]; // you've found an array in your given array, now you get all the elements of the array you just found, with the rest operator, put them all into a new array, with the remaining elements of the main array at it's back with also the rest operator, make it equal to the original array
  };
  return flattenedArray; // return the flattened array
};
// This is less problematic and straight forward, because all the elements previously removed that are not arrays continue to leave the main array into the flattened array 

Procrustean

Please read How do I write a good answer?. While this code block may answer the OP's question, this answer would be much more useful if you explain how this code is different from the code in the question, what you've changed, why you've changed it and why that solves the problem without introducing others. – Zoan

Thanks Saeed, I'm relatively new to posting answers, didn't feel like adding too much explanations too, would make sure I do that next time. Thanks. – Procrustean

Thanks for your effort. I didn't mean to explain the code line by line using commenting. you can explain the idea behind your solution and what is wrong with the OP's code that leads to their problem. you can explore StackOverflow and see many examples of good answers to learn more about writing complete and useful answers. good luck – Zoan

I understand your point, the OP's code doesn't really have a problem I can see except that the OP wants to use a non-recursive approach which my code also solves, there's really nothing much again to do with what I already did, thanks Saeed. – Procrustean

Answer 10

const ar =[1,2,[3,[4,5,[6,7,[8,9]]]]]
 function singleArray(ar) {
 return ar.reduce((ac, cur) =>{
   if(Array.isArray(cur)){
     return [...ac, ...singleArray(cur)]
   }
   return [...ac, cur];
 },[])
}
console.log(singleArray(ar)) 

Leitmotif

Answer needs supporting information Your answer could be improved with additional supporting information. Please edit to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers in the help center. – Pentecost

Answer 11

const getFalttenArrayWithInArrayModification = (arr) => {
    for (let i = 0; i < arr.length; i++) {
      if (Array.isArray(arr[i])) {
        arr.splice(i, 1, ...arr[i]);
        if (Array.isArray(arr[i])) 
          i--;
      }
    }
    return arr;
}
const input = [[[[2,5],6], [4,5]], 5, [[4,5], 3, [9,8]]];
console.log(getFalttenArrayWithInArrayModification(input));

The answer is with little modification to Skay answer as that was not handling the use cases where first replaced element is array.

Necktie

Answer 12

function flat(arr) {
    for (let i= 0; i < arr.length; i++) {
      const element = arr[i];
      if (Array.isArray(element)) {
        arr.splice(i, 1, ...element); // Replaces arr[i] with its elements
        i--; // This is needed because the next iteration has to start from i and not i + 1 because of the change in array elements
      }
    } 
    return arr;
}

Metsky