Good DSA problem -ROTATE ARRAY

Check the git repo

Explanation of Code: Rotating an Array by d Elements (Counter-Clockwise)

The code provides a solution to rotate an array arr by d elements in a counter-clockwise direction using the reversal algorithm.

Code Walkthrough

class Solution {

    // Function to rotate an array by d elements in counter-clockwise direction.

    static void rotateArr(int arr[], int d) {

        int n = arr.length;



        // Edge case: If the array has only one element or no rotation needed

        if (n <= 1 || d <= 0) {

            return;

        }



        // Normalize d in case it's greater than or equal to array length

        d = d % n;



        // Step 1: Reverse the first d elements

        reverse(arr, 0, d - 1);



        // Step 2: Reverse the remaining elements

        reverse(arr, d, n - 1);



        // Step 3: Reverse the entire array

        reverse(arr, 0, n - 1);

    }



    // Helper function to reverse elements in the array

    private static void reverse(int arr[], int start, int end) {

        while (start < end) {

            // Swap elements at start and end

            int temp = arr[start];

            arr[start] = arr[end];

            arr[end] = temp;

            start++;

            end--;

        }

    }

}

Step-by-Step Explanation

1. Handle Edge Cases

• If the array length is 1 or less (n <= 1), or if no rotation is needed (d <= 0), the function exits early.


• No modifications are performed on such inputs.

2. Normalize the Rotation Count

• If d is greater than or equal to the array length (d >= n), rotating by d elements is equivalent to rotating by d % n.


• This ensures the rotation count remains within bounds.

3. Reverse Algorithm for Rotation

The reversal algorithm rotates the array in three steps:

1. 
   

   Reverse the first d elements

   
   
   
   
   
   • Example: For an array [1, 2, 3, 4, 5] and d = 2, reverse [1, 2] to get [2, 1, 3, 4, 5].
   
   
   
   


2. 
   

   Reverse the remaining n - d elements

   
   
   
   
   
   • Reverse [3, 4, 5] to get [2, 1, 5, 4, 3].
   
   
   
   


3. 
   

   Reverse the entire array

   
   
   
   
   
   • Reverse [2, 1, 5, 4, 3] to get [3, 4, 5, 1, 2].
   
   
   
   

4. Helper Function: reverse

• The reverse function swaps elements in the array between the specified start and end indices.


• It iteratively swaps elements until the pointers meet.

Complexity Analysis

1. 
   

   Time Complexity:

   
   
   
   
   
   • Reversing subsets of the array involves traversing all elements exactly once.
   
   
   • Total time complexity: O(n), where n is the length of the array.
   
   
   
   


2. 
   

   Space Complexity:

   
   
   
   
   
   • The algorithm uses constant extra space for swapping elements.
   
   
   • Space complexity: O(1).
   
   
   
   

Example Walkthrough

Input:

arr = [1, 2, 3, 4, 5]

d = 2

Execution:

1. Normalize d: d = 2 % 5 = 2
   


2. Reverse the first d elements: [1, 2] → [2, 1]
   
   
   
   
   • Array becomes: [2, 1, 3, 4, 5]
     
   
   
   
   


3. Reverse the remaining elements: [3, 4, 5] → [5, 4, 3]
   
   
   
   
   • Array becomes: [2, 1, 5, 4, 3]
     
   
   
   
   


4. Reverse the entire array: [2, 1, 5, 4, 3] → [3, 4, 5, 1, 2]
   

Output:

[3, 4, 5, 1, 2]

Advantages

• The reversal algorithm is efficient and does not require additional space.


• It provides a systematic approach to solving array rotation problems.