Checking if an array can be rotated to equal another in JavaScript

Question

I needed to write a function in JavaScript which checks if any rotation of an array is equal to another array.

By rotation, I mean:

rotate [1, 2, 3] --> [3, 1, 2]
rotate [3, 1, 2] --> [2, 3, 1]
rotate [2, 3, 1] --> [1, 2, 3]

Here's the code for my function. It feels pretty verbose, especially since the array functions added by ES6 seem perfect for this sort of thing, yet I've used very few of them. In particular, using a label on the outer loop feels wrong.

Is there any way I can make this function shorter and/or faster?

/**
 * Taking two arrays, checks whether one may be rotated so that it equals
 * the other.
 */
function arraysEqualByRotation(first, second) {
  if (first.length !== second.length) {
    return false;
  }

  // We'll rotate the first continually and compare it to the second
  var rotatedFirst = first.slice(0);

  outer:
  for (var rotateCounter = 0; rotateCounter < rotatedFirst.length; rotateCounter++) {
    // Rotate the array
    rotatedFirst.unshift(rotatedFirst.pop());

    // Check if their elements are equal
    for (var i = 0; i < rotatedFirst.length; i++) {
      if (rotatedFirst[i] !== second[i]) {
        // Try another rotation
        continue outer;
      }
    }

    // At this stage, they're equal
    return true;
  }

  // At this stage, a matching combination was never found
  return false;
}

Example inputs and outputs:

first      | second     | result
-----------------------------------------------
[1, 2, 3]  | [1, 2, 3]  | true (same array)
[1, 2, 3]  | [3, 1, 2]  | true (rotate once)
[1, 2, 3]  | [2, 3, 1]  | true (rotate twice)
[1, 2]     | [1, 2, 3]  | false (different lengths)
[1, 2, 3]  | [1, 3, 2]  | false (no valid rotation)

Answer 1

I have not looked too deeply into the problem and I am guessing that there may be some function that produces a unique hash based on the sequence and independent of starting position. That would then only require that you iterate each array to create the hash and then compare to see if they match. That would give you a O(2n) solution where n is the size of one of the arrays.

If such hashing function does not exist, the brute force approch can easily be divided up and done in parallel. In javascript you would use webWorkers

There is also the approch that can use the GPU and the basic canvas 2D API but that has some limits on the size of the input arrays and the integer size of the values. Or via WebGL which is a little more flexible, but again the bottle neck is converting the arrays to an appropriate data format that the GPU can handle. The are some libraries out there that simplify the process, but you would only start to see any gains for very large arrays.

So to make some minor changes to your solution. To remove the pop and unshift you can use the % operator to cycle past the end back to the start (see inner loop)

And the using continue to jump out of the loops is hacky to say the least. A little smarter logic and you don't need the goto in disguise.

So the function below is not an improvement in complexity, but rather a improvement of efficiency.

function canRotate(a, b) {
    var pos, count;
    const len = a.length;
    if (len === b.length) { 
        pos = 0;
        while (pos < len) {
            count = 0;
            while (count < len && a[count] === b[(pos + count) % len]) {
                count ++;
            }
            if (count === len) { return true }
            pos ++;
        }
    }
    return false;
}

You could also use a regExp to do the search but again its not an improvement in complexity, just less code, and may be a lot faster in many situations (however the joins may need a separator to work on all cases)

Just join the second array and double it by add to its self, then join the first and convert to a regExp (or use String.API ) to test if the first array has a match in the second.

function canRotate(a,b){
    if(a.length === b.length) { 
        const strB = b.join("");
        return new RegExp(a.join(""),"").test(strB+strB);
    }
    return false;
}

Or using a asymmetrical separator ie has two different characters.

function canRotate(a,b){
    if(a.length === b.length) {
        const jStr = "=>"; 
        const strB = b.join(jStr);
        return new RegExp(a.join(jStr),"").test(strB + jStr + strB);
    }
    return false;
}

Update This answer assumes that the arrays contains positive values of the JS 32bit signed int.

Obliviously you should take care with the regExp solutions and only use it if array content can be joined without breaking the sequence uniqueness, and does not contain regExp tokens.

Answer 2

I'm afraid I don't know enough Javascript to give a meaningful review on the language specific things.

The algorithm seems sensible.

One observation is that if two lists are not anagrams of each other, they are not rotations of each other. The complexity of a sort based anagram check is \$ O(n log(n)) \$ and that of a histogram based check is \$ O(n+b) \$ (where b is the number of distinct elements in the array). That is compared with the worst case complexity here of \$ O(n^2) \$ That means, much like you have an early sanity check against the length, you might benefit from doing a standard anagram check before getting into the full rotated list check. This entirely depends on your data source: it is not worth doing if all your inputs are anagrams for example.

---

I also thought I'd offer a bit of elaboration on Blindman67's suggestions.

One key thing to think about performance wise is what you do to arrays. As a rule of thumb for almost all languages, the fastest container data structure is often a simple contiguous array, because it's quick and easy to find and update an element in it. However, arrays are particularly bad at dealing with cases where data gets shuffled about. This is because, if you insert or delete something, every element later in the array needs to be shuffled forward or backwards. While it's always better to make judgements about efficiency with the help of a profiler, the line that reads as probably slowest by a long way here is rotatedFirst.unshift(rotatedFirst.pop()); That's why it would be faster to use % and just index into the original array in the location you'd be looking if it had been rotated.

Second, his comment about regExp doesn't actually work. Directly collapsing an array to a string is always messy. He mentions that "the joins may need a separator to work on all cases" because it falls apart with, say, [12, 3] being reported as a rotation of [1,23]. However it's not possible in general to pick a separator that cannot appear in the string representation of any data type that could be in your arrays. Nevertheless if you want to look at more advanced optimisations, it may be helpful to observe that "m is an array rotation of n" is equivalent to "m is a substring of n+n". As such, it may be worth looking at substring search algorithms for insights. Just apply them to arrays instead of strings. (Do note, however, that most research into that area has assumed the string being searched is very long compared to the string being looked for, so what works best for typical search may not work for your particular search problem.)

Answer 3

I don't know a lot of JavaScript, but I'll explain how to solve this problem in general using any programming language in O(n) time, where n is the number of elements in any of the input arrays. Of course, if the arrays are of different sizes, then they are not a rotation of one another.

The key observation is, array B is a rotation of array A, if B is a subarray of the A concatenated with itself. For example, A = [5, 3, 4] and B = [3, 4, 5]. Observe that B is a subarray of A' = [5, 3, 4, 5, 3, 4].

However, you don't literally need to double array A. Instead, wrap around once you fall off the end of A, and keep going. This gives the following algorithm:

IS-ROTATION(A, B)
  m = A.length
  n = B.length

  if m ≠ n; then
    return false
  endif

  i = j = 0

  while i < 2m && j < n; do
    if i >= m; then
      if j > 0 && A[i % m] == B[j]; then
        j++
      else
        return false
      endif
    else if A[i] == B[j]; then
      j++
    else
      j = 0
    endif
    i++
  done

  return j >= n