Flatten an array of multiple nested arrays without recursion - javascript
Perhaps this is a stupid question, but I cannot figure out that it is possible to flatten a 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;
}
An example of an anti-aliasing array:
[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]
Thank!
source to share
You can use a stack. When you find a nested array, just replace it with elements.
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;
}
source to share
You need to run the state in other ways.
Here I am doing it with an array. This allows us to keep track of where we are in the overall pattern of what we are doing. I feel like I did it rather unsightly, 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]
source to share
This is a proposal that uses two arrays to align another array.
Basically one array stores the score from a certain level, the other stores a reference to the array with the level.
The main advantage over the other two solutions is the one-time use of Array # push and other array-distortion methods.
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);
source to share
I have the same question in an 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 basic idea is that we are moving forward through our array, and if we come across an array, we replace it with its contents and keep moving forward ... The complexity of this solution is O (n).
source to share