Flatten and Sort an Array of Arrays JavaScript

Link to the video

365 days of coding day 2! How to flatten, filter, and sort and array in JavaScript. The solution for a popular interview question flatten an array taken one step further to make it an array with only the unique values and have it sorted in numerical order. I did add strings to the tests later today so I apologize for the people earlier that just got numbers. for their tests.

Disclaimer: there are MANY ways to solve this problem this is an answers that I would see or use in a coding interview and would accept as a proper answer

TLDR: explanation of the solution at the bottom of the post

The Problem

Write a function that accepts an array of numbers or strings this can be an array with any number of nested arrays. Flatten the array (make all one level), put it in numerical order of distinct numbers from the original array

Examples:

    flattenFilterAndSort([1, 1, 6, 9])  //[1, 6, 9]   
    flattenFilterAndSort([20, [3, 5], 10])  //[3, 5, 10, 20]   
    flattenFilterAndSort([[1,2,3],[[4,5],6,[7,8,9], 19, 21, [0, 1], ]])  //[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 19, 21]
    flattenFilterAndSort(['Marv', ['Dakota', 'Boo'], 'Dakota']) //['Boo', 'Dakota', 'Marv']
    flattenFilterAndSort(['Happy', [['New'], ['Year']]]) //["Happy", "New", "Year"]

The Solution

To do this we are going to need a recursive function. A recursive function is a function that calls itself. If you are not familiar with recursion and would like to read more about it check out this page.

So lets break down what we need to do

• create a function that accepts and array

• create a new array to hold everything

• loop through the passed array

  • check if the current index is an array

    • if its an array
      • if its only a single level array concatenate that array with the current array
      • otherwise call flattenFilterAndSort again to do the same checks - recursion is here
    • if not push the current index to the new array and continue the loop

• once loop has ended

  • filter the loop to be only unique values
  • sort those values

First we need to create a function

function flattenFilterAndSort(arr){
    // create a new array to hold everything
    // loop through the passed array
        // check if the current index is an array
            // if its an array 
                // if its only a single level array concatenate that array with the current array
               // otherwise call flattenFilterAndSort again to do the same checks - recursion is here
          // if not push the current index to the new array and continue the loop
    // once loop has ended
        // filter the loop to be only unique values
       // sort those values
}

now we need to create a new array to hold our final flattened array

function flattenFilterAndSort(arr){
    let flatArray = []
    // loop through the passed array
        // check if the current index is an array
            // if its an array 
                // if its only a single level array concatenate that array with the current array
               // otherwise call flattenFilterAndSort again to do the same checks - recursion is here
          // if not push the current index to the new array and continue the loop
    // once loop has ended
        // filter the loop to be only unique values
       // sort those values
}

now we need to loop through the array that was passed. If you are not familiar with for loops check out this W3Schools page.

function flattenFilterAndSort(arr) {
    let flatArray = [];
    for(var i = 0; i < arr.length; i++) {
        // check if the current index is an array
            // if its an array 
                // if its only a single level array concatenate that array with the current array
               // otherwise call flattenFilterAndSort again to do the same checks - recursion is here
          // if not push the current index to the new array and continue the loop
    // once loop has ended
        // filter the loop to be only unique values
       // sort those values
    }
}

Now we need to check if the current index is an array. If you are unfamiliar with .isArray() check out this MDN page.

function flattenFilterAndSort(arr) {
    let flatArray = [];
    for(var i = 0; i < arr.length; i++) {
         if(Array.isArray(arr[i])) {
            // if its an array 
                // if its only a single level array concatenate that array with the current array
               // otherwise call flattenFilterAndSort again to do the same checks - recursion is here
         } else {
          // if not push the current index to the new array and continue the loop
         }
    // once loop has ended
        // filter the loop to be only unique values
       // sort those values
    }
}

Now here comes the fun part. If you are unfamiliar with .concat() check out this MDN page before going any further.

If you use .concat() on an array it will merge that array with the array you are concatenating it with making it one flat array. This means that we need to concatenate the new array with any array we may run into. However, we first need to check if those arrays also have nested arrays (we need to loop through those arrays the same way we are the first array) this is when recursion comes in. So for each array we run into we are going to call the same function we are already calling to make sure those arrays are flattened. Once the arrays are flat we will concatenate them until all of the arrays have been concatenated and we have 1 flat array. The recursion is going to look like this:

function flattenFilterAndSort(arr) {
    let flatArray = [];
    for(var i = 0; i < arr.length; i++) {
         if(Array.isArray(arr[i])) {
            flatArray = flatArray.concat(flattenFilterAndSort(arr[i]));
         } else {
          // if not push the current index to the new array and continue the loop
         }
    // once loop has ended
        // filter the loop to be only unique values
       // sort those values
    }
}

This may look a little confusing since we are setting flat array to an empty array in the beginning of the function so each time we recursively go over it we are setting it to []. You have to remember though this is happening recursively. It hasn’t concatenated anything until the arrays are flat. So it is only looping through the array we are currently on not the ones before it. Every time it gets to a flat array it will concatenate it with the array that came before it. So imagine that it is finding the most nested array first then concatenating that to the one before it and so on and so on until it is all one level then concatenating that to the original flat array. If this doesn’t make sense try putting a console log on line 6 (right after flatArray = flatArray.concat(flattenFilterAndSort(arr[i]))) once you have the final answer and you can see what flat array is on each loop it may make more sense to you here is an example:

If it is not an array then all we have to do is put it in the flat array just the way it is. If you are unfamiliar with .push() you can check out this MDN page.

function flattenFilterAndSort(arr) {
    let flatArray = [];
    for(var i = 0; i < arr.length; i++) {
        if(Array.isArray(arr[i])) {
            flatArray = flatArray.concat(flattenFilterAndSort(arr[i]));
        } else {
            flatArray.push(arr[i]);
        }
    }
      // once loop has ended
        // filter the loop to be only unique values
       // sort those values
}

We have to filter the flattened array. You can do this with .filter() however I am going to spread the flatArray into a new Set because its easier. If you are unfamiliar with any of those I have linked the MDN pages to them.

function flattenFilterAndSort(arr) {
    let flatArray = [];
    for(var i = 0; i < arr.length; i++) {
        if(Array.isArray(arr[i])) {
            flatArray = flatArray.concat(flattenFilterAndSort(arr[i]));
        } else {
            flatArray.push(arr[i]);
        }
    }
    return [...new Set(flatArray)]
    //sort those values
}

Now all we have to do is sort them. we need to check if the array is an array of strings or an array of numbers first because this will determine how we need to sort them. with numbers you have to tell .sort() how to sort them with strings it will automatically sort them alphabetically if you just use .sort(). If you are unfamiliar with this check out this MDN page

function flattenFilterAndSort(arr) {
    let flatArray = [];
    for(var i = 0; i < arr.length; i++) {
        if(Array.isArray(arr[i])) {
            flatArray = flatArray.concat(flattenFilterAndSort(arr[i]));
        } else {
            flatArray.push(arr[i]);
        }
    }
    return typeof(flatArray[0]) === 'string' ? [...new Set(flatArray)].sort() : [...new Set(flatArray)].sort((num1, num2) => {return num1 - num2}) 
}

There you go! Again there are a lot of ways to write this. I like this solution for performance and readability. If you would like to get the challenge each day in you email in the morning subscribe here. Please leave your solutions that you came up with in the comments section. If you have any challenge you would like to see done also leave that in the comments below you may see it come up!

Comments

[𒎏Wii 🏳️‍⚧️]

Why would you filter out duplicates before sorting? Once sorted, duplicates will all be next to each other...

[Hello Dev World Blog]

It isn’t really any easier if they are next to each other and if you don’t flatten first they will still be nested JS will see them as arrays not numbers to sort it will sort the parent arrays and the things within them but it won’t directly yield the results you’re looking for. You’ll still need to flatten it too lol

you could put checking for duplication as part of your loop instead of doing it after if you wanted to though!

[𒎏Wii 🏳️‍⚧️]

Checking an unsorted array for duplication requires keeping track of elements you've seen before though, whereas if they're next to each other you can just walk through the array and drop elements that are the same as the previous one. For longer arrays this can be a considerable memory improvement.

[George]

Thx for explanation. It seems you forgot to change the name of the function where the recursion starts. Change it from 'flatten' to 'flattenFilterAndSort'.

[Hello Dev World Blog]

lol thank you! I did that in the video too I have updated!