Many ways to skin a cat (or flatten an array) in JavaScript
Recently I came across a simple tech challenge:
Given a deeply nested array, return a flattened array;eg:
var a = [1,[2,[3,4]]];
console.log(flatten_array(a)); // [1,2,3,4]
This challenge seemed fairly simple, however my initial attempts to solve it left much to be desired in both efficiency and code elegance, so I started to try and figure out all the different ways one could accomplish this task in JavaScript. Here are some guidelines:
- The array can be composed of any type of items (numbers, strings, objects, etc)
- The function should return a new array, without morphing the original array.
- Here are some test cases:
var a = [1,[2,[3,4]]];
var b = ['Boki',['does','not'],'know',[{'what': 'shit'}]]];
var c = [1,[2,3,4],5,[[6,7],8]];console.log(flatten_array(a));
// [1,2,3,4]console.log(flatten_array(b));
// ['Boki','does','not','know',{'what': 'shit'}]console.log(flatten_array(c));
// [1,2,3,4,5,6,7,8]console.log(a);
// [1,[2,[3,4]]]console.log(b);
// ['Boki',['does','not'],'know',[{'what': 'shit'}]]]console.log(c);
// [1,[2,3,4],5,[[6,7],8]]
So here are some different approaches that I could come up with.
Simple recursion:
function flatten_array(arr) {
if (!arr) { return arr; }
let ret = [];
for (let i in arr) {
if (Array.isArray(arr[i])){
ret = ret.concat(flatten_array(arr[i]));
} else {
ret.push(arr[i]);
}
}
return ret;
This is the first thing I came up with. It’s simple and easy to understand, however its not very elegant nor is it optimized. If we look at the solution we see that we’re using both Array.push, which modifies the ret inline, and Array.concat which returns a new array so we have to override the entire value of ret with the new array. The bigger problem however is how many arrays we’re instantiating to create this solution. Lets walk through the loop:
arr = [1,[2,[3,4]]]*[] // we start with an empty array ret// Loop 1[1] // ret is just modified// Loop 2
// Loop 2.0 Recursion
*[] // new ret is created for the recursive call // Loop 2.1
[2] // new ret is just modified // Loop 2.2
// Loop 2.2.0 Recursion
*[] // new ret is created for the recursive call // Loop 2.2.1
[3] // new ret is just modified // Loop 2.2.2
[3,4] // new ret is just modified
*[2,3,4] // created by concat
[2,3,4] // ret is set to new array*[1,2,3,4] // created by concat
[1,2,3,4] // ret is set to new array
So what we can see is that this algorithm has to create 2 new arrays for each nesting. Worst case scenario is that if each element is an array, then the Big-O space is actually O(2n) => O(n), which is actually pretty bad for such a simple algorithm.
Splicing Inline
function flatten_array(arr) {
if (!arr) { return arr; }
let ret = arr.concat();
for (let i=0; i<ret.length; i++) {
if(Array.isArray(ret[i])) {
Array.prototype.splice.apply(ret, [i,1].concat(ret[i]));
i--;
}
}
return ret;
}Another way we can do this is by cloning the array and modifying it inline. This example goes through a copy of the original array and replaces each sub-array with its contents. This saves us creating that initial empty array, however in order to splice the contents in, we have to combine the splice parameters and the items of the array to pass in. We can do this by calling Function.prototype.apply, however that takes in all the arguments in as an array, and so we still have to create a new array to construct the right params. In practice this saves us some space, however we’re still in the O(n) space here.
Splicing Inline with ES6
The above solution comes so close, but we’re still stuck with creating new arrays. To solve this, we can use the handy dandy spread operator!
function flatten_array(arr) {
if (!arr) { return arr; }
let ret = arr.concat();
for (let i=0; i<ret.length; i++) {
if(Array.isArray(ret[i])) {
Array.prototype.splice.call(ret, i, 1, …ret[i]);
i--;
}
}
return ret;
}Now we’re just cloning the array once and all the operations are happening within the single splice call. Since we can use the spread operator we can call Function.prototype.call and don’t have to worry about creating new arrays just for props.
Array.prototype.map
function flatten_array(arr) {
if (!arr) { return arr; }
var output = [];
arr.map(function(item) {
if(Array.isArray(item)){
output = output.concat(flatten_array(item));
} else {
output.push(item);
}
return item;
});
return output;
}This is just a ridiculous implementation that uses Array.prototype.map using it as an iterator. It’s functionally identical to the simple recursion example, however its even more obscure and defeats the purpose of using map…it’s just an unnecessary implementation.
Array.prototype.reduce
function flatten_array(arr) {
if (!arr) { return arr; }
return arr.reduce(function(flat, next) {
return flat.concat(Array.isArray(next) ? flatten_array(next) : next);
}, []);
}Using Array.prototype.reduce actually yields a very elegant solution. Reduce walks through an array and performs a callback on each item and the previous result. It’s a very cool implementation, however it still suffers from the Array.prototype.concat problem.
Better Recursion
function flatten_array(array) {
if (!array) { return array; }
let ret = [];
function traverse(arr, output) {
if (!arr) { return arr; }
for (var i in arr) {
if (Array.isArray(arr[i])) {
traverse(arr[i], output);
} else {
output.push(arr[i]);
}
}
}
traverse(array, ret);
return ret;
}Each of the previous examples had varying approaches and different levels of elegance, but all suffered from the fact that we had to keep creating arrays in memory. This implementation finally addresses that problem. The recursion here is actually embedded within the flatten_array function. One new array is created and then is referenced through the recursive function and mutated in place. The traverse function just walks through each element, and if it’s not an array it pushes it into the passed in reference. It, not very elegant, however it is very efficient as its the only implementation that does not mutate the input and only creates a single new array as the output.
Generators
function flatten_array(array) {
if (!array) { return array; }
function *traverse(arr){
if (!arr) { return arr; }
for (let i in arr) {
if (Array.isArray(arr[i])){
yield *traverse(arr[i]);
} else {
yield arr[i];
}
}
} let ret = [],
it = traverse(array),
res = it.next();
while(!res.done){
ret.push(res.value);
res = it.next();
}
return ret;
}
With the new ECMA2017 draft spec of generators, we can actually reintroduce some elegance into the Better Recursion example. The inner *traverse function is no longer mutating an array in place. It’s just providing an iterator that walks through the nested array and returns each non array element in a row. We then execute the generator and loop though it pushing each element into a new return array ret.
EDIT:
My friend Chase Murphy just pointed out to me that we could simplify this even further by using the spread operator instead of the while loop:
function flatten_array(array) {
if (!array) { return array; }
function *traverse(arr){
if (!arr) { return arr; }
for (let i in arr) {
if (Array.isArray(arr[i])){
yield *traverse(arr[i]);
} else {
yield arr[i];
}
}
}
return [...traverse(array)];
}Edge Case Array.prototype.map (will only work with numbers)
function flatten_array(arr) {
if(!arr) {return arr;}
return arr.toString().split(',').map(function(item) {
return parseInt(item, 10);
});
}I came across and interesting solution for solving this problem if all we have is numbers. Array.prototype.toString will actually flatten an array for us and return a comma value separated string which then we can split back into an array and map through to convert to Array.prototype.map to iterate through and convert the string values back into numbers. This approach could be extended for strings as well, but will not work for nested objects or boolean values.