Rotating an Array

Problem

Given an array of size n. The task is to rotate array by d elements where d ≤ n.

Examples:

Example 1:

Input:
n = 7
arr[] = {-1, -2, -3, 4, 5, 6, 7}
d = 2
Output: {-3, 4, 5, 6, 7, -1, -2}
Explanation: 
Rotate by 1: [-2, -3, 4, 5, 6, 7, -1]
Rotate by 2: [-3, 4, 5, 6, 7, -1, -2]

Example 2:

Input:
n = 4
arr[] = {1, 3, 4, 2}
d = 3
Output: {2, 1, 3, 4}

Your task:

You don't need to read input or print anything. Your task is to complete the function leftRotate() which takes the array of integers arr[], its size n and d as input parameters and rotates arr[] in-place without using any extra memory.

• Expected Time Complexity: $O(n)$
• Expected Auxiliary Space: $O(1)$

Constraints:

• $1 ≤ n ≤ 10^6$
• $-10^9 ≤ arr[i] ≤ 10^9$
• $0 ≤ d ≤ n$

Solution

Python

def reverse(self, arr, start, end):
    while start < end:
        arr[start], arr[end] = arr[end], arr[start]
        start += 1
        end -= 1
        
def leftRotate(self, arr, n, d):
    d = d % n
    self.reverse(arr, 0, d - 1)
    self.reverse(arr, d, n - 1)
    self.reverse(arr, 0, n - 1)

Java

void leftRotate(int[] arr, int n, int d) {
    d = d % n;
    reverse(arr, 0, d - 1);
    reverse(arr, d, n - 1);
    reverse(arr, 0, n - 1);
}

void reverse(int[] arr, int start, int end) {
    while (start < end) {
        int temp = arr[start];
        arr[start] = arr[end];
        arr[end] = temp;
        start++;
        end--;
    }
}

C++

public:
void reverse(int arr[], int start, int end) {
    while (start < end) {
        swap(arr[start], arr[end]);
        start++;
        end--;
    }
}
    
public:
void leftRotate(int arr[], int n, int d) {
    d = d % n;  
    reverse(arr, 0, d - 1);
    reverse(arr, d, n - 1);
    reverse(arr, 0, n - 1);
}

C

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void reverse(int arr[], int start, int end) {
    while (start < end) {
        swap(&arr[start], &arr[end]);
        start++;
        end--;
    }
}

void leftRotate(int arr[], int n, int d) {
    d = d % n;
    reverse(arr, 0, d - 1);
    reverse(arr, d, n - 1);
    reverse(arr, 0, n - 1);
}

• Time Complexity: $O(n)$
• Auxiliary Space: $O(1)$