# 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)`

.