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!

• Joe Enos: Why don't you want to use recursion?
• Kosmetika: @JoeEnos it's more about educate myself and curiosity.
• juvian: With only arrays its easy, but including objects not sure
• Kosmetika: @juvian how easy it is? using [].concat.apply([], arr); won't do the trick for multiple nestings :/
• juvian: var a = [1, 4, [5, [6]], [[[5],[6],[[7]]], 8, 9], 10];console.log(a.toString().split(','))

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

• Jorge Orpinel Pérez: What is the , first for?
• Jorge Orpinel Pérez: 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

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

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

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]

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

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 7

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 8

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 9

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 10

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 11

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 

• Saeed Zhiany: 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.
• Michael Aigbovbiosa: 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.
• Saeed Zhiany: 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
• Michael Aigbovbiosa: 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.

Answer 12

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

• moken: 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.