Created
August 3, 2016 18:35
-
-
Save voter101/f5a26b55c6a3b01f6f649c0a0e0b25a7 to your computer and use it in GitHub Desktop.
Flattening nested arrays in JavaScript
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Let me present my steps in finding the right solution. If you are not interested in seeing the process, | |
// please skip to `flatten2` function. | |
// You can copy-paste the code into your browser - it will run both versions against tests and return output | |
// First approach, a bit naive, split to 2 functions. Let's do it dirty, but working. | |
// | |
// The idea is to use the fact of JavaScript's property of pass-by-reference arguments in function | |
// This solution is in O(n). | |
function flatten1(arr) { | |
var stack = []; | |
arr.forEach(function(e) { | |
flatten_aux(stack, e); | |
}) | |
return stack; | |
} | |
function flatten_aux(acc, e) { | |
e instanceof Array ? | |
e.forEach(function(el) { | |
flatten_aux(acc, el); | |
}) : | |
acc.push(e); | |
} | |
console.log(testFunction(flatten1)); // true | |
// Alright, but with simple usage of `#reduce`, this gets code easier to read. | |
// The solution is still in O(n), but the usage of `concat` makes it slower (as concat creates a new array). | |
// If performance matters, we may try to use Immutable.JS's List implementation (with efficient structural sharing) | |
// or just mutate some array like in `flatten1`. | |
function flatten2(arr) { | |
return arr.reduce(function(acc, e) { | |
return e instanceof Array ? // I could have used Array.isArray... | |
acc.concat(flatten2(e)) : | |
acc.concat(e) | |
}, []); | |
} | |
console.log(testFunction(flatten2)); // true | |
// Testing | |
function testFunction(fn) { | |
var test1 = [[1,2,[3]],4]; | |
var test2 = [[[]],[[1]]]; | |
var test3 = []; | |
var resultTest1 = [1,2,3,4]; | |
var resultTest2 = [1]; | |
var resultTest3 = []; | |
return arraysEqual(fn(test1), resultTest1) && | |
arraysEqual(fn(test2), resultTest2) && | |
arraysEqual(fn(test3), resultTest3); | |
} | |
// A bit naive (doesn't check if a and b are arrays) | |
function arraysEqual(a, b) { | |
if (a === b) { | |
return true; | |
} | |
if (a.length != b.length) { | |
return false; | |
} | |
for (var i = 0; i < a.length; i++) { | |
if (a[i] !== b[i]) return false; | |
} | |
return true; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment