JavaScript Flatten Array Algorithm

Breaking Down The Steamroller Algorithm Problem From FreeCodeCamp.org

8 min readApr 1, 2020

Goal

We’re going to examine the problem of trying to flattening arrays in JavaScript or the act of making a multidimensional array into a single dimensional array:

[1, [2], [3, [4]]] -> [1, 2, 3, 4]

Real World Use

In most cases I see this as a formatting issue or you need to get the data transformed into another form to easily access certain attributes. While GraphQL from a database could solve this, if we’re dealing with a REST API or we have a ton of data that we need to get through and format a specific way, we might need to flatten the data.

Couldn’t You Just Use Array.Flat()?

You could technically use the new ES2019 functionality called Array.flat which takes an array and just flattens it by making all sub arrays (or multidimensional array) into a single array.

// ES2019
const arr = [1, [2], [3, 4]];arr.flat();// Result
[1, 2, 3, 4]

There are however a few limitations to this.

Not Supported On All Browsers

Currently works for most major browsers but does not work for IE11.

Can I use... Support tables for HTML5, CSS3, etc

"Can I use" provides up-to-date browser support tables for support of front-end web technologies on desktop and mobile…

caniuse.com

Deeply Nested Arrays You Need To Specify Depth

While the first result from our example above shows how easy it was to flatten an array, if we took the same scenario with a deeper Array we would get a different result:

// ES2019
const arr = [1, [2], [[[3]], [4]]];arr.flat();// Result
[1, 2, Array(1), Array(1)]

You could solve this by specifying the depth:

// ES2019
const arr = [1, [2], [[[3]], [4]]];arr.flat(2);// Result
[1, 2, Array(1), 4]arr.flat(3);
[1, 2, 3, 4]

But what if you don’t know how deep the Array is or you can’t bother with the idea of counting how deep it is?

The Problem

Following the excerpt from FreeCodeCamp.org:

“Flatten a nested array. You must account for varying levels of nesting.”

freeCodeCamp.org

Learn to code. Build projects. Earn certifications.Since 2015, 40,000 graduates have gotten jobs at tech companies…

www.freecodecamp.org

What This Means

1 — We don’t know how deep the nested Array goes

2 — We only know that if it’s not an Array then we need to keep digging / iterating

3 — We need to present the data as a flat array as a output

Iterations + Unknown Depth

When iterations is involved the first though it to use either a for loop or while loop. Through process of elimination, let’s examine each.

For Loop

If we decided to go with a for loop we would need to know the length of the array and then known any nested array’s length, and so on. In other words, for loop is not an option.

// const arr = [...unknown]
for (let i = 0; i < arr.length; i++) {
  if (arr[i] instanceof Array) {
    for (let y = 0; y < arr[i].length; y++) {
       if (arr[i][y] instanceof Array) {
         for (let z = 0; arr[i][y].length; z++) {
            ...keeps going

While Loop

When we don’t know the length of an array then could also use a while loop until we figure out a condition where it’s iterated of each element and perhaps the condition we could set is that it finishes once it reaches the last element, but the issue is that we need need to figure out a way to iterate without writing the same code over and over again. In this case, while loop is not an option.

// const arr = [...unknown]let index = 0;
let newArr = [];
let tempArr = [];
let tempIndex = 0;  
while (index < arr.length) {
   if (arr[index] instanceOf Array) {
       tempIndex = 0;
       tempArr = arr[index]; 
       if (!tempArr[tempIndex] instanceOf Array) {
          newArr.push(tempArr[tempIndex]);
          ... 
   }
}

Direction: Recursive Functions

Knowing these two scenarios, the best option would be a recursive function that keeps calling itself until it gets through all values of the nested array. That way we’re not writing more code, but just utilizing the same code over and over again until we get the base units that we want.

// const arr = [...unknown];const Steamroller = (arr) => {
    // If still an array
    return Streamroller(modifiedArr);
 
    // If not an array return the result 
    return arrValue; 
}

Solution In Steps

Breaking down the pseudo code we want to achieve:

1 — If the current index we’re on is still an array then continue to break it down to a single value

2 — If the current index is a single value and not a nested array then return the value

3 — We need to keep track of the values and send a new Array and make sure we’re returning this Array

If Still An Array

The first thing we want to identify is if the value we are getting is an Array to be able to continue to break it down. There could be even a case where we get const arr = 7; but we still need to return [7];

// const arr = [...unknown];const Steamroller = (arr) => {
   // 1. If still an array
   if (arr instanceof Array) {
 
      // 1A Still an array but we need to iterate over it
      // Steamroller(arr); would be an infinite loop
      // Let remove the first value and pass the rest
      Steamroller(arr.slice(1)); 
   }
};

Now if we run just this would get a Maximum call stack size exceeded.

That’s because if we just took the example of a simple array input of [1] and we did an arr.slice(1) on it, it would return [] which is still an instance of an Array and continues to loop endlessly.

So we need to account for an empty array.

// const arr = [...unknown];
const Steamroller = (arr) => {
   // 1. If still an array
   if (arr instanceof Array) {
 
      // 1A Still an array but we need to iterate over it
      // Steamroller(arr); would be an infinite loop
      // Let remove the first value and pass the rest
      // 1B AND has a length greater than 0
      if (arr.length > 0) { 
          Steamroller(arr.slice(1));
      } 
   }
};

Now when we run the following we don’t get an error message:

Streamroller([1]);

But we also don’t get anything at all.

// Result
undefined

If A Value (Not An Array)

That’s because we still need to return the value.

// const arr = [...unknown];
const Steamroller = (arr) => {
   // 1. If still an array
   if (arr instanceof Array) {
 
      // 1A Still an array but we need to iterate over it
      // Steamroller(arr); would be an infinite loop
      // Let remove the first value and pass the rest
      // 1B AND has a length greater than 0
      if (arr.length > 0) { 
          Steamroller(arr.slice(1));
      } 
   }
   // 2. If not an array
   return arr;  
};

If we ran the following it technically works:

Steamroller([1]);// Result
[1]

But if we ran a bigger array [1, [2], [[3]]] we get something like the following:

Steamroller([1, [2], [[3]]]);// Result
[1, Array(1), Array(1)];

This is deceiving though because what’s really happening is that following does get called, but it continues on the end return which just displays the exact same array we gave it. That’s because we also need to return the recursive function results as well.

...
   if (arr.length > 0) { // True but skips ahead
      Steamroller(arr.slice(1));
   }
   return arr; // And just returns this (end of the function)
}

When we modify it, we now get the following:

...
   if (arr.length > 0) {
      return Steamroller(arr.slice(1));
   }
   return arr;
};Steamroller([1, [2], [[3]]]);// Result
[]

This happens because of the following breakdown:

[1, [2], [[3]]] // Original Array
[[2], [[3]]] // After Array.slice
[[[3]]] // After Array.slice again
[] // After Array.slice the last time
[] // Returned because the array length is zero

So we succeeded in iterating the array, but we need to keep track of each value and retrieve just the value within the nested array.

Storing Values & Diving Deeper

The best way to keep track of things through a single value is either as an Object or an Array and in this case, since we’re suppose to return an Array, it makes sense to store things as an Array.

Modifying Our Last Return

Since our return Steamroller(arr.slice(1) already assumes it’s an Array, we’ll modify our last return by wrapping it in Array with [].

...
   if (arr.length > 0) {
      return Steamroller(arr.slice(1));
   }
   return [arr];
};Steamroller([1, [2], [[3]]]);
 
// Result
[Array(0)]

Doesn’t get us closer to our final value, but it does wrap out last value as an Array, which is important, if we can assume that the last value is not an array and just a value.

Getting Just The Value

Array.slice helps us to iterate over the Array but we need to get the value, and if we assume that we’re always removing the first value, then we can assume that we break down the first index.

...
   if (arr.length > 0) {
      return Steamroller(arr[0]);
   }
   return [arr];
};
 
Steamroller([1, [2], [[3]]]);
 
// Result
[1]

Combining Iteration & Storing

We got the first value, but we still need to continue iterating through the rest of the Array. We also need to keep the results that we already got and combine them with our future results. This is where we’ll use Array.concat to combine our results, because we can assume the last return is always going to be a [arr].

...
   if (arr.length > 0) {
      return Steamroller(arr[0]).concat(Steamroller(arr.slice(1));
   }
   return [arr];
};
 
Steamroller([1, [2], [[3]]]);
 
// Result
[1, 2, Array(0), 3, Array(0), Array(0), Array(0)]

Now we got all the values, but got a few extra values, that’s because of our condition of arr.length > 0, what happens when the Array length is zero, it still continues on to return [arr] which is an Array wrapped in another Array.

Handling Empty Arrays

Using Array.concat it manages to clean up empty arrays:

[].concat([1, 2, 3]);// Result
[1, 2, 3][5, 6].concat([]);// Result
[5, 6]

So we just need to return an empty Array when the Array length is zero.

const Steamroller = (arr) => {
   if (arr instanceof Array) {
      if (arr.length === 0) {
          return [];
      } 
      if (arr.length > 0) { 
          return Steamroller(arr[0]).concat(Steamroller(arr.slice(1)));
      } 
   }

   return [arr];  
};Steamroller([1, [2], [[3]]]);
 
// Result
[1, 2, 3]

Optimizing Our Code

If there are multiple ifs and the only condition is if the Array length is zero or not, then we could use a ternary operator.

const Steamroller = (arr) => {
   if (arr instanceof Array) {
      return arr.length === 0 ? [] : Steamroller(arr[0]).concat(Steamroller(arr.slice(1)));
   }
   return [arr];
}Steamroller([[["a"]], [["b"]]]);// Result
["a", "b"]

Final Solution

Here’s our final solution:

const Steamroller = (arr) => {
   if (arr instanceof Array) {
      return arr.length === 0 
         ? [] 
         : Steamroller(arr[0]).concat(Steamroller(arr.slice(1)));
   }
   return [arr];
}

Alternate Solution

You could also use the latest Spread syntax with ...:

const Steamroller = (arr) => {
   if (arr instanceof Array) {
      return arr.length === 0 
         ? [] 
         : [...Steamroller(arr[0]), ...Steamroller(arr.slice(1))];
   }
   return [arr];
}

Testing

Just to make sure it’s working correctly, let’s test a few scenarios.

Steamroller([[["a"]], [["b"]]]); // ["a", "b"]
Steamroller([1, [2], [3, [[4]]]]); // [1, 2, 3, 4]
Steamroller([1, [], [3, [[4]]]]); // [1, 3, 4]
Steamroller([1, {}, [3, [[4]]]]); // [1, {}, 3, 4]

Where To Go From Here

Continue going through FreeCodeCamp.org and continue practicing.

If you got value from this, and/or if you think this can be improved, please let me know in the comments.

Please share it on twitter 🐦 or other social media platforms. Thanks again for reading. 🙏

Please also follow me on twitter: @codingwithmanny and instagram at @codingwithmanny.