What is the most efficient way to check if n arrays are the same length?

Question

What is the most efficient way to check if n arrays are the same length in JavaScript?

One way or the other you have to examine the `.length` property of all the arrays in question, and that's a linear operation no matter how you do it (assuming you don't do it some way that's crazy). The performance differences between ways of achieving that linear-time result will probably be negligible. — Pointy, Oct 02 '18 at 21:07
@Pointy: Well, you could short-circuit if you found a single length that differed. If the common case is "all are the same length", then yeah, you'll need to check them all most of the time. — ShadowRanger, Oct 02 '18 at 21:12
@ShadowRanger right but that's still just a constant factor. — Pointy, Oct 02 '18 at 21:13

KevBot · Accepted Answer · 2018-10-02T21:25:13.117

6

Use Array.every with the length accessor.

const array1 = [1, 2, 3];
const array2 = [4, 5, 6];
const array3 = [7, 8, 9, 0];

const firstLength = array1.length;
const allSameLength = [array2, array3]
    .every(({length}) => length === firstLength);

console.log(allSameLength);

edited Oct 02 '18 at 21:25

answered Oct 02 '18 at 21:12

KevBot

17,900
5
50
68

2

You can omit `array1` from the array of arrays to check, since you used it to calculate `firstLength` (so it's definitely the same length). Upvoted regardless (the trick of using an accessor for `length` like that was new to me, I like it). – ShadowRanger Oct 02 '18 at 21:14
What's a great way to add all those arrays into a parent array dynamically? – zero_cool Oct 02 '18 at 21:18
@zero_cool: Make them elements of the parent array in the first place? Typically, if you want to store an unknown number of X, the correct solution is an array of X, not a bunch of independent variables that you have to manually combine later. – ShadowRanger Oct 02 '18 at 21:21
@ShadowRanger, that's a great suggestion. @zero_cool, it depends on how they are currently stored. You could for example pass `n` number of arrays to a function, and there ways to handle that too. How is your data currently stored? – KevBot Oct 02 '18 at 21:23
@ShadowRanger Each array is stored on individual objects inside a larger array. I'd like to compare those arrays for equality eventually, and the first step is checking if they are the same length. – zero_cool Oct 02 '18 at 21:25
1

@zero_cool Perhaps you should use a loop to traverse through your array of objects to create another array. You can use `var newArr = [];` to create the array and `newArray.push(some.other.array);` to add objects to that array. – Pluto Oct 02 '18 at 21:29
How would you then check if all the arrays contain the same values? integers in this case. – zero_cool Oct 02 '18 at 21:30
Does their order matter? – Pluto Oct 02 '18 at 21:31
1

@zero_cool, is something like this referring to what you are trying to do? [JSFiddle](https://jsfiddle.net/tcjmw48g/) (Click on the javascript tab) – KevBot Oct 02 '18 at 21:33
That would make an impact. If you keep the order of their contents the same, then I'd recommend using this answer: https://stackoverflow.com/a/19746771/1507941 – Pluto Oct 02 '18 at 21:34
I mean taking it a step further and checking the actual values - so if all the arrays are the same length - then check if they all contain the same values. – zero_cool Oct 02 '18 at 21:34
I think this answer has the solution: https://stackoverflow.com/questions/10110510/underscore-js-determine-if-all-values-in-an-array-of-arrays-match – zero_cool Oct 02 '18 at 21:39

score 2 · Answer 2 · answered Oct 02 '18 at 21:11

If the arrays whose lengths you want to examine are stored inside a "parent" array, then you can simply use every to check whether the length of the iterated array is the same as the length of the first one.

Example:

const array = [
  ["a", "b", "c"],
  [1, 2, 3],
  [[1, 2], 3, "f"]
];

const equal = array.every((val, i, arr) => val.length === arr[0].length);

console.log(equal);

tkiral · Answer 3 · 2018-10-02T21:21:06.307

1

Initialize an array of the arrays, apply the .length function to each element using map and then return whether or not the min and max of the array are equal.

You could also just store a variable that is the first array length you come across and then check to see if each of the arrays is the same length as that array.

I'm not sure if the min/max functions in JS sort or do an O(n) search through the array, but the second method will definitely be O(n).

Edit: I imagine the 'every' function is also O(n) but I'm not sure (I would be very surprised if it is better and less surprised if it is worse).

edited Oct 02 '18 at 21:21

answered Oct 02 '18 at 21:16

tkiral

49
1
9

`min` and `max` are linear, so your first option, while `O(n)`, involves four separate `O(n)` steps (constructing the array, `map` to get lengths, `min`, `max`), none of which short-circuit, so it's likely slower than the solutions that only have 1-2 `O(n)` steps (one or more of which short-circuit). – ShadowRanger Oct 02 '18 at 21:19
1

@ShadowRanger I've never known anyone to differentiate O(n) algorithms like that but I suppose it makes sense. – tkiral Oct 02 '18 at 21:24
For CS theory purposes, they're all the same. The real world typically acknowledges the advantages in constant factor or short-circuiting though. It's why many sort APIs use hybrid sort strategies, e.g. Python's TimSort, which uses merge sort at the top level, but switches to insertion sort when the segments are small enough; insertion sort may be `O(n^2)` while merge sort is `O(n log n)`, but the constant factors matter. Similarly, TimSort includes a "galloping" mode that exploits pre-existing order; in theory, it's useless, but it can reduce work to `O(n)` in common cases. – ShadowRanger Oct 02 '18 at 21:38
Mind you, all sorts of weirdness affects the *real* performance; built-in functions can sometimes operate more efficiently than user defined functions, JIT-ing does all sorts of weird things to expected performance, etc. But all else being equal, you may as well reduce the constant factor if it doesn't cost you anything. A constant factor of 4 vs. 1 is the difference between taking 10 seconds and taking 40. In this case, it's likely premature optimization (can't see this test being the hottest code), but it's worth keeping in mind. – ShadowRanger Oct 02 '18 at 21:41

score 0 · Answer 4 · answered Oct 02 '18 at 21:16

As soon as you find one array with a different length than the first one, you know they're not all the same length. Otherwise you just have to check .length for every array to know for sure, so there isn't going to be anything faster than that.

function checkLengths() {
  var len = arguments[0].length;
  for(var i = 1; i < arguments.length; i++) {
    if(arguments[i].length != len) {
      return false;
    }
  }
  return true;
}

var arr1 = [0, 1, 2];
var arr2 = ['lala', 'ayy', 'whatup'];
var arr3 = ['what in the worlddddd'];

console.log('Same lengths:', checkLengths(arr1, arr2));
console.log('Same lengths:', checkLengths(arr1, arr2, arr3));

I wouldn't expect other answers to be significantly different...

What is the most efficient way to check if n arrays are the same length?

4 Answers4