Java Program To Make A Circular Rotation Of An Array By K Positions Using The Loops

Rotating an array is a fundamental operation in computer science, often encountered in algorithms and data structures. In this article, you will learn how to perform a circular rotation of an array by k positions to the right using iterative loop-based approaches in Java.

Problem Statement

A circular array rotation by k positions means that elements are shifted to the right, and elements that 'fall off' the end wrap around to the beginning of the array. The challenge is to implement this efficiently using loops, without relying on built-in collection methods that abstract away the looping logic. This operation is critical in scenarios like processing data streams, image manipulation, or cryptography.

Example

Consider an array [1, 2, 3, 4, 5] and a rotation by k = 2 positions. The expected output after circular rotation would be [4, 5, 1, 2, 3].

Background & Knowledge Prerequisites

To understand and implement array rotation, readers should have a basic grasp of:

• Java Fundamentals: Variables, data types, and basic syntax.
• Arrays: How to declare, initialize, and access elements in a one-dimensional array.
• Loops: Familiarity with for loops for iteration.
• Modulo Operator (%): Understanding how it helps with wrapping around indices.

Use Cases or Case Studies

Array rotation finds application in various domains:

• Data Encryption: Simple forms of encryption or data scrambling can involve circular shifts of character arrays.
• Image Processing: Shifting pixels in an image grid can be achieved through array rotations for effects like scrolling or tiling.
• Game Development: Rotating game board states or character positions in a circular fashion.
• Data Stream Processing: When processing continuous data, a fixed-size window of data might need to shift, and older data elements might wrap around to become new inputs.
• Algorithm Optimization: In certain algorithms, rotating a data set can help optimize access patterns or reduce computation.

Solution Approaches

Here, we will explore two distinct loop-based approaches to perform circular array rotation.

Approach 1: Using a Temporary Array

This method involves creating a new temporary array to store the rotated elements, which is then copied back to the original array.

One-line summary: Store elements from the original array into a new temporary array at their rotated positions, then copy back.

// CircularArrayRotationTempArray
import java.util.Arrays;

// Main class containing the entry point of the program
public class Main {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        int k = 2; // Number of positions to rotate

        System.out.println("Original Array: " + Arrays.toString(arr));

        // Step 1: Handle edge cases for k
        // If k is greater than array length, reduce it using modulo
        k = k % arr.length;
        if (k < 0) { // Handle negative k by converting to equivalent positive rotation
            k = k + arr.length;
        }

        // Step 2: Create a temporary array to store rotated elements
        int[] temp = new int[arr.length];

        // Step 3: Copy elements to the temporary array at their new positions
        for (int i = 0; i < arr.length; i++) {
            // Calculate the new index: (current_index + k) % array_length
            // This ensures elements wrap around
            temp[(i + k) % arr.length] = arr[i];
        }

        // Step 4: Copy elements back from the temporary array to the original array
        for (int i = 0; i < arr.length; i++) {
            arr[i] = temp[i];
        }

        System.out.println("Rotated Array (Temp Array): " + Arrays.toString(arr));
    }
}

Run

Sample Output:

Original Array: [1, 2, 3, 4, 5]
Rotated Array (Temp Array): [4, 5, 1, 2, 3]

Stepwise Explanation:

1. Normalize k: The rotation amount k is normalized using the modulo operator (%) with the array length. This handles cases where k is larger than the array size, ensuring k is always within 0 to array.length - 1. Negative k values are adjusted to their equivalent positive rotation.
2. Create temp Array: An auxiliary array, temp, of the same size as the original array arr is created.
3. Populate temp: A for loop iterates through the original array arr. For each element arr[i], its new position in the rotated array is calculated as (i + k) % arr.length. The element is then placed at this new index in the temp array. The modulo operator ensures that if i + k exceeds the array bounds, the index wraps around to the beginning.
4. Copy Back: Finally, another for loop copies all elements from the temp array back into the original arr, completing the rotation.

Approach 2: Rotating One Element at a Time (Repeated Shifts)

This approach performs the rotation by repeatedly shifting each element one position to the right, k times.

One-line summary: Shift all elements one position to the right, moving the last element to the first, and repeat this k times.

// CircularArrayRotationOneByOne
import java.util.Arrays;

// Main class containing the entry point of the program
public class Main {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        int k = 2; // Number of positions to rotate

        System.out.println("Original Array: " + Arrays.toString(arr));

        // Step 1: Handle edge cases for k
        k = k % arr.length;
        if (k < 0) {
            k = k + arr.length;
        }

        // Step 2: Perform k rotations
        for (int i = 0; i < k; i++) {
            int lastElement = arr[arr.length - 1]; // Store the last element

            // Shift all elements from right to left by one position
            for (int j = arr.length - 1; j > 0; j--) {
                arr[j] = arr[j - 1];
            }
            
            arr[0] = lastElement; // Place the stored last element at the beginning
        }

        System.out.println("Rotated Array (One by One): " + Arrays.toString(arr));
    }
}

Run

Sample Output:

Original Array: [1, 2, 3, 4, 5]
Rotated Array (One by One): [4, 5, 1, 2, 3]

Stepwise Explanation:

1. Normalize k: Similar to the previous approach, k is normalized to ensure it's within the valid range and positive.
2. Outer Loop (k times): An outer for loop runs k times, as each iteration performs one single-position rotation.
3. Store Last Element: Inside the outer loop, the last element of the array (arr[arr.length - 1]) is temporarily stored in a variable lastElement. This element will eventually wrap around to the front.
4. Inner Loop (Shift): An inner for loop iterates from the second-to-last element down to the first element (arr.length - 1 down to 1). In each step, arr[j] is assigned the value of arr[j - 1], effectively shifting every element one position to the right.
5. Place lastElement: After all elements have been shifted, the stored lastElement is placed at the very beginning of the array (arr[0]).
6. This process repeats k times, resulting in the complete rotation.

Conclusion

Both discussed loop-based approaches successfully perform circular array rotation in Java. The temporary array method is generally more efficient for larger arrays and k values, as it involves two passes over the array regardless of k. The one-by-one rotation method, while intuitive, can be less performant for large k values due to its nested loop structure, resulting in k * N operations where N is the array length. Choosing between them depends on the specific performance requirements and the nature of the input data.

Summary

• Circular array rotation shifts elements to the right, wrapping elements from the end to the beginning.
• Normalize k using the modulo operator to handle k values larger than the array length.
• Temporary Array Approach: Uses an auxiliary array to store elements at their final rotated positions, then copies back. This is often more efficient.
• One-by-One Rotation Approach: Shifts elements one position to the right, k times. This can be less efficient for large k.
• Both methods rely purely on loops, providing a fundamental understanding of array manipulation.