Left rotate an array by D places

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.

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:

1. First, we will perform (d%n) to get the effective number of rotations.
2. We will store the first d elements in a temporary array.
3. 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].
4. 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).
1. 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.
2. 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:

1. Step 1: Reverse the subarray with the first d elements (reverse(arr, arr+d)).
2. Step 2: Reverse the subarray with the last (n-d) elements (reverse(arr+d, arr+n)).
3. 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.