Left And Right Rotation Of Array In Java Program

Array rotation is a fundamental operation in computer science, used to efficiently rearrange elements within an array. In this article, you will learn different methods to perform left and right array rotations in Java, understanding their implementation and various use cases.

Problem Statement

An array rotation involves shifting elements of an array by a specified number of positions, either to the left or to the right. The elements that move beyond the array boundaries are reinserted at the opposite end, maintaining a circular order.

For example:

• Original Array: [1, 2, 3, 4, 5]
• Left Rotation by 2: [3, 4, 5, 1, 2] (elements 1 and 2 move to the end)
• Right Rotation by 2: [4, 5, 1, 2, 3] (elements 4 and 5 move to the beginning)

This operation is crucial in algorithms dealing with cyclic data structures, queue implementations, and various data manipulation tasks.

Example

Consider an array [10, 20, 30, 40, 50] and a rotation count k = 2.

• Original Array: [10, 20, 30, 40, 50]
• Left Rotation by 2: The first two elements (10, 20) move to the end of the array. The array becomes [30, 40, 50, 10, 20].
• Right Rotation by 2: The last two elements (40, 50) move to the beginning of the array. The array becomes [40, 50, 10, 20, 30].

Background & Knowledge Prerequisites

To effectively follow the array rotation examples and explanations in Java, you should have a basic understanding of:

• Basic Java Syntax: Familiarity with declaring variables, data types (like int[]), and calling methods.
• Arrays in Java: How to declare, initialize, and access elements of an array using indices.
• Loops: Knowledge of for loops for iterating through array elements is essential.

Use Cases or Case Studies

Array rotation, while seemingly simple, is a building block for more complex algorithms and data structures. Here are a few practical examples:

• Cryptography: Simple substitution ciphers or permutation-based algorithms might use array rotation to scramble or descramble character arrays.
• Image Processing: Rotating image pixel data, which is often stored in 2D arrays, can involve array rotation operations on rows or columns.
• Game Development: In grid-based games, rotating elements or patterns on the game board (e.g., Tetris blocks, puzzle pieces) can be implemented using array rotations.
• Data Streaming and Circular Buffers: When processing continuous data streams with a fixed-size buffer, older data might need to be "rotated out" as newer data "rotates in," forming a circular queue.
• Algorithmic Puzzles: Many coding challenges and interview questions involve array rotation as a core component or a sub-problem.

Solution Approaches

We will explore several common approaches to perform array rotations, detailing both left and right rotations.

Approach 1: Left Rotation Using a Temporary Array

This approach involves storing the first d elements in a temporary array, shifting the remaining n-d elements to the left, and then placing the temporary elements at the end of the array.

// Left Array Rotation using Temporary Array
import java.util.Arrays; // Required for Arrays.toString()

// Main class containing the entry point of the program
public class Main {
    /**
     * Performs a left rotation on an array by 'd' positions.
     *
     * @param arr The array to be rotated.
     * @param d The number of positions to rotate left.
     */
    static void leftRotate(int[] arr, int d) {
        // Handle edge cases: null array or empty array
        if (arr == null || arr.length == 0) {
            return;
        }
        int n = arr.length;
        // Adjust d to be within array bounds (in case d >= n)
        // A rotation by n is equivalent to no rotation.
        d = d % n;

        // Step 1: Create a temporary array to store the first d elements
        int[] temp = new int[d];
        for (int i = 0; i < d; i++) {
            temp[i] = arr[i];
        }

        // Step 2: Shift the remaining elements (from index d to n-1) to the left
        // These elements move to positions (i - d)
        for (int i = d; i < n; i++) {
            arr[i - d] = arr[i];
        }

        // Step 3: Copy the elements from the temporary array to the end of the original array
        // These elements go into positions (n - d + i)
        for (int i = 0; i < d; i++) {
            arr[n - d + i] = temp[i];
        }
    }

    public static void main(String[] args) {
        // Example 1
        int[] arr1 = {1, 2, 3, 4, 5, 6, 7};
        int d1 = 2; // Number of positions to rotate left

        System.out.println("Original Array: " + Arrays.toString(arr1));
        leftRotate(arr1, d1); // Perform left rotation
        System.out.println("Array after " + d1 + " left rotations: " + Arrays.toString(arr1));

        System.out.println("-------------------------------------");

        // Example 2
        int[] arr2 = {10, 20, 30, 40, 50};
        int d2 = 3;
        System.out.println("Original Array: " + Arrays.toString(arr2));
        leftRotate(arr2, d2);
        System.out.println("Array after " + d2 + " left rotations: " + Arrays.toString(arr2));
    }
}

Run

Original Array: [1, 2, 3, 4, 5, 6, 7]
Array after 2 left rotations: [3, 4, 5, 6, 7, 1, 2]
-------------------------------------
Original Array: [10, 20, 30, 40, 50]
Array after 3 left rotations: [40, 50, 10, 20, 30]

Explanation:

1. Handle d: The rotation amount d is first adjusted using the modulo operator (d = d % n). This ensures that if d is greater than or equal to the array length (n), we only perform the effective number of rotations (e.g., rotating an array of 5 elements by 5 positions is the same as 0 rotations).
2. Store first d elements: A new temporary array temp of size d is created. The first d elements from the original arr are copied into temp.
3. Shift remaining elements: Elements from index d up to n-1 are shifted d positions to the left. For instance, arr[d] moves to arr[0], arr[d+1] to arr[1], and so on.
4. Copy back from temp: Finally, the elements stored in temp (the original first d elements) are copied back into the last d positions of the arr array.

Approach 2: Left Rotation One-by-One

This method involves repeatedly shifting each element by one position for d times. While simpler to conceptualize, it is generally less efficient for large arrays and many rotations.

// Left Array Rotation One-by-One
import java.util.Arrays;

// Main class containing the entry point of the program
public class Main {
    /**
     * Performs a single left rotation on the array.
     * The first element moves to the end, and all others shift left.
     *
     * @param arr The array to be rotated.
     */
    static void rotateOneElementLeft(int[] arr) {
        // Handle edge cases: null array or array with 0 or 1 element
        if (arr == null || arr.length <= 1) {
            return;
        }
        int first = arr[0]; // Step 1: Store the first element
        // Step 2: Shift remaining elements to the left by one position
        for (int i = 0; i < arr.length - 1; i++) {
            arr[i] = arr[i + 1];
        }
        arr[arr.length - 1] = first; // Step 3: Place the stored first element at the end
    }

    /**
     * Performs 'd' left rotations on an array using the one-by-one method.
     *
     * @param arr The array to be rotated.
     * @param d The number of positions to rotate left.
     */
    static void leftRotateOneByOne(int[] arr, int d) {
        if (arr == null || arr.length == 0) {
            return;
        }
        // Adjust d
        d = d % arr.length;
        for (int i = 0; i < d; i++) {
            rotateOneElementLeft(arr); // Rotate by one element, d times
        }
    }

    public static void main(String[] args) {
        // Example 1
        int[] arr1 = {1, 2, 3, 4, 5};
        int d1 = 2; // Number of positions to rotate left

        System.out.println("Original Array: " + Arrays.toString(arr1));
        leftRotateOneByOne(arr1, d1);
        System.out.println("Array after " + d1 + " left rotations (one-by-one): " + Arrays.toString(arr1));

        System.out.println("-------------------------------------");

        // Example 2
        int[] arr2 = {100, 200, 300, 400, 500, 600};
        int d2 = 4;
        System.out.println("Original Array: " + Arrays.toString(arr2));
        leftRotateOneByOne(arr2, d2);
        System.out.println("Array after " + d2 + " left rotations (one-by-one): " + Arrays.toString(arr2));
    }
}

Run

Original Array: [1, 2, 3, 4, 5]
Array after 2 left rotations (one-by-one): [3, 4, 5, 1, 2]
-------------------------------------
Original Array: [100, 200, 300, 400, 500, 600]
Array after 4 left rotations (one-by-one): [500, 600, 100, 200, 300, 400]

Explanation:

1. rotateOneElementLeft method: This helper method performs a single left rotation. It saves the value of arr[0], then shifts every element arr[i+1] to arr[i], effectively moving all elements one position to the left. Finally, the saved arr[0] is placed at arr[n-1].
2. leftRotateOneByOne method: This main method simply calls rotateOneElementLeft d times. This repeats the single-element shift d times to achieve the desired total number of left rotations.

Approach 3: Right Rotation Using a Temporary Array

This approach is analogous to left rotation with a temporary array but operates in the opposite direction. It stores the last d elements in a temporary array, shifts the remaining n-d elements to the right, and then places the temporary elements at the beginning of the array.

// Right Array Rotation using Temporary Array
import java.util.Arrays;

// Main class containing the entry point of the program
public class Main {
    /**
     * Performs a right rotation on an array by 'd' positions.
     *
     * @param arr The array to be rotated.
     * @param d The number of positions to rotate right.
     */
    static void rightRotate(int[] arr, int d) {
        // Handle edge cases: null array or empty array
        if (arr == null || arr.length == 0) {
            return;
        }
        int n = arr.length;
        // Adjust d to be within array bounds
        d = d % n;

        // Step 1: Create a temporary array to store the last d elements
        int[] temp = new int[d];
        for (int i = 0; i < d; i++) {
            // Copy elements from (n - d) to (n - 1) into temp
            temp[i] = arr[n - d + i];
        }

        // Step 2: Shift the remaining elements (from 0 to n-d-1) to the right
        // These elements move to positions (i + d). Loop backwards to avoid overwriting elements
        // before they are moved.
        for (int i = n - d - 1; i >= 0; i--) {
            arr[i + d] = arr[i];
        }

        // Step 3: Copy the elements from the temporary array to the beginning of the original array
        for (int i = 0; i < d; i++) {
            arr[i] = temp[i];
        }
    }

    public static void main(String[] args) {
        // Example 1
        int[] arr1 = {1, 2, 3, 4, 5, 6, 7};
        int d1 = 2; // Number of positions to rotate right

        System.out.println("Original Array: " + Arrays.toString(arr1));
        rightRotate(arr1, d1); // Perform right rotation
        System.out.println("Array after " + d1 + " right rotations: " + Arrays.toString(arr1));

        System.out.println("-------------------------------------");

        // Example 2
        int[] arr2 = {10, 20, 30, 40, 50};
        int d2 = 3;
        System.out.println("Original Array: " + Arrays.toString(arr2));
        rightRotate(arr2, d2);
        System.out.println("Array after " + d2 + " right rotations: " + Arrays.toString(arr2));
    }
}

Run

Original Array: [1, 2, 3, 4, 5, 6, 7]
Array after 2 right rotations: [6, 7, 1, 2, 3, 4, 5]
-------------------------------------
Original Array: [10, 20, 30, 40, 50]
Array after 3 right rotations: [30, 40, 50, 10, 20]

Explanation:

1. Handle d: Similar to left rotation, d is adjusted by d % n.
2. Store last d elements: A temporary array temp of size d is created. The last d elements of arr (from index n - d to n - 1) are copied into temp.
3. Shift remaining elements: Elements from index 0 up to n - d - 1 are shifted d positions to the right. To avoid overwriting elements prematurely, this loop must iterate backward, from n - d - 1 down to 0. For example, arr[n-d-1] moves to arr[n-1].
4. Copy back from temp: The elements from temp (the original last d elements) are then copied into the first d positions of the arr array.

Approach 4: Right Rotation One-by-One

This method is the right-rotation equivalent of the one-by-one left rotation. It repeatedly shifts each element by one position to the right for d times.

// Right Array Rotation One-by-One
import java.util.Arrays;

// Main class containing the entry point of the program
public class Main {
    /**
     * Performs a single right rotation on the array.
     * The last element moves to the beginning, and all others shift right.
     *
     * @param arr The array to be rotated.
     */
    static void rotateOneElementRight(int[] arr) {
        // Handle edge cases: null array or array with 0 or 1 element
        if (arr == null || arr.length <= 1) {
            return;
        }
        int last = arr[arr.length - 1]; // Step 1: Store the last element
        // Step 2: Shift remaining elements to the right by one position
        // Loop backwards from (n-1) down to 1.
        for (int i = arr.length - 1; i > 0; i--) {
            arr[i] = arr[i - 1];
        }
        arr[0] = last; // Step 3: Place the stored last element at the beginning
    }

    /**
     * Performs 'd' right rotations on an array using the one-by-one method.
     *
     * @param arr The array to be rotated.
     * @param d The number of positions to rotate right.
     */
    static void rightRotateOneByOne(int[] arr, int d) {
        if (arr == null || arr.length == 0) {
            return;
        }
        // Adjust d
        d = d % arr.length;
        for (int i = 0; i < d; i++) {
            rotateOneElementRight(arr); // Rotate by one element, d times
        }
    }

    public static void main(String[] args) {
        // Example 1
        int[] arr1 = {1, 2, 3, 4, 5};
        int d1 = 2; // Number of positions to rotate right

        System.out.println("Original Array: " + Arrays.toString(arr1));
        rightRotateOneByOne(arr1, d1);
        System.out.println("Array after " + d1 + " right rotations (one-by-one): " + Arrays.toString(arr1));

        System.out.println("-------------------------------------");

        // Example 2
        int[] arr2 = {100, 200, 300, 400, 500, 600};
        int d2 = 4;
        System.out.println("Original Array: " + Arrays.toString(arr2));
        rightRotateOneByOne(arr2, d2);
        System.out.println("Array after " + d2 + " right rotations (one-by-one): " + Arrays.toString(arr2));
    }
}

Run

Original Array: [1, 2, 3, 4, 5]
Array after 2 right rotations (one-by-one): [4, 5, 1, 2, 3]
-------------------------------------
Original Array: [100, 200, 300, 400, 500, 600]
Array after 4 right rotations (one-by-one): [300, 400, 500, 600, 100, 200]

Explanation:

1. rotateOneElementRight method: This helper method performs a single right rotation. It saves the value of arr[n-1], then shifts every element arr[i-1] to arr[i], effectively moving all elements one position to the right. This loop must iterate backward from arr.length - 1 down to 1. Finally, the saved arr[n-1] is placed at arr[0].
2. rightRotateOneByOne method: This main method simply calls rotateOneElementRight d times, achieving the total d right rotations.

Conclusion

Array rotation is a foundational concept in programming with various practical applications. We've explored common methods for both left and right array rotations in Java. The temporary array approach typically offers a good balance in terms of time and space complexity, making it efficient for most scenarios. The one-by-one rotation is simpler to implement but generally less efficient, especially for larger arrays or a high number of rotations. Choosing the right method depends on specific requirements, including performance needs and code readability. Understanding these basic techniques forms a strong basis for tackling more complex data manipulation challenges.

Summary

• Array rotation shifts elements by a specified number of positions, either to the left or right, with elements wrapping around.
• Left rotation moves the initial d elements to the end of the array.
• Right rotation moves the final d elements to the beginning of the array.
• Temporary Array Approach:
• Mechanism: Uses an auxiliary array to temporarily store elements, then shifts the rest, and finally copies back the stored elements.
• Time Complexity: O(N), as it involves a constant number of passes over the array.
• Space Complexity: O(d), as it uses a temporary array of size d.
• One-by-One Rotation Approach:
• Mechanism: Performs d single-element rotations, where each rotation shifts all elements by one position.
• Time Complexity: O(N * d), as each of the d rotations takes O(N) time. This can be inefficient for large d.
• Space Complexity: O(1), as it uses only a few extra variables, not dependent on d or N.
• Always ensure the rotation count d is adjusted by d % n to handle cases where d is greater than or equal to the array length n.