Left rotating an array involves shifting the elements of the array to the left by a specified number of places. In this article, we’ll discuss two efficient methods to achieve this rotation.
Solution 1: Brute Force Approach (using a Temp Array)
This method uses an auxiliary array to store the first D elements and then shifts the rest of the elements to the left.
Implementation:
// Time Complexity: O(n)
// Space Complexity: O(k)
// since k array elements need to be stored in temp array
void leftRotate(int arr[], int n, int k)
{
// Adjust k to be within the valid range (0 to n-1)
k = k % n;
// Handle edge case: empty array
if (n == 0)
{
return;
}
int temp[k];
// Storing k elements in temp array from the left
for (int i = 0; i < k; i++)
{
temp[i] = arr[i];
}
// Shifting the rest of elements to the left
for (int i = k; i < n; i++)
{
arr[i – k] = arr[i];
}
// Putting k elements back to main array
for (int i = n – k; i < n; i++)
{
arr[i] = temp[i – n + k];
}
}
Logic:
Adjust k: Ensure k is within the valid range by taking k % n.
Store in Temp: Store the first k elements in a temporary array.
Shift Elements: Shift the remaining elements of the array to the left by k positions.
Copy Back: Copy the elements from the temporary array back to the end of the main array.
Time Complexity: O(n)
Explanation: Each element is moved once.
Space Complexity: O(k)
Explanation: An additional array of size k is used.
Example:
Input: arr = [1, 2, 3, 4, 5, 6, 7], k = 3
Output: arr = [4, 5, 6, 7, 1, 2, 3]
Explanation: The first 3 elements [1, 2, 3] are stored in a temp array, the rest are shifted left and then the temp array is copied back to the end.
Solution 2: Optimal Approach (using Reversal Algorithm)
This method uses a three-step reversal process to achieve the rotation without needing extra space.
Implementation:
// Time Complexity: O(n)
// Space Complexity: O(1)
// Function to Reverse Array
void reverseArray(int arr[], int start, int end)
{
while (start < end)
{
int temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
start++;
end—;
}
}
// Function to Rotate k elements to the left
void leftRotate(int arr[], int n, int k)
{
// Adjust k to be within the valid range (0 to n-1)
k = k % n;
// Handle edge case: empty array
if (n == 0)
{
return;
}
// Reverse first k elements
reverseArray(arr, 0, k – 1);
// Reverse last n-k elements
reverseArray(arr, k, n – 1);
// Reverse whole array
reverseArray(arr, 0, n – 1);
}
Logic:
Adjust k: Ensure k is within the valid range by taking k % n.
Reverse First Part: Reverse the first k elements.
Reverse Second Part: Reverse the remaining n-k elements.
Reverse Entire Array: Reverse the entire array to achieve the final rotated array.
Time Complexity: O(n)
Explanation: The array is reversed three times, each taking O(n) time.
Space Complexity: O(1)
Explanation: The algorithm operates in place, using only a constant amount of extra space.
Example:
Input: arr = [1, 2, 3, 4, 5, 6, 7], k = 3
Output: arr = [4, 5, 6, 7, 1, 2, 3]
Explanation:
Reverse the first 3 elements: [3, 2, 1, 4, 5, 6, 7]
Reverse the last 4 elements: [3, 2, 1, 7, 6, 5, 4]
Reverse the entire array: [4, 5, 6, 7, 1, 2, 3]
Comparison
Brute Force Method (Using Temp Array):
Pros: Simple and easy to understand.
Cons: Uses additional space for the temporary array, which may not be efficient for large values of k.
Optimal Method (Using Reversal Algorithm):
Pros: Efficient with O(n) time complexity and O(1) space complexity.
Cons: Slightly more complex to implement but highly efficient for large arrays.
Edge Cases
Empty Array: Returns immediately as there are no elements to rotate.
k >= n: Correctly handles cases where k is greater than or equal to the array length by using k % n.
Single Element Array: Returns the same array as it only contains one element.
Additional Notes
Efficiency: The reversal algorithm is more space-efficient, making it preferable for large arrays.
Practicality: Both methods handle rotations efficiently but the choice depends on space constraints.
Conclusion
Left rotating an array by k positions can be efficiently achieved using either a temporary array or an in-place reversal algorithm. The optimal choice depends on the specific constraints and requirements of the problem.
