Juggling/Dolphin’s algorithm is a technique used for array rotation, which is the process of shifting the elements of an array to the left or right by a certain number of positions. This algorithm is efficient and is particularly useful in situations where you need to perform frequent array rotations in-place without using any extra space. You may refer to this article to understand more about what array rotation means.
Array Rotation
Consider an array containing the following elements:
[1, 2, 3, 4, 5]
After rotating the elements by one position towards right, the array becomes:
[5, 1, 2, 3, 4]
Notice that all the elements moved by one position towards right. Also, the last element 5 wrapped around and moved to the starting of the array.
Similarly, after rotating the elements by one position towards right, the array becomes:
[4, 5, 1, 2, 3]
And so on..
Juggling/Dolphin’s Algorithm to Rotate Array
By now, you must have understood what an array rotation is and how positions of elements in an array are shifted. Let’s now take a look at the code to rotate an array by d positions towards right using Juggling/Dolphin’s algorithm:
Time Complexity:
The time complexity of the Juggling algorithm is O(n), where n is the length of the array. This is because the algorithm performs a series of swaps where each swap takes constant time, and the total number of swaps made is equal to the total number of elements present in the array.
Space Complexity:
The space complexity of the Juggling algorithm is O(1), which means it uses a constant amount of additional space. This is because the algorithm performs the rotations in-place, without requiring any additional data structures.
Idea behind the Algorithm
Let’s start with a simple scenario where we need to rotate the array: [1, 2, 3, 4, 5] by 3 positions to the right. Below is how the array looks after each rotation towards right:
[1, 2, 3, 4, 5] # Initial Array
[5, 1, 2, 3, 4] # After 1st rotation
[4, 5, 1, 2, 3] # After 2nd rotation
[3, 4, 5, 1, 2] # After 3rd rotation
If you observe closely,
- The index of number
1is0before rotation. After 3rd rotation, the index of number1is3. - Similarly the index of number
2is1before rotation. After 3rd rotation, the index of number2is4 - So we can generalize this as follows: If the index of an element is
ibefore rotation, it’s position after rotatingdpositions towards right isi+d - So far so good, but for number
3, the index before rotation is2. But after3rotations, the new index has to be “initial index + number of positions rotated” which is2 + 3=5 - But since the last index of the array is
4, we need to wrap this index and start again from the beginning. So you need to think of index5as the element after index4which is index0due to wrapping. - Mathematically, this can be computed as:
new_index = (old_index + positions_rotated) % array_len- For example, the old index of number
5is4. The new index after rotating3positions to the right will be(4 + 3)%5which is2.
The key idea behind Juggling/Dolphin’s algorithm is to start at the first element at index i and move it to i+d position. Now move the element originally present at i+d position to (i+d)+d position. We keep repeating this until we reach the first element. You can think of all elements covered in this loop to belong to a unique set.
In cases where the GCD of the length of the array and the number of rotations is 1 (i.e, there is no common divisor other than 1), there is only one set, and just one pass of the above algorithm is sufficient to rotate all elements. For example, in the below illustration with an array of 8 elements and 3 position rotation, we have only one cycle with sequence: 1 -> 4 -> 7 -> 2 -> 5 -> 8 -> 3 -> 6 -> 1. Juggling and rotating all elements in this sequence starting from element 1 will result in a rotated array.
But in cases where the GCD is more than 1, there are more than 1 sets/cycles and so we need to iterate through each set/cycle and rotate all elements present in each set/cycle. For example, in the below illustration with an array of 8 elements 2 position rotation, we have two cycles, one with sequence: 1 -> 3 -> 5 -> 7 -> 1 and the other with sequence 2 -> 4 -> 6 -> 8 -> 2. Juggling and rotating all elements present in both these cycles will result in a complete rotated array.
In the Juggling/Dolphin’s algorithm we went through, the first loop loops through the starting index of each set/cycle and the second loop rotates all elements present in that particular set.