4
\$\begingroup\$

Write a piece of functioning code that will flatten an array of arbitrarily nested arrays of integers into a flat array of integers. e.g. [[1,2,[3]],4] -> [1,2,3,4].

* tests use Jasmine can be found  http://jsbin.com/harofo/4/edit?html,js,output
* @input  array
* @output array
*/

function flatten(arr) {
    // this function is called in recursion mode
    let result = [];
    if (arr && arr.length > 0) {
        arr.forEach(function(value) {
            if(Array.isArray(value)) {
                result = result.concat(flatten(value));
            } else {
                result.push(value);
            }
        });
    }    
    return result;

};
\$\endgroup\$
3
\$\begingroup\$

Problems with recursion and cyclic infinity.

BTW the best solution is array.flat(10); 10 is recursion depth. See bottom of answer for details on the new Array prototypes.

Call stack overflow

Your code is not protected from call stack overflow,

As amard's answer correctly pointed out recursion is dangerous as the call stack depth is unknowable from within javaScript, (and is a major flaw in the language until we get proper tail calls). Superbly elegant answer BTW +1 (surprised it does not have more up votes)

Unfortunately his answer does, flatten in place, all contained arrays which may have consequences elsewhere, nor does it protect against cyclic references.

Stack overflow from cyclic references

Example of a cyclic reference.

var a = [];
var b = [a];
a.push(b);
flatten(a); // will throw or call stack overflow or worse if
            // a or b were large arrays crash the page with our of
            // memory error.

Cyclic references must always be considered when using recursion or recursive like solutions to iterate over an unknown data set. There is no time or memory that can handle an infinite loop.

Cyclic safe solutions

  • Do as Array.prototype.flat does and use a depth argument to limit recursion depth
  • Track flattened arrays using a Set
  • Use type coercion, String.split, Array.map and Number if items only number like or arrays.

The one liner

Array.toString flattens an array to a string, items separated by a , comma. As coercion is automatic in JavaScript such transformations must be protected against cyclic references.

Method : First the array is converted to a string, you could use .toString but can be forced via a sting contact operator +. Then just split the new string at "," to convert back to array, and if needed convert the array of strings back to numbers with map(Number)

const arr = [1,2,3,[1,2,[4,5],3,4],2];
arr.push([1,2,3,[arr]]);  // create cyclic ref

// one liner flatten array of numbers (or number like items)
const flat = ("" + arr).split(",").map(Number);

Using a Set to remember flatten items.

The following flattenSafe uses Set to track flattened arrays, also to reduce overall memory us by pushing to a single result array rather than create arrays each recursion to be return for addition to the previous iterations array.

Example snippet includes the above oneline method as well.

//==========================================================
// Cyclic data to test on
const a = [1,2,3,4,5,[6,[110,123]]];
// create an array the contains a reference to array a
const b = [[7,8,9],[10,12,13,14,[21,22,a]]];
// create a cyclic reference in a by push b.
a.push(b);

//==========================================================
// Test data cyclic using the most ugly way NOTE this is only 
// situation and not a valid test, don't use it in production 
// code.
try { JSON.stringify(a); log("failed") } catch(e) { log("Cyclic JSON.stringify Throws : " + e.message) } 

//==========================================================
// flatten using toString
const flat = (""+a).split(",").map(Number);

//==========================================================
// recursive cyclic safe flatten
function flattenSafe(arr) {
    if (Array.isArray(arr)) {
        const usedArrays = new Set(); // Note dont add array here
        usedArrays.add(arr); // mark incoming array as used
        const resArr = [];
        (function flatten(arr) {
            for (const item of arr) {
                if (Array.isArray(item)) {
                    if (! usedArrays.has(item) ) { // check this item has not been touched
                        usedArrays.add(item); // add to used Set
                        flatten(item);
                    }
                } else {
                    resArr.push(item);
                }
            }
        })(arr);
        return resArr;
    }
    return arr;
}

const safeFlat = flattenSafe(a);


//==========================================================
// Show results

log("Flat using string " + flat.join("-"));
log("Flat flattenSafe " + safeFlat.join("="));

// Join flattens so you should use console to examine results  
// On snippet console looks bad so I used  above.
// console.log(flat);
// console.log(safeFlat);



function log(str) { document.body.innerHTML += str + "</br>" }
    

Avoid recursion using a stack.

You can also avoid recursion using a while loop and a stack to hold arrays and array indexes. For each item push to flat array unless that item is an array,if so push to the current array and index to stack. Ref the new array as the current and reset index to 0 and iterate each item with same rules. Pop from stack when array index past end and continue until stack is empty, Use Set to test for cyclic arrays as in above example.

JavaScript Array.prototype.flat and Array.prototype.flatMap

New to javascript, and after a long debate about the naming* we finally have Array.flat and Array.flatMap. The latter applies a transform function to each item that is flattened.

Used as

([1,2,[1,2]]).flat(); // default depth 1
([1,2,[1,2,[1,2]]]).flat(2); //  depth 2

* Common libraries use of flatten meant it would break the net and flat is not commonly used as a verb (Verb in music. C flat to lower by a semitone, or language, flat that surface) and for a while it looked like it may have been Array.smoosh

Warning on performance testing re - webNeat's answer

The tests results are off by 2 orders, should be around

  • JSON method 5289ms.
  • Loop method 23ms.

Always run the function several 100 or 1000 times before you start timing, so you don't test the time the optimizer is using.

Always use a global soak. Functions that do not effect external state*1 are simply not run, this is the most basic optimization the optimizer can do. (A soak has its state changed by an unknowable result of the test function.) A function that produces the same result independent of arguments will have the result cached. A function that produces the same result for the same input each time can have the result cached and thus falsifies performance tests)

*1 Note State used to mean browser state not just the JS context.

Order of execution can effect timing, randomize your tests and use a statistical mean to estimate the results of many tests.

NOTE do to an ongoing and unresolved security issue performance.now can not be trusted to give anything above a 0.1-0.2ms accuracy.

\$\endgroup\$
5
\$\begingroup\$

The check for arr.length > 0 is not needed: forEach() can be called on an empty array (and does nothing in that case).

The check if (arr) protects against a call with an undefined argument, but not against a call with a non-array. As an example, flatten(123) would cause a JavaScript error. So you have to decide:

  • If the argument to flatten() is known to be an array then the outer if statement is not needed at all.
  • If flatten() can be called with any argument than you need to check for an array before calling forEach().

See also Flatten an array on how reduce() can be used instead of a loop.

\$\endgroup\$
  • \$\begingroup\$ You write that the check for arr.length > 0 is not needed, but that's not quite true, because on the initial (non-recursive) call, arr may not be an array at all. arr.length > 0` is false if arr.length is undefined, but arr.forEach() throws if arr.forEach is undefined. In effect, arr.length > 0 protects against a call with a non-array argument - at least to some extent, and in a rather unreliable way. flatten(123) with OP's code would not cause an error - it would return []. \$\endgroup\$ – jcsahnwaldt says GoFundMonica Aug 1 '18 at 23:03
5
\$\begingroup\$

There is a practical limit to take into account when it comes to using recursive functions: the size of the call stack.

If the depth of the nested arrays is not limited, you can not use a recursive solution in javascript because most of the time you cannot assume that the interpreter has tail call optimizations: https://stackoverflow.com/questions/37224520/are-functions-in-javascript-tail-call-optimized.

So any recursive solution will fail because of the memory if the input array is very nested.

Therefore I would prefer an iterative solution that does not use a stack. (The iterative solutions that use a stack have the same problems than recursion)

function flatten(array) {
    let i = 0;
    while (i != array.length) {
        let valueOrArray = array[i];
        if (! Array.isArray(valueOrArray)) {
            i++;
        } else {
            array.splice(i, 1, ...valueOrArray);
        }
    }
    return array;
}

Please note that this function modifies its input.

As pointed out by Blindman67, this function will never end if there are cyclic references in the argument. This seems correct because it is impossible to flatten an array with cyclic references in a finite time. However one could detect the cyclic reference and throw an error.

Of course you can use a recursive solution but you should specify in the documentation of your function a limit for the depth of the nested array.

\$\endgroup\$
  • \$\begingroup\$ This is a bad answer. It's very unlikely that an array is so deeply nested that the recursion will blow the stack. In this case, a recursive implementaion is much simpler than iteration. Using iteration is premature optimization. \$\endgroup\$ – jcsahnwaldt says GoFundMonica Jul 31 '18 at 23:28
  • \$\begingroup\$ This is not about performance or optimization, this is about robustness. Indeed I do not know which one between iterative or recursion is faster. But the recursive implementation is less robust. \$\endgroup\$ – amard Aug 1 '18 at 12:47
  • \$\begingroup\$ By the way, your solution also has a severe problem with the size of the call stack. It fails for arrays larger than about 150000 elements: RangeError: Maximum call stack size exceeded. Test code: let a = []; for (let i = 0; i < 200000; i++) a.push(i); a = [a]; flatten(a);Reason: array.splice(i, 1, ...valueOrArray) copies all the array elements onto the call stack. Same error in Node.js 8, 9, 10, 11 and Chrome 68. \$\endgroup\$ – jcsahnwaldt says GoFundMonica Aug 1 '18 at 20:31
  • 1
    \$\begingroup\$ P.S.: I like your code though. It's clever. Took me a moment to understand how it works. On the other hand - that's generally not a good thing if one is trying to write production code. For example, modifying an argument value and changing a loop variable inside the loop should be avoided. That's why I still prefer the recursive solutions - they are simpler. \$\endgroup\$ – jcsahnwaldt says GoFundMonica Aug 1 '18 at 22:30
  • 1
    \$\begingroup\$ Correct, expanding the array with "...valueOrArray" explodes the stack. I agree that for this particular problem, real life arrays are not problematic. \$\endgroup\$ – amard Aug 3 '18 at 10:16
3
\$\begingroup\$

I found simpler solution for this specific case where the array items are integers.

const flatten = array =>
    JSON.stringify(array)
    .match(/\d+/g)
    .map(x => parseInt(x))

I wanted to know if this solution is faster or slower than the loop solution. So I wrote this script

const generate = length =>
  length <= 0 ? []
  : (
    Math.random() < 0.7 
    ? [Math.floor(Math.random() * 1000)] 
    : [generate(length / 2)]
  ).concat(generate(length - 1))

const flattenLoop = array => {
    let i = 0;
    while (i != array.length) {
        let valueOrArray = array[i];
        if (! Array.isArray(valueOrArray)) {
            i++;
        } else {
            array.splice(i, 1, ...valueOrArray);
        }
    }
    return array;
}

const flattenJSON = array =>
    JSON.stringify(array)
    .match(/\d+/g)
    .map(x => parseInt(x))

console.time('generate')
const input = generate(500)
console.timeEnd('generate')

console.time('flattenLoop')
flattenLoop(input)
console.timeEnd('flattenLoop')

console.time('flattenJSON')
flattenJSON(input)
console.timeEnd('flattenJSON')

And the output in my computer is

generate: 2288.048ms
flattenLoop: 3810.580ms
flattenJSON: 2430.594ms

Surprisingly, using JSON.stringify and regular expression is faster! Did I miss something?

\$\endgroup\$
3
\$\begingroup\$

Here's a recursive function whose basic idea is similar to yours:

function flatten(a) {
  if (! Array.isArray(a)) throw new Error('flatten() called with non-array');
  const f = [];
  function p(a) {
    for (let e of a) if (Array.isArray(e)) p(e); else f.push(e);
  }
  p(a);
  return f;
}

Advantages of this version:

  • It avoids copying the nested arrays twice (which happens in result.concat(flatten(value)) in your solution).
  • By using a plain for loop instead of forEach(function ...), the syntax becomes simpler, and we avoid an extra function call in each recursive call, which will probably make things a bit faster (but I haven't measured it).
    • (This also means that it can handle arrays that are nested about twice as deep before it exceeds the stack size, but that's a problem that is extremely unlikely to occur in real life.)
  • The main function flatten is not recursive. It just checks its argument, sets up a data structure, calls the recursive function p which does the main work, and returns the result.
    • Such a split between a 'public' function that is meant to be called by 'normal' users and an 'internal' recursive function that does the actual work is often helpful when you develop recursive functions. The 'public' function has a simple interface and does some housekeeping, the 'internal' function has fewer argument checks or maybe has additional arguments that are not meant to be used by 'normal' callers. This often makes the recursive function simpler and faster.

On my machine, this version can process arrays with millions of elements and thousands of nesting levels in a few seconds.

At the top of the function, I added a check whether the argument is an array. Note that this check is only applied once, not on every recursive call - on a recursive call of p, we already know that the argument is an array.

I also modified the behavior of the function when the argument is not an array:

  • In your original version, an empty array is returned when the value is falsy, doesn't have a length property, or its length is not positive. When it has a positive length property but no forEach() method (e.g. it's a non-empty string), an error is thrown. When it has a length property and a forEach() method, that method is called, which may or may not be useful.
  • In this version, an error is thrown for all non-array arguments.

I generally prefer the 'fail-fast' approach - when an error is detected, don't try to keep working, just fail. But that's a matter of taste. In some cases, it may make sense to for e.g. flatten({}), flatten(123) or flatten('foo') to succeed and return a default value, e.g. an empty array, or the given value, or an array containing the given value.


Here's a solution with a recursive generator function:

function flatten(a) {
  if (! Array.isArray(a)) throw new Error('flatten() called with non-array');
  function* f(a) {
    for (let e of a) if (Array.isArray(e)) yield* f(e); else yield e;
  }
  return Array.from(f(a));
}

Generator functions often allow elegant solutions to problems that are otherwise much harder to solve, but in this case (and probably many others), the performance is quite bad: Processing an array with 40,000 elements takes 10 seconds in Node.js on my machine.

\$\endgroup\$
  • \$\begingroup\$ Obviously recursive functions have advantages but could you please explicitly state why this code is better? Please read this answer for more context. \$\endgroup\$ – Sᴀᴍ Onᴇᴌᴀ Aug 1 '18 at 21:52
  • \$\begingroup\$ @SamOnela Thanks for the link! I'm pretty new here on codereview, probably still working in SO mode. I added a sentence explaining that this solution avoids copying the nested arrays twice. Is that enough? \$\endgroup\$ – jcsahnwaldt says GoFundMonica Aug 1 '18 at 22:03
2
\$\begingroup\$

I cannot figure out better solution than yours, but I can suggest more concise code, though less readable.

function flatten(arr) {
    if (!Array.isArray(arr)) { return []; }
    return arr.reduce(function(acc, x) {
        return acc.concat( Array.isArray(x) ? flatten(x) : [x] );
    }, []);
};
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.