Problem Statement: Given an array of N integers and an integer D, left rotate the array by D place.
Pre-requisite: Left Rotate the Array by One
Examples:
Example 1:
Input: N = 7, array[] = {1,2,3,4,5,6,7} , d = 3
Output: 4 5 6 7 1 2 3
Explanation: The array is rotated to the left by 3 positions.
Example 2:
Input: N = 6, array[] = {3,7,8,9,10,11} , d = 2
Output: 8 9 10 11 3 7
Explanation: The array is rotated to the left by 2 positions.
Solution
Disclaimer: Don’t jump directly to the solution, try it out yourself first.
Problem Link 1.
Problem Link 2.
Observation:
Before moving on to the solution, let’s understand how the rotation will happen for a given array. The following illustration will clarify the rotation technique.
Assume the given array is {1,2,3,4,5,6,7} and d = 3.
Now, in the above case, if we closely observe, we can notice that if the value of d = 7 i.e. the size of the array, after rotation the array will be exactly similar to the given array. And the same case can be observed when the value of d is 14, 21, 28, or a multiple of 7.
So, we can conclude, that if the number of rotations is a multiple of the size of the array, the rotations will have no effect on the given array.
if( d % n == 0) rotated array = given array, where d = number of rotations, n =size of the array
So, if d is greater than n(i.e. Size of the array), the effective number of rotations will be (d % n).
Brute Force Approach:
The steps are as follows:
- First, we will perform (d%n) to get the effective number of rotations.
- We will store the first d elements in a temporary array.
- We will shift the last (n-d) elements by d places to the left using a loop(say i) that will start from index d and run up to index n-1 (in case of 0-based indexing). Inside the loop, the shifting will be like: arr[i-d] = arr[i].
- After that, we will place the elements of the temporary array in the last d places of the given array using another loop that starts from (n-d) and runs up to n-1 (0-based index).
- While selecting elements from the temporary array, one of the ways is to use a variable(say j and starts from 0) and increment it inside the loop.
- The efficient way will be the following. The element at index i in the temporary array will be placed at index (n-d+i) in the given array. So, to place the elements in the correct position, inside the loop, we will do this: arr[i] = temp[i-(n-d)].
Assume the given array is {1,2,3,4,5,6,7} and d = 3.
Code:
C++ Code
#include <bits/stdc++.h>
using namespace std;
void leftRotate(int arr[], int n, int d) {
if (n == 0) return;
// Get the effective number of rotations:
d = d % n;
//checking if d is a multiple of n:
if (d == 0) return;
int temp[d]; // temporary array
//step 1: Copying first d elements
// in the temporary array:
for (int i = 0; i < d; i++) {
temp[i] = arr[i];
}
// step 2: Shift last (n-d) elements
// to the left by d places in the given array:
for (int i = d; i < n; i++) {
arr[i - d] = arr[i];
}
//step 3: Place the elements of the temporary
// array in the last d places of the given array:
for (int i = n - d; i < n; i++) {
arr[i] = temp[i - (n - d)];
}
}
int main()
{
int n = 7;
int arr[] = {1, 2, 3, 4, 5, 6, 7};
int d = 3;
cout << "Before rotation:" << endl;
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
leftRotate(arr, n, d);
cout << "After rotation:" << endl;
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
return 0;
}
Output:
Before rotation:
1 2 3 4 5 6 7
After rotation:
4 5 6 7 1 2 3
Time Complexity: O(d)+O(n-d)+O(d) = O(n+d), where n = size of the array, d = the number of rotations. Each term represents each loop used in the code.
Space Complexity: O(d) extra space as we are using a temporary array of size d.
Java Code
import java.util.*;
public class Main {
static void leftRotate(int arr[], int n, int d) {
if (n == 0) return;
// Get the effective number of rotations:
d = d % n;
// checking if d is a multiple of n:
if (d == 0) return;
int[] temp = new int[d]; // temporary array
//step 1: Copying first d elements
// in the temporary array:
for (int i = 0; i < d; i++) {
temp[i] = arr[i];
}
// step 2: Shift last (n-d) elements
// to the left by d places in the given array:
for (int i = d; i < n; i++) {
arr[i - d] = arr[i];
}
//step 3: Place the elements of the temporary
// array in the last d places of the given array:
for (int i = n - d; i < n; i++) {
arr[i] = temp[i - (n - d)];
}
}
public static void main(String args[]) {
int n = 7;
int arr[] = {1, 2, 3, 4, 5, 6, 7};
int d = 3;
System.out.println("Before rotation:");
for (int i = 0; i < n; i++)
System.out.print( arr[i] + " ");
System.out.println();
leftRotate(arr, n, d);
System.out.println("After rotation:");
for (int i = 0; i < n; i++)
System.out.print(arr[i] + " ");
System.out.println();
}
}
Output:
Before rotation:
1 2 3 4 5 6 7
After rotation:
4 5 6 7 1 2 3
Time Complexity: O(d)+O(n-d)+O(d) = O(n+d), where n = size of the array, d = the number of rotations. Each term represents each loop used in the code.
Space Complexity: O(d) extra space as we are using a temporary array of size d.
Optimized Approach(without using any extra space): Using “Reversal Algorithm”
This is a straightforward method. The steps are as follows:
- Step 1: Reverse the subarray with the first d elements (reverse(arr, arr+d)).
- Step 2: Reverse the subarray with the last (n-d) elements (reverse(arr+d, arr+n)).
- Step 3: Finally reverse the whole array (reverse(arr, arr+n)).
Assume the given array is {1,2,3,4,5,6,7} and d = 3.
Note: In C++ we can use the in-built reverse() function for array reversal. If we have no in-built function, we can implement one like the following:
Code:
C++ Code
#include <bits/stdc++.h>
using namespace std;
void leftRotate(int arr[], int n, int d) {
if (n == 0) return;
// Get the effective number of rotations:
d = d % n;
//step 1:
reverse(arr, arr + d);
//step 2:
reverse(arr + d, arr + n);
//step 3:
reverse(arr, arr + n);
}
int main()
{
int n = 7;
int arr[] = {1, 2, 3, 4, 5, 6, 7};
int d = 3;
cout << "Before rotation:" << endl;
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
leftRotate(arr, n, d);
cout << "After rotation:" << endl;
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
return 0;
}Output:
Before rotation:
1 2 3 4 5 6 7
After rotation:
4 5 6 7 1 2 3
Time Complexity: O(d)+O(n-d)+O(n) = O(2*n), where n = size of the array, d = the number of rotations. Each term corresponds to each reversal step.
Space Complexity: O(1) since no extra space is required.
Java Code
import java.util.*;
public class tUf {
// Function to Reverse the array
static void reverse(int arr[], int start, int end) {
while (start <= end) {
int temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
start++;
end--;
}
}
static void leftRotate(int arr[], int n, int d) {
if (n == 0) return;
// Get the effective number of rotations:
d = d % n;
//step 1:
reverse(arr, 0, d - 1);
//step 2:
reverse(arr, d, n - 1);
//step 3:
reverse(arr, 0, n - 1);
}
public static void main(String args[]) {
int n = 7;
int arr[] = {1, 2, 3, 4, 5, 6, 7};
int d = 3;
System.out.println("Before rotation:");
for (int i = 0; i < n; i++)
System.out.print( arr[i] + " ");
System.out.println();
leftRotate(arr, n, d);
System.out.println("After rotation:");
for (int i = 0; i < n; i++)
System.out.print(arr[i] + " ");
System.out.println();
}
} Output:
Before rotation:
1 2 3 4 5 6 7
After rotation:
4 5 6 7 1 2 3
Time Complexity: O(d)+O(n-d)+O(n) = O(2*n), where n = size of the array, d = the number of rotations. Each term corresponds to each reversal step.
Space Complexity: O(1) since no extra space is required.
Special thanks to KRITIDIPTA GHOSH for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article. If you want to suggest any improvement/correction in this article please mail us at [email protected]