Javascript: Flatten multidimensional array in place using recursion

Question

I have the following code that flattens a multidimensional array

var x = [[[2, 3], 4], 5, [6, 7]];

function flatten(arr) {

  for (var i = 0; i < arr.length; i++) {
    if (arr[i].constructor === Array) {
      subArr = arr[i];
      // Shift the array down based on the space needed for the sub array
      for (var j = arr.length + subArr.length - 2; j > i + subArr.length - 1; j--) {
        arr[j] = arr[j - subArr.length + 1];
      }
      // Insert sub array elements where they belong
      for (var k = 0; k < subArr.length; k++) {
        arr[i + k] = subArr[k]; 
      }
      // Look at arr[i] again in case the first element in the subarray was another array;
      i--;
    }
  }
}

flatten(x);

JSBin here: http://jsbin.com/gazagemabe/edit?js,console

I want to do this using recursion but I end up getting stuck. I'm trying to do it without keeping a temp array, but then things seem to fall out of whack. I feel like I'm missing some core principal of recursion.

I realize I need a base case. The only case I can come up with is when the array currently in flatten has no subarrays. But since I'm always passing the array by reference, I have nothing to return.

My psuedo-code is

function flatten(arr) 

  loop through arr
    if arr[index] is an array
      increase the array length arr[index] length
      flatten(arr[index])
    else
      // unsure what to do here to modify the original array

Answer 1

Do the recursive flattening from the inside out. First call the flatten function on the array that you find, then move the contents of that (now flat) array into the parent array. Loop backwards through the array so that you don't have to adjust the loop variable for the items that are inserted.

As you know that the arrays that you insert are flat, you can use the splice method to replace an array with its items.

It works like this:

start with
[[[2, 3], 4], 5, [6, 7]]

flatten [6,7] (which is already flat) and insert:
[[[2, 3], 4], 5, 6, 7]

flatten [[2, 3], 4] recursively calls flatten [2,3] and inserts in that array:
[[2, 3, 4], 5, 6, 7]
then it inserts [2, 3, 4]:
[2, 3, 4, 5, 6, 7]

Code:

function flatten(arr) {
  for (var i = arr.length - 1; i >= 0; i--) {
    if (arr[i].constructor === Array) {
      flatten(arr[i]);
      Array.prototype.splice.apply(arr, [i, 1].concat(arr[i]));
    }
  }
}

var x = [[[2, 3], 4], 5, [6, 7]];

flatten(x);

// Show result in snippet
document.write(JSON.stringify(x));

Answer 2

Here is a purely recursive version that works completely in place, and builds no intermediate arrays.

// Deep-flatten an array starting at index `i`.
function flatten(a, i = 0) {                                                                              

  if (i >= a.length)                                                                                      
    // Null case--we are off the end of the array.                                                        
    return;                                                                                               

  var elt = a[i];                                                                                         

  if (!Array.isArray(elt))                                                                                
    // Element is not an array. Proceed to next element.                                                  
    i++;                                                                                                  

  else                                                                                                    
    // Element is an array.                                                                               
    // Unroll non-empty arrays; delete empty arrays.                                                      

    if (elt.length) {                                                                                     
      // Non-empty array.                                                                                 
      // Unroll it into head and tail.                                                                    

      // Shift elements starting at `i` towards end of array.
      // Have to do this recursively too--no loops!                                             
      (function shift(a, i, n = a.length) {                                                               
        if (n > i ) a[n] = a[n-1], shift(a, i, --n);                                                      
      }(a, i));                                                                                           

      // Replace elt with its head, and place tail in slot we opened up.                                  
      a[i] = elt.shift();                                                                                 
      a[i + 1] = elt;                                                                                     
    }                                                                                                     

  else                                                                                                    
    // Array is empty.                                                                                    
    // Delete the element and move remaining ones toward beginning of array. 
    // Again, have to do this recursively!                             
    (function unshift(a, i) {                                                                             
      if (i < a.length) a[i] = a[i+1], unshift(a, ++i);                                                   
      else a.length--;                                                                                    
    }(a, i));                                                                                             

  flatten(a, i);                                                                                          

}                                                                                                         

var arr = [[[2, 3], 4], 5, [6, 7]];                                                                   
flatten(arr);                                                                                             
console.log(arr);                                                                                         

[2, 3, 4, 5, 6, 7]         

This solution uses bits and pieces of ES6, such as default function parameters and Array.isArray. If you don't have ES6 available, adapt accordingly.