Rotate array

First problem in “Cracking the Coding interview” tutorial on HackerRank is to rotate array to the left.

The solution is easy: calculate new index and copy-paste everything from original array to a newly created empty one that is then returned. We can even use System.arraycopy to speed up copy process.

But that requires O(n) extra memory. This problem could be solved with O(1) memory.

I already knew the solution (general approach, but not implementation) and it took me ~15 minutes to write algorithm down. However it was buggy and I wasn’t able to find the bug during test run.

After about 25 minutes debugging the problem was discovered.

Optimal solution is to pick number, remember its index and then repeat following n times:

  • Compute new index of picked number
  • Remember number at this new index
  • Set picked number at this new index
  • Set remembered number to picked number

It works but corner case exists where it fails. Namely if length of array is divisible by # of steps (k) (without remainder). In that case our replacements will go in loops never touching all elements. (Try to run this algorithm on 1234 with k=2).

There is a nice addition to steps described above that fixes that problem:

  • If we completed “replacement loop” (inserted number to index we started from) — increment index by 1

The only question remains is “how to detect that loop is completed?”. In my original version it was done with condition i % k == 0 which wasn’t correct: in 123456 and k = 2 we’ll do shift 3 times (when k == 0,2,4) while we need it 2 times (when k == 0,3). The correct condition is i % (arr.length / k).