Manny

Apr 1, 2020

8 min read
Photo by Nadya Spetnitskaya on Unsplash

JavaScript Flatten Array Algorithm

Breaking Down The Steamroller Algorithm Problem From FreeCodeCamp.org

Goal

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

Real World Use

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

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

Deeply Nested Arrays You Need To Specify Depth

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

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

What This Means

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

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

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

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

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

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

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

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

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.