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!

Answer 1

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

Answer 2

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.

Answer 3

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

Answer 4

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 

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)

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

Answer 7

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

Answer 8

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

Answer 9

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

Answer 10

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

Answer 11

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

Answer 12

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]