Sorting Nested Array

Question

Recently on SO there was this question

i am trying to get sequence index of each array of array like I have an element of the array and that 5 arrays have multiple elements and I want to get the first index of each array then the second and so.

below is my array data const arrData = [[1,2,4,6],[3,8,7],[12,13],[],[9,10]];

and my expected outout [1,3,12,9,2,8,13,10,4,7,6]

This is very basic but I found it interesting and tried to solve it.

I solved it like this, I thought it is easy to understand and to read but in reasons that I go in every nested array through all elements maybe it is not the best solution.

For example if I have one array with length 100 and all the other ones are just have length 1.

What do you think about my code?

const arr = [ [1, 2, 4, 6], [3, 8, 7], [12, 13], [], [9, 10] ]; let biggestLength = Number.MIN_VALUE; for (let i = 0; i < arr.length; i++) { if (arr[i].length > biggestLength) { biggestLength = arr[i].length; } } let result = []; for (let l = 0; l < biggestLength; l++) { for (let k = 0; k < arr.length; k++) { if (arr[k][l] !== undefined) { result.push(arr[k][l]) } } } console.log(result)

Answer 1

Bug

The second function does not work. The break will exit the inner loop before all arrays have been processed. Having a short arrays does not mean the following arrays will also be short.

However looks like you copied it from an answer so not really your code (apart from the bug you added).

Question

"What do you think about my code?"

The first snippet.

• Not too bad.
• Some odd naming.
• A little old school in terms of style.
• A few missing semicolons.

Always create functions

When ever you write code, even as example or experiment write it as a named function with arguments as input, and return the result. This forces you to name the code and changes the way you conceptualize the problem. It may seem like a trivial thing to do, and may not always be useful, however good habits need repetition to pick up.

Number.MIN_VALUE

Javascript has some clangers that should never have been let into the language. This is one of them.

The name suggests MIN as in minimum. One would expect Math.min(Number.MIN_VALUE, anyNumber) to always return Number.MIN_VALUE. But no.

Rather it is the smallest positive number greater than 0 or 5e-324 and also happens to the largest negative number if you change the sign -Number.MIN_VALUE === -5e-324. I wonder what that would be called if they named that.

Number.MIN_VALUE is as close to useless as you can get. To understand it requires a good working knowledge of Floating point numbers. The minimum practical positive number is Number.EPSILON and defines the maximum precision of JavaScripts number.

I digress. Your code....

let biggestLength = Number.MIN_VALUE;

Your code works the smallest non empty array has a length of 1. Any number smaller than Number.MIN_VALUE; would also have worked.

let biggestLength = 0; // would be best for arrays sizes. 

Avoid indexing arrays out of bounds.

I can not think of a good reason to do this unless the array has undefined items within the array length.

You have

if (arr[k][l] !== undefined) {

It works as a test to see if you have gone past the end of the array. But you pay a huge cost. I am not sure why, but indexing outside an arrays bounds is just over 5 times slower than testing against the array size (chrome)

You may say. "Its just a single test how much of a difference can it make."

Well if you change the test to what you actually intended

if (l < arr[k].length) { 

Then run the function on 100 arrays of random sizes 1 to 100 the difference is 25%. That means you can process ~125 arrays in the same time as 100.

JavaScript rule of thumb somearray[i] !== undefined should never replace i < somearray.length

Iterators

You are using for ;;; type loops to iterate the arrays. Meaning accessing the arrays is via an index, array indexing is harder on the eyes than direct referencing.

Note replacing biggestLength with theMostGiganticArraysLength no no sorry, with max

You have

for (let i = 0; i < arr.length; i++) { if (arr[i].length > max) { max = arr[i].length; } } 

Use for of loops if you do not need the item index, the loop becomes...

for (const array of arr) { if (array.length > max) { max = array.length; } } 

As you only want length you could also extract the length via destructuring

for (const {length} of arr) { if (length > max) { max = length; } } 

Note there is a small performance penalty using the for of loop in this case.

Finding max length

The first loop is redundant as you can do that inside the main nested loop. You only need the max value to know when to stop. At minimum you need to look at each array at least once to check length.

You set the max to 1 at the start to make sure you look at each array at least once. As you go check the array length for a max length. After the first inner loop you have the first column of values added and the max array length.

There are many ways you could do this.

function interlacedFlat(arrays) { const result = []; var max = 1; for (let i = 0; i < max; i++) { for (const array of arrays) { if (i < array.length) { result.push(array[i]); if (!i && max < array.length) { max = array.length } } } } return result; } 

or

function interlacedFlat(arrays) { const result = []; var max = 1, i = 0; do { for (const array of arrays) { if (i < array.length) { result.push(array[i]); max < array.length && (max = array.length); } } } while (++i < max); return result; } 

or

function interlacedFlat(arrays) { const result = []; var max = 1, i = -1; while (i++ < max) { for (const array of arrays) { if (i < array.length) { result.push(array[i]); max = i + 1; } } } return result; } 

Answer 2

For a better way of identifying the biggestLength, consider mapping each array to its length and spreading the result into Math.max.

Since the arr variable actually contains multiple arrays, I think it'd be a bit more appropriate to call it something like arrs (plural) to avoid possibly mixing it up with one of the single arrays of numbers.

You can also use const instead of let for result (since it never gets reassigned, constshould be preferred).

const arrs = [ [1, 2, 4, 6], [3, 8, 7], [12, 13], [], [9, 10] ]; const biggestLength = Math.max(...arrs.map(subarr => subarr.length)); const result = []; for (let l = 0; l < biggestLength; l++) { for (let k = 0; k < arrs.length; k++) { if (arrs[k][l] !== undefined) { result.push(arrs[k][l]) } } } console.log(result);

Answer 3

Overall your code is readable and it seems reasonably clear what it does. As you said, the code is somewhat inefficient if one of the arrays is much larger than the rest, but for your example (and honestly, even if you had a thousand items in one array), the time cost would probably be negligible, unless the number of arrays in arr is very very large.

Number.MIN_VALUE

Number.MIN_VALUE is not what you think it is. It represents the smallest positive number that can be represented, not the most negative number. As a result, if you use let arr = []; you end up with a biggestLength that is slightly more than 0 and run your second loop... only to figure out that you do not have items. Or arrays, This in itself does not break anything, but you could just initialise biggestLength to 0 and things would work out fine.

Optimising

As I said earlier, the amount of time it takes to do this operation is negligible, even if you have 100 items in the first array. With 11 items over 4 arrays (16 operations) it takes me 0.010ms, and with 107 items over 4 arrays (400 operations) it takes me 0.025ms.

const arr = [ [1, 2, 4, 6], [3, 8, 7], [12, 13], [], [9, 10] ]; function getUnfoldedArray(arr) { let biggestLength = Number.MIN_VALUE; for (let i = 0; i < arr.length; i++) { if (arr[i].length > biggestLength) { biggestLength = arr[i].length; } } let result = []; for (let l = 0; l < biggestLength; l++) { for (let k = 0; k < arr.length; k++) { if (arr[k][l] !== undefined) { result.push(arr[k][l]) } } } return result; } console.time('First run is always slower'); getUnfoldedArray(arr); console.timeEnd('First run is always slower'); console.time('time1'); const result = getUnfoldedArray(arr); console.timeEnd('time1'); // 0.010ms arr[0] = []; for (let i = 0; i < 100; i++) { arr[0].push(i); } console.time('time2'); const result2 = getUnfoldedArray(arr); console.timeEnd('time2'); // 0.025ms console.log(result); console.log(result2);

If you don't mind destroying the array you are doing stuff on, you can potentially use Array.shift(). You could also splice out any empty arrays then, but keep in mind that loops will mess up when you do that. Overall your code would probably get more complicated for not a lot of gain.