Write a program to cyclically rotate an array by one

Problem Statement

Given an array, cyclically rotate the array clockwise by one position. The last element becomes the first element, and all other elements shift to the right.

Example:

• Input: [1, 2, 3, 4, 5]
• Output: [5, 1, 2, 3, 4]
• Explanation: Last element 5 moves to front, others shift right

Approach 1: Using Extra Array (Brute Force)

Intuition

Create a new array where the first element is the last element of original array, and remaining elements are shifted by one position.

Algorithm

1. Create a new array of same size
2. Place last element at index 0
3. Copy remaining elements shifted by one position

public class Solution {
    public int[] rotateByOne(int[] arr) {
        int n = arr.length;
        if (n <= 1) return arr;
        
        int[] result = new int[n];
        
        // Place last element at first position
        result[0] = arr[n - 1];
        
        // Shift remaining elements
        for (int i = 1; i < n; i++) {
            result[i] = arr[i - 1];
        }
        
        return result;
    }
}

Complexity Analysis

• Time Complexity: O(n) - Single traversal
• Space Complexity: O(n) - Extra array of size n

Approach 2: In-Place Rotation (Optimal)

Intuition

Store the last element, shift all elements to the right by one position, then place the stored element at the beginning.

Algorithm

1. Store the last element in a temporary variable
2. Shift all elements to right by one position (from end to start)
3. Place the stored element at index 0

public class Solution {
    public void rotateByOne(int[] arr) {
        int n = arr.length;
        if (n <= 1) return;
        
        // Store last element
        int last = arr[n - 1];
        
        // Shift elements to right
        for (int i = n - 1; i > 0; i--) {
            arr[i] = arr[i - 1];
        }
        
        // Place last element at first position
        arr[0] = last;
    }
}

Dry Run Example

Complexity Analysis

• Time Complexity: O(n) - Single traversal
• Space Complexity: O(1) - Only one extra variable

Approach 3: Using Swap Operations

Intuition

Swap the last element with every previous element, effectively moving it to the front.

public class Solution {
    public void rotateByOne(int[] arr) {
        int n = arr.length;
        if (n <= 1) return;
        
        // Swap last element with each previous element
        for (int i = n - 1; i > 0; i--) {
            int temp = arr[i];
            arr[i] = arr[i - 1];
            arr[i - 1] = temp;
        }
    }
}

Complexity Analysis

• Time Complexity: O(n) - n-1 swaps
• Space Complexity: O(1) - In-place

Extension: Rotate by K Positions

If you need to rotate by K positions, use the reversal algorithm:

public class Solution {
    public void rotateByK(int[] arr, int k) {
        int n = arr.length;
        if (n == 0) return;
        
        k = k % n;
        if (k == 0) return;
        
        reverse(arr, n - k, n - 1);
        reverse(arr, 0, n - k - 1);
        reverse(arr, 0, n - 1);
    }
    
    private void reverse(int[] arr, int start, int end) {
        while (start < end) {
            int temp = arr[start];
            arr[start] = arr[end];
            arr[end] = temp;
            start++;
            end--;
        }
    }
}

Key Takeaways

1. In-place rotation requires only O(1) extra space
2. Shifting elements from the end to start avoids overwriting
3. The swap approach is intuitive but does more operations
4. For K rotations, use the reversal algorithm for O(n) time
5. Always handle edge cases: empty array, single element, k > n
6. Cyclic rotation is a common operation in circular queues and scheduling algorithms