Rotating an array is a common coding problem that frequently comes up in technical interviews. In this tutorial, we will explore the “Rotate Array” interview question and provide a step-by-step solution using Java. We will cover the problem statement, different approaches to solving it, and discuss their time and space complexities.
Problem Statement
Given an array of integers and a positive integer k, rotate the array to the right by k steps. For example, if the array is [1, 2, 3, 4, 5, 6, 7] and k is 3, the array should be rotated to [5, 6, 7, 1, 2, 3, 4].
Approach 1: Brute Force
One way to solve this problem is to perform the rotation step-by-step. In each step, we move the last element of the array to the front and shift all other elements one step to the right. We repeat this process k times to achieve the desired rotation.
public static void rotate(int[] nums, int k) {
int len = nums.length;
for (int i = 0; i < k; i++) {
int lastElement = nums[len - 1];
for (int j = len - 1; j > 0; j--) {
nums[j] = nums[j - 1];
}
nums[0] = lastElement;
}
}Time Complexity: In the worst case, we need to perform k rotations, and each rotation takes O(n) time where n is the length of the array. Therefore, the total time complexity is O(n * k).
Space Complexity: This approach uses a constant amount of extra space, so the space complexity is O(1).
While this approach works, it is not very efficient, especially when k is large. We can explore a more optimal approach to solving this problem.
Approach 2: Using Extra Array
In this approach, we use an extra array to store the rotated elements. We iterate through the original array and place each element at the correct position in the new array by considering the rotation. Finally, we copy the elements from the new array back to the original array.
public static void rotate(int[] nums, int k) {
int len = nums.length;
int[] rotated = new int[len];
for (int i = 0; i < len; i++) {
rotated[(i + k) % len] = nums[i];
}
System.arraycopy(rotated, 0, nums, 0, len);
}Time Complexity: We iterate through the entire array once to perform the rotation, which takes O(n) time where n is the length of the array. Additionally, we copy the rotated elements back to the original array using System.arraycopy, which also takes O(n) time. Therefore, the total time complexity is O(n).
Space Complexity: We use an extra array to store the rotated elements, which requires O(n) space.
This approach is more efficient than the brute force approach, but we can further optimize it to achieve a better space complexity.
Approach 3: Reversing Subarrays
This approach involves reversing subarrays to achieve the rotation effect. We reverse the entire array, then reverse the first k elements, and finally reverse the remaining elements.
public static void rotate(int[] nums, int k) {
int len = nums.length;
k = k % len; // Handle cases where k > len
// Reverse the entire array
reverse(nums, 0, len - 1);
// Reverse the first k elements
reverse(nums, 0, k - 1);
// Reverse the remaining elements
reverse(nums, k, len - 1);
}
private 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--;
}
}Time Complexity: We reverse the entire array, reverse the first k elements, and reverse the remaining elements, each of which takes O(n) time where n is the length of the array. Therefore, the total time complexity is O(n).
Space Complexity: This approach uses a constant amount of extra space, so the space complexity is O(1).
Approach 4: Cyclic Replacements
This approach involves cyclic replacements to achieve the rotation effect. We start by placing an element from the original array in its correct position. Then, we continue placing the displaced element in its correct position until we reach the starting element again. We repeat this process for each cycle until all elements are in their correct positions.
public static void rotate(int[] nums, int k) {
int len = nums.length;
k = k % len; // Handle cases where k > len
int count = 0;
for (int start = 0; count < len; start++) {
int current = start;
int prev = nums[start];
do {
int next = (current + k) % len;
int temp = nums[next];
nums[next] = prev;
prev = temp;
current = next;
count++;
} while (start != current);
}
}Time Complexity: We visit each element exactly once and place it in its correct position, so the time complexity is O(n).
Space Complexity: This approach uses a constant amount of extra space, so the space complexity is O(1).
Conclusion
In this tutorial, we explored the “Rotate Array” interview question and discussed multiple approaches to solving it. We started with a brute force approach and then moved on to more optimized solutions, including using an extra array, reversing subarrays, and cyclic replacements. Each approach has its own time and space complexities, with the last two approaches being the most efficient in terms of both time and space.
Remember that understanding the problem thoroughly and designing efficient algorithms are essential skills when it comes to solving coding interview questions. It’s important to analyze the requirements, constraints, and possible edge cases before finalizing your solution. Practice and experimentation will help you become more confident in tackling such problems during technical interviews.