Left Rotate an Array

Problem

Given an array of integers, you need to rotate it by k times.

Sample Input

[1, 2, 3] k=1

Sample Output

[2, 3, 1]

Approach 1

We can place the first k elements in some other array and shift remaining elements to the beginning. Later, we can insert the first k elements at the last. The approach takes O(N) time and O( k ) auxiliary space.

C

#include <stdio.h>
voidsolve(int arr[], int k, int n)
{
 int auxArray[k];
 for (int i = 0; i < k; i++) {
 auxArray[i] = arr[i];
 }
 for (int i = k; i < n; i++) {
 arr[i-k] = arr[i];
 }
 for (int i = n-k; i < n; i++) {
 arr[i] = auxArray[i-(n-k)];
 }
}
intmain()
{
 int arr[] = { 1, 2, 3 };
 int k = 1;
 int n = sizeof(arr)/sizeof(arr[0]);
 solve(arr, k, n);
 for (int i = 0; i < n; i++) {
 printf("%d ", arr[i]);
 }
 return0;
}

Output

2 3 1

Approach 2

If we reverse first k elements, then the remaining elements and then the entire array, we may observe that this will always give the required array. This approach takes O(N) time and O(1) auxiliary space.

C

#include <stdio.h>
voidreverseHelper(int arr[], int low, int high)
{
 for (int i = low, j = high; i < j; i++, j--)
 {
 int temp = arr[i];
 arr[i] = arr[j];
 arr[j] = temp;
 }
}
voidsolve(int arr[], int k, int n)
{
 reverseHelper(arr, 0, k - 1);
 reverseHelper(arr, k, n - 1);
 reverseHelper(arr, 0, n - 1);
}
intmain(void)
{
 int arr[] = { 1, 2, 3 };
 int k = 1;
 int n = sizeof(arr)/sizeof(arr[0]);
 solve(arr, k, n);
 for (int i = 0; i < n; i++) {
 printf("%d ", arr[i]);
 }
 return0;
}

Output

2 3 1

C++

#include <bits/stdc++.h>
usingnamespacestd;
voidreverseHelper(int arr[], int low, int high)
{
 for (int i = low, j = high; i < j; i++, j--)
 {
 int temp = arr[i];
 arr[i] = arr[j];
 arr[j] = temp;
 }
}
voidsolve(int arr[], int k, int n)
{
 reverseHelper(arr, 0, k - 1);
 reverseHelper(arr, k, n - 1);
 reverseHelper(arr, 0, n - 1);
}
intmain(void)
{
 int arr[] = { 1, 2, 3 };
 int k = 1;
 int n = sizeof(arr)/sizeof(arr[0]);
 solve(arr, k, n);
 for (int i = 0; i < n; i++) {
 cout<<arr[i]<<" ";
 }
 return0;
}

Output

2 3 1

Python

defswap(arr, i, j):
 temp = arr[i]
 arr[i] = arr[j]
 arr[j] = temp
defreverse(arr, start, finish):
 (i, j) = (start, finish)
 while i < j:
 swap(arr, i, j)
 i = i + 1
 j = j - 1
defsolve(arr, k):
 reverse(arr, 0, k - 1)
 reverse(arr, k, len(arr) - 1)
 reverse(arr, 0, len(arr) - 1)
arr = [1, 2, 3]
k = 1
solve(arr, k)
print(arr)

Output

2 3 1

People are also reading:

• Sorted Triplet in an Array
• Print Matrix in Spiral Form
• Job Sequencing Problem
• Find Subarrays within Given Sum in an Array
• Find MSB in O(1)
• Longest Substring without repeating characters
• Delete Nodes And Return Forest
• Count subarrays with given XOR
• Nth root of M
• Find K-th Smallest Element in BST