FCC Algorithm Challenges
by strongeleeroy

FCC Bonfire Series 135: Steamroller

This time, I bring a few solutions for the Steamroller bonfire. This guy has been a problem for many campers before, as it deals with recursion, a concept that may take some time to understand properly. As always, we will explore a few solutions, and will see how these perform.

Steamroller will have us write a function that takes in a nested array. This nested array could have any number of nesting levels. Our function must turn that array into a flat one. Enough chatter though, here’s what I’m talking about:

var nestedArray1 = [1, 2, 3, [4, 5, 6], [7, 8]];
steamroller(nestedArray1); //-> [1, 2, 3, 4, 5, 6, 7, 8];

var nestedArray2 = [[1, 2, [3, 4, [5, 6]]], 7, 8];
steamroller(nestedArray2); //-> [1, 2, 3, 4, 5, 6, 7, 8];

As you can see, no matter how many levels of nesting we throw at it, it should always return a flat, non-nested array. For the first solution, we’ll try to keep it clean. It’s obvious that we need a way of checking if an item is an array or not at some point. We are going to create a new variable (named flatArray) where we’ll store values as we flatten the different items in the input array. If the current item is not an array, we push it into flatArray, but if it is, we proceed to flatten it. Let’s do it step by step:

function steamroller(array) {
  var flatArray = [];

  // Do some flattening magic.

  return flatArray;
}

That’s just the bare-bones; notice how we create and return the flatArray varible. Let’s add some logic to it by looping over each item (using forEach), and checking if the current item is an array using the Array.isArray() method. Array.isArray() takes in an argument and returns true if said argument is an array, or false if it isn’t:

var myNumber = 3;
Array.isArray(myNumber);  //-> false

var myWord = 'Hey';
Array.isArray(myWord);  //-> false

var myArray = [3, 'Hey', 37];
Array.isArray(myArray);  //-> true

Let’s use this knowledge in the steamroller function:

function steamroller(array) {
  var flatArray = [];

  array.forEach(function(item) {
    if (!Array.isArray(item)) {   // Not an array.
      flatArray.push(item);       // We push it to the result array.
    } else {
      // Item is an array, so we flatten it somehow!
    }
  });

  return flatArray;
}

The idea is there, we just need a way of executing it. Let’s create a flatten function that takes an array and flattens it. Since we need it to accout for varying levels of nesting, it should do the following: Go item by item, if the item is not an array, push it to a results array; if it’s an array itself, flatten it. Sounds familiar? We just did it actually, we are already flattening an array by pushing items to the results array, so why not take what we already have, and put it inside a function that calls itself when needed? Let’s see how it looks like:

function steamroller(array) {
  var flatArray = [];

  flatten(array);   // We call it once on the input array.


  function flatten(array) {
    array.forEach(function(item) {
      if (!Array.isArray(item)) {
        flatArray.push(item);
      } else {
        flatten(item);        // If current item is an array, call flatten on it.
      }
    });
  }

  return flatArray;
}

It may seem confusing, I know, so I’m going to use an example and go line by line, so you can see what’s happening at each iteration:

var myArray = [1, [2, 3], 4];

steamroller(myArray);

function steamroller(array) {     // array = [1, [2, 3], 4];
  var flatArray = [];             // flatArray = [];

  flatten(array);                 // array = [1, [2, 3], 4];

  function flatten(array) {           // flatten([1, [2, 3], 4]);  See below for what happens in each cycle of the forEach loop.
    array.forEach(function(item) {
      if (!Array.isArray(item)) {
        flatArray.push(item);
      } else {
        flatten(item);
      }
    });
  }

  // flatten([1, [2, 3], 4])
    // forEach starts:
      // item = 1
      // NOT AN ARRAY SO: flatArray = [1]; Next cycle:
      // item = [2, 3];
      // IS AN ARRAY SO: flatten([2, 3])
        // inner forEach stars:
          // item = 2
          // NOT AN ARRAY SO: flatArray = [1, 2]; Next cycle:
          // item = 3
          // NOT AN ARRAY SO: flatArray = [1, 2, 3]; inner forEach ends.
      // item 4
      // NOT AN ARRAY SO: flatArray = [1, 2, 3, 4]; forEach ends. Function finishes executing.

  return flatArray; // returns flatArray = [1, 2, 3, 4];
}

It may still sound a bit confusing, but that’s what makes recursion so beautiful, the only way to get a solid understanding is by practising and tracking the variables inside until you get it to work inside your head.

Now that we have a working solution, let’s make it faster. Array.prototype.forEach() is very useful when we need to get some more complex stuff done, but the for loop is incredibly faster at looping over array items. Let’s make the switch to that and see how it goes:

function steamroller(array) {
  var flatArray = [];

  flatten(array);

  function flatten(array) {
    for (var i = 0; i < array.length; i++) {
      if (!Array.isArray(array[i])) {
        flatArray.push(array[i]);
      } else {
        flatten(array[i]);
      }
    }
  }

  return flatArray;
}

Does the same thing as before, it just does it much faster (remember that forEach will still be more readable and will allow passing custom functions to it, but keep in mind that when talking performance, the for loop is faster).

Now, I’ll write down another function that also works, and is even faster that the previous. Why? You’ll have to think about it yourself this time!