Welcome to array rotation! Array rotation is a fundamental operation where we shift elements in an array to the left or right by a specified number of positions. In left rotation, elements move left and the first elements wrap around to the end. For example, if we rotate the array one, two, three, four, five left by two positions, we get three, four, five, one, two.
The first method for array rotation uses a temporary array. This approach creates a new array and copies elements to their rotated positions. The steps are: first, create a temporary array of the same size. Second, copy each element to its new position in the temporary array. Finally, copy all elements back to the original array. This method has linear time complexity but requires extra space.
The reversal algorithm is an elegant space-efficient method. For left rotation by k positions, we perform three reversal operations. First, reverse the first k elements. Second, reverse the remaining elements. Finally, reverse the entire array. This gives us the rotated result using only constant extra space. The algorithm works by strategically repositioning elements through reversals.
The juggling algorithm is the most efficient method for array rotation. It works by moving elements in cycles based on the greatest common divisor of array length and rotation count. Elements are moved directly to their final positions in cycles. For an array of six elements rotated by two, we have two cycles: one cycle moves elements at positions zero, two, and four, while another cycle moves elements at positions one, three, and five.
To summarize array rotation: We explored three fundamental methods. The temporary array approach is straightforward but requires extra memory. The reversal algorithm efficiently uses constant space through strategic reversals. The juggling algorithm is most optimal, moving elements directly in cycles. All methods achieve linear time complexity, but differ in space usage and implementation complexity.