How to flatten a deep nested Array in JS #DailyAlgorithm

Amazon AD Banner

There comes the time when we need to explore nested entities such as directories, object literals, arrays or lists within lists that far exceed one or two levels deep. Recursion solves this problem by applying the same declared procedure to every array that is inside an array and so on. We can picture the process in our heads if I set a little example.

Imagine that one of your relatives (who happens to be traveling far away) sends you a package over the mail and when you open it, it contains plenty of boxes that also contain boxes and some other contents inside; in summary, boxes inside boxes inside boxes (oh my!). You have a place where you want to store all this stuff and get rid of the boxes first will be a hard task but, you already know how to extract contents from a box, don't you? The process would go like this:

  1. You open the main big box your relative sent you.
  2. Start picking each item in no particular order (in JavaScript, the order in which you'll be accessing items in the Array is from left to right).
  3. If the item happens to be a box, you backtrack to step 1 (open the box, then pick each item and do step 3). If it's not a box, put it in the container where you're going to store all the stuff you got from your relative.

As you see, you're doing the process of opening and extracting contents when the item you pick happens to be a box itself over and over again, spending time evaluating deep levels of nesting and in the end, after all of the items have been evaluated and processed, you got yourself a nice container with all the extracted items! No more damned boxes!


Credit of the image goes to PrettyUnexpected

Translating it to code

I'm going to use the JavaScript language and a recursive call to a functional Array iterative method called reduce which will make our task more pleasant. It's not tail-call optimized but if your array doesn't have many levels of deep nesting, your call stack will be safe enough.

We first need to declare a nested array to do some testing, here's a simple example that you can use:

var nested = [3,[1,'hey',[2, 'you',[2,5]]],1,[9,[{},[2,true]]]];  

The maximum level of deepness in that array is about 4, which means that to access the innermost elements in the nested array, you must do it this way: nested[1][2][2][0] or nested[1][2][2][1] since both the 2 and the 5 are inside the same sub-array and there's also [2,true] on the left side of the array with the same level. Now, to create the recursive function, try to remember what we talked about in the first paragraphs, how we had a certain procedure and repeated it if the item that's being evaluated in the reduce method is an array until there are no more arrays left.

function flatten(arr) {  
  return arr.reduce(function(explored, toExplore) {
    return explored.concat(
      flatten(toExplore) : toExplore
  }, []);

IMPORTANT: Before you take this solution as valid, please see its flaws first, it's not optimized and sacrifices elegance for efficiency and memory usage. You may want to check out the other solutions that are also perfectly valid.

The first step is creating a function that takes an array (a nested one) as its only parameter. Next, we return a reduced array parting from the one that was passed to the function and we're taking two parameters, the items that were already explored (evaluated to see if they're arrays or single elements) and stripped off any container they were in (with the recursive calls), and the item that's currently being evaluated.

The magic comes in the second call to the flatten function (the same function that we declared), it makes sense because in the early explanation, we decided that you already know how to detect, explore and extract the contents of a box so you don't need to declare another procedure for that, you have already declared it and calling it inside itself allows us to take advantage of recursion.

The reduce algorithm is going to set an initial value for the explored variable in order to keep concatenating the evaluated items into the previous concatenated array, starting from an empty one. The subsequent values of explored will be the outcome of the function as it keeps collecting the extracted values and the subsequent values of the toExplore variable will be each item inside the array (from left to right). If the item "to explore" happens to be a variable (hence the call to Array.isArray(toExplore), then we call the function inside itself to keep repeating the process, accessing the deeply nested levels of the array by using the call stack; if it's not then we just concatenate the value with the result array and move on to the next item; at the end, all of the StackTrace will substitute back to a single value and we'll end up with the flattened array.

Exploring the recursive call

In here I'll just illustrate what happened when we execute the function passing the nested array and how we obtain the flattened array as a result.

var flattened = flatten(arr);  

// => "[ 3, 1, 'hey', 2, 'you', 2, 5, 1, 9, {}, 2, true ]"
1. flatten() receives arr.  
2. We start by returning a reduced array.  
2.1. Accumulating [].concat(3)  
  -> [3] because 3 is not an array.
2.2. Accumulating [3].concat(evaluating...)  
  (!) [1, 'hey', [2, 'you', [2, 5]]] is an array so...
    2.2.1. Accumulating [].concat(1)
      -> [1] because 1 is not an array
    2.2.2. Accumulating [1].concat('hey')
      -> [1, 'hey'] because 'hey' is not an array
    2.2.3. Accumulating [1, 'hey'].concat(evaluating...)
      (!) [2, 'you',[2,5]] is an array so... Accumulating [].concat(2)
          -> [2] because 2 is not an array Accumulating [2].concat('you')
          -> [2, 'you'] because 'you' is not an array Accumulating [2, 'you'].concat(evaluating...)
          (!) [2,5] is an array so...
   Accumulating [].concat(2)
              -> [2] because 2 is not an array
   Accumulating [2].concat(5)
              -> [2, 5] because 5 is not an array
          -> [2, 'you'].concat([2, 5]) becomes...
          => [2, 'you', 2, 5]
      -> [1, 'hey'].concat([2, 'you', 2, 5]) becomes...
      => [1, 'hey', 2, 'you', 2, 5]
  -> [3].concat([1, 'hey', 2, 'you', 2, 5]) becomes...
  => [3, 1, 'hey', 2, 'you', 2, 5]
2.3. Acc [3, 1, 'hey', 2, 'you', 2, 5].concat(1)  
  -> [3, 1, 'hey', 2, 'you', 2, 5, 1] because 1 is no array
2.4. Acc [3, 1, 'hey', 2, 'you', 2, 5, 1].concat(eval...)  
  (!) [9, [{}, [2, true]]] is an array so...
    2.4.1. Accumulating [].concat(9)
      -> [9] because 9 is not an array
    2.4.2. Accumulating [9].concat(evaluating...)
      (!) [{}, [2, true]] is an array so... Accumulating [].concat({})
          -> [{}] because {} is not an array Accumulating [{}].concat(evaluating...)
          (!) [2, true] is an array so...
   Accumulating [].concat(2)
              -> [2] because 2 is not an array
   Accumulating [2].concat(true)
              -> [2, true] because true is not an array
          -> [{}].concat([2, true]) becomes...
          => [{}, 2, true]
      -> [9].concat([{}, 2, true]) becomes...
      => [9, {}, 2, true]
  -> [3, 1, 'hey', 2, 'you', 2, 5, 1]
     .concat([9, {}, 2, true]) becomes...
  => [3, 1, 'hey', 2, 'you', 2, 5, 1, 9, {}, 2, true ]
2.5. The above is the final result, return it!  

As you see, the deep levels keep going back and being substituted by their concatenated versions until everything is concatenated and flattened in the end. You can use the same algorithm with a few tweaks to deep explore an object literal, you'd need to use methods like Object.hasOwnProperty(), (a loop for object literals) and typeof element === 'object' with an extension to check for arrays if you consider arrays as values.

Other solutions

As I mentioned in the side note below the code, the solution above is a bit memory-expensive because it creates extra arrays and the innermost call is completely unnecessary; what we could do is explore more options and see the one that suits you best. First I want to introduce you to the tail-call optimized recursive call in ECMAScript 6 (ES2015, ES6) that was suggested to me by a user on Reddit called iSmokeGauloises:

const scalar = v => !Array.isArray(v);

const flatten = (deep, flat = []) => {  
  if (deep.length === 0) return flat;
  let [head, ...tail] = deep;
  if (scalar(head)) {
    return flatten(tail, flat.concat(head));
  } else {
    return flatten(tail, flat.concat(flatten(head)));

He first creates a function that determines whether the item passed to it can be concatenated to the result array or if it needs to be flattened because it's an array (this is an arrow function).

Next, another function that is tail-call optimized (takes an accumulator and will only work on modern browsers and recent versions of NodeJS) and takes in a parameter which is the array to flatten, while the second parameter is optional and has a default value, acting as the accumulator for later calls.

The first line is the condition to break the recursive call and it happens once there's a single item passed (because of the spread operator) to the flat variable. The 2nd line in the function is important because it declares two variables, the first variable (deep) holds the current item and the tail variable holds the remaining items in the array that's being passed through calls.

The JSON parser

This solution shouldn't even be taken seriously but I came up with it and I think it's a neat trick that I don't think it would work if one of the values inside the nested array is a string with square brackets.

  '[' +
      .replace(/[|]/g, '') +

Don't mind the extra whitespace I added, it was just because of mobile users. The first step is to convert the array to string using JSON.strinfigy and then replace (using a regular expression) every square bracket inside with nothing (empty string), after that, wrap the resulting string with opening and closing square brackets to finally parse it with JSON.parse which will convert the string back to a now flattened array. PLEASE DON'T TRY THIS AT HOME.

A trick using [].splice()

This was suggested by another user on Reddit called oorza, what he suggests is a non-recursive solution, working with a copy of the nested array.

// Create a copy of the array
var flat = [].concat(nested);

for(var i = 0; i < flat.length; i++) {  
  if(Array.isArray(flat[i])) {
    // Replace with the items and backtrack 1 position
    flat.splice(i, 1, ...flat[i--]);  

If you wish not to modify the original array, you can use the copy = [].concat(copied) trick to create a copy of the original array and then iterate over it with a classic for loop, if the current item is an array, remove that sub-array (with Array.splice) from the index (the first two parameters) and then fill the gaps with the items that were inside it but separated by commas using the ES6 spread operator. Notice the i-- expression, it doesn't mean that it will access the previous item, no, it means it will access the current item and after that, it's going to decrement the value of i by one; that's why pre-increment and post-increment are important to differentiate. It's decrementing the index because we're backtracking one position to check if the sub-array didn't contain any other sub-arrays, doing this until there's no more sub-arrays so it can move on with the left to right iteration.

Using a library like _.lodash

It's actually called just Lodash, the other one is UnderscoreJS and I'm pretty sure you've heard of them before. These libraries have a _.flatten (just for one level of depth) method but not only that, they also have _.flattenDeep (recursive) and _.flattenDepth.

These comments are powered by Disqus