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.