5

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!

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

11 Answers 11

5

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;
}
2
  • What is the , first for? Jan 22, 2019 at 8:00
  • 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 Jan 22, 2019 at 8:21
5

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

0
5

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

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

  return arr;
}

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

0

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

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

0

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

0
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 
4
  • 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. Jul 25, 2022 at 3:41
  • 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. Jul 25, 2022 at 7:25
  • 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 Jul 25, 2022 at 8:14
  • 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. Jul 25, 2022 at 11:36
0
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)) 
1
  • 1
    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.
    – moken
    Jul 25, 2023 at 12:26
0
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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.