Skip to main content

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)O(n)
  • Expected Auxiliary Space: O(1)O(1)

Constraints:​

  • 1≤n≤1061 ≤ n ≤ 10^6
  • −109≤arr[i]≤109-10^9 ≤ arr[i] ≤ 10^9
  • 0≤d≤n0 ≤ 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)O(n)
  • Auxiliary Space: O(1)O(1)