.png)
Rotate an Array by K Positions
Problem Statement
Given an array of integers and a value K, rotate the array by K positions.
By default, we consider right rotation unless stated otherwise.
Important Conditions
- K can be greater than the array size
- The rotation should be done efficiently
- Extra space should be avoided if possible
- Handle both small and large values of K
Understanding the Problem
Example 1
Input: Array = [1, 2, 3, 4, 5]
K = 2
Output: [4, 5, 1, 2, 3]
Explanation:
Rotating the array right by 2 positions moves the last two elements to the front.
Example 2 (Another Example)
Input: Array = [10, 20, 30, 40, 50, 60]
K = 3
Output: [40, 50, 60, 10, 20, 30]
Explanation:
After rotating right by 3 positions:
- Elements 40, 50, 60 come to the front
- Remaining elements shift to the right
Why This Problem Is Important
This problem helps in understanding:
- Modulo arithmetic
- Efficient array manipulation
- In-place reversal techniques
It is commonly asked in:
- Coding interviews
- Competitive programming
- Real-world data rotation problems
Input and Output Format
Input
Array: [10, 20, 30, 40, 50, 60]
K = 3
Output
Rotated Array: [40, 50, 60, 10, 20, 30]
Approach 1: Reversal Algorithm (Optimal)
Key Idea
For right rotation by K:
- Reverse the entire array
- Reverse the first K elements
- Reverse the remaining n - K elements
Step-by-Step Algorithm
Compute
K = K % n- Reverse the entire array
- Reverse elements from index 0 to K-1
- Reverse elements from index K to n-1
Pseudocode
K = K % n
reverse(arr, 0, n-1)
reverse(arr, 0, K-1)
reverse(arr, K, n-1)
Dry Run (Example 2)
Array = [10, 20, 30, 40, 50, 60]
K = 3
- Reverse whole array
[60, 50, 40, 30, 20, 10]
- Reverse first K elements
[40, 50, 60, 30, 20, 10]
- Reverse remaining elements
[40, 50, 60, 10, 20, 30]
✅ Final Answer
Time and Space Complexity
| Metric | Value |
|---|---|
| Time Complexity | O(n) |
| Space Complexity | O(1) |
Language-wise Implementation
C Implementation
#include<stdio.h>
void reverse(int arr[], int start, int end) {
while(start < end) {
int temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
start++;
end--;
}
}
int main() {
int arr[] = {10, 20, 30, 40, 50, 60};
int n = sizeof(arr) / sizeof(arr[0]);
int k = 3;
k = k % n;
reverse(arr, 0, n - 1);
reverse(arr, 0, k - 1);
reverse(arr, k, n - 1);
for(int i = 0; i < n; i++)
printf("%d ", arr[i]);
return 0;
}
C++ Implementation
#include<iostream>
using namespace std;
void reverse(int arr[], int start, int end) {
while(start < end) {
swap(arr[start], arr[end]);
start++;
end--;
}
}
int main() {
int arr[] = {10, 20, 30, 40, 50, 60};
int n = sizeof(arr) / sizeof(arr[0]);
int k = 3;
k = k % n;
reverse(arr, 0, n - 1);
reverse(arr, 0, k - 1);
reverse(arr, k, n - 1);
for(int i = 0; i < n; i++)
cout << arr[i] << " ";
return 0;
}
Java Implementation
public class Main {
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--;
}
}
public static void main(String[] args) {
int[] arr = {10, 20, 30, 40, 50, 60};
int k = 3;
int n = arr.length;
k = k % n;
reverse(arr, 0, n - 1);
reverse(arr, 0, k - 1);
reverse(arr, k, n - 1);
for(int num : arr)
System.out.print(num + " ");
}
}
Python Implementation
arr = [10, 20, 30, 40, 50, 60]
k = 3
n = len(arr)
k = k % n
arr.reverse()
arr[:k] = reversed(arr[:k])
arr[k:] = reversed(arr[k:])
print(arr)
JavaScript Implementation
let arr = [10, 20, 30, 40, 50, 60];
let k = 3;
let n = arr.length;
k = k % n;
arr.reverse();
let firstPart = arr.slice(0, k).reverse();
let secondPart = arr.slice(k).reverse();
arr = firstPart.concat(secondPart);
console.log(arr);
Common Mistakes to Avoid
- Forgetting to apply K % n
- Confusing left and right rotation
- Using extra arrays unnecessarily
- Rotating one-by-one instead of using optimal logic
Detailed Summary
Rotating an array by K positions is an extension of single-position rotation. Using the reversal algorithm, we can rotate the array efficiently in O(n) time and O(1) space. This method handles large values of K gracefully and is widely preferred in interviews.
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
