Rotate Array

Given an unsorted array arr[]. Rotate the array to the left (counter-clockwise direction) byd steps, where d is a positive integer. Do the mentioned change in the array in place.

Note:Consider the array as circular.

Examples :

Input: arr[] = [1, 2, 3, 4, 5], d = 2
Output: [3, 4, 5, 1, 2]
Explanation: when rotated by 2 elements, it becomes 3 4 5 1 2.

Input: arr[] = [2, 4, 6, 8, 10, 12, 14, 16, 18, 20], d = 3
Output: [8, 10, 12, 14, 16, 18, 20, 2, 4, 6]
Explanation: when rotated by 3 elements, it becomes 8 10 12 14 16 18 20 2 4 6.

Input: arr[] = [7, 3, 9, 1], d = 9
Output: [3, 9, 1, 7]
Explanation: when we rotate 9 times, we'll get 3 9 1 7 as resultant array.

Constraints:
1 <= arr.size(), d <= 10⁵
0 <= arr[i] <= 10⁵

Approach 01:

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    // Function to rotate an array by d elements in counter-clockwise direction.
    void rotateArr(vector<int>& arr, int d) {
        int n = arr.size();
        d = d % n; // Handle cases where d > n

        // Rotate using slicing logic
        reverse(arr.begin(), arr.begin() + d);
        reverse(arr.begin() + d, arr.end());
        reverse(arr.begin(), arr.end());
    }
};

class Solution:
    # Function to rotate an array by d elements in counter-clockwise direction.
    def rotateArr(self, arr, d):
        n = len(arr)
        d = d % n  # Handle cases where d > n
        arr[:] = arr[d:] + arr[:d]  # Rotate using slicing

Time Complexity

• Calculating d % n:

  This operation takes constant time \( O(1) \).

• Using the reverse Function:

  The function uses the reverse method three times:

  • First, reversing the first d elements takes \( O(d) \) time.
  • Second, reversing the remaining elements takes \( O(n – d) \) time.
  • Finally, reversing the entire array takes \( O(n) \) time.
• Overall Time Complexity:

  The overall time complexity is \( O(n) \) since each element is visited a constant number of times.

Space Complexity

• In-place Rotation:

  The algorithm uses the reverse function which operates in-place, so no additional space is needed.

• Auxiliary Variables:

  Only a few variables like n and d are used, which take constant space \( O(1) \).

• Overall Space Complexity:

  The overall space complexity is \( O(1) \).