Problem Statement: Given an array of N integers, left rotate the array by one place.
Examples
Example 1:
Input: N = 5, array[] = {1,2,3,4,5}
Output: 2,3,4,5,1
Explanation:
Since all the elements in array will be shifted
toward left by one so ‘2’ will now become the
first index and and ‘1’ which was present at
first index will be shifted at last.
Example 2:
Input: N = 1, array[] = {3}
Output: 3
Explanation: Here only element is present and so
the element at first index will be shifted to
last index which is also by the way the first index.
Disclaimer: Don’t jump directly to the solution, try it out yourself first.
Brute Force Approach
Algorithm / Intuition
Solution 1: Brute force Approach
Intuition:
The rotated array has just a difference that its first element is present at the last index of the array. So if we can just store the element at the first index and then shift all the elements towards the left and at last put the stored element at the last index. We will get th rotated array.
Approach:
We can take another dummy array of the same length and then shift all elements in the array toward the left and then at the last element store the index of 0th index of the array and print it.
Code
#include<bits/stdc++.h>
using namespace std;
void solve(int arr[], int n) {
int temp[n];
for (int i = 1; i < n; i++) {
temp[i - 1] = arr[i];
}
temp[n - 1] = arr[0];
for (int i = 0; i < n; i++) {
cout << temp[i] << " ";
}
cout << endl;
}
int main() {
int n=5;
int arr[]= {1,2,3,4,5};
solve(arr, n);
}
Output: 2 3 4 5 1
import java.util.*;
class TUF{
static void solve(int arr[], int n) {
int temp[]=new int[n];
for (int i = 1; i < n; i++) {
temp[i - 1] = arr[i];
}
temp[n - 1] = arr[0];
for (int i = 0; i < n; i++) {
System.out.print(temp[i]+" ");
}
}
public static void main(String args[]) {
int n=5;
int arr[]= {1,2,3,4,5};
solve(arr, n);
}
}
Output: 2 3 4 5 1
def solve(arr, n):
temp = [0] * n
for i in range(1, n):
temp[i - 1] = arr[i]
temp[n - 1] = arr[0]
for i in range(n):
print(temp[i], end=" ")
print()
n = 5
arr = [1, 2, 3, 4, 5]
solve(arr, n)
Output: 2 3 4 5 1
function solve(arr, n) {
let temp = new Array(n);
for (let i = 1; i < n; i++) {
temp[i - 1] = arr[i];
}
temp[n - 1] = arr[0];
for (let i = 0; i < n; i++) {
console.log(temp[i] + " ");
}
console.log();
}
let n = 5;
let arr = [1, 2, 3, 4, 5];
solve(arr, n);
Output: 2 3 4 5 1
Complexity Analysis
Time Complexity: O(n), as we iterate through the array only once.
Space Complexity: O(n) as we are using another array of size, same as the given array.
Optimal Approach
Algorithm / Intuition
Solution 2:
Approach:
Here, in the given array :
n = 5,
arr[] = {1,2,3,4,5}
At first, we have to shift the array towards the left so, we store the value of the first index in a variable (let it be x).
Then we iterate the array from the 0th index to the n-1th index(why n-1 i will explain it below)
And then store the value present in the next index to the current index like this :
arr[i] = arr[i+1]
And to prevent its segmentation fault we will iterate it till n-1.
At last, put the value of variable x in the last index of the array.
Code
#include<bits/stdc++.h>
using namespace std;
void solve(int arr[], int n) {
int temp = arr[0]; // storing the first element of array in a variable
for (int i = 0; i < n - 1; i++) {
arr[i] = arr[i + 1];
}
arr[n - 1] = temp; // assigned the value of variable at the last index
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
}
int main() {
int n=5;
int arr[]= {1,2,3,4,5};
solve(arr, n);
}
Output: 2 3 4 5 1
import java.util.*;
class TUF{
static void solve(int arr[], int n) {
int temp = arr[0]; // storing the first element of array in a variable
for (int i = 0; i < n - 1; i++) {
arr[i] = arr[i + 1];
}
arr[n - 1] = temp; // assigned the value of variable at the last index
for (int i = 0; i < n; i++) {
System.out.print(arr[i]+" ");
}
}
public static void main(String args[]) {
int n=5;
int arr[]= {1,2,3,4,5};
solve(arr, n);
}
}
Output: 2 3 4 5 1
def solve(arr, n):
temp = arr[0] # storing the first element of the array in a variable
for i in range(n - 1):
arr[i] = arr[i + 1]
arr[n - 1] = temp # assign the value of the variable at the last index
for i in range(n):
print(arr[i], end=" ")
n = 5
arr = [1, 2, 3, 4, 5]
solve(arr, n)
Output: 2 3 4 5 1
function solve(arr, n) {
let temp = arr[0]; // storing the first element of the array in a variable
for (let i = 0; i < n - 1; i++) {
arr[i] = arr[i + 1];
}
arr[n - 1] = temp; // assign the value of the variable at the last index
for (let i = 0; i < n; i++) {
console.log(arr[i] + " ");
}
}
let n = 5;
let arr = [1, 2, 3, 4, 5];
solve(arr, n);
Output: 2 3 4 5 1
Complexity Analysis
Time Complexity: O(n), as we iterate through the array only once.
Space Complexity: O(1) as no extra space is used
Video Explanation
Special thanks to Ayush Pandey for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article