Left Rotate Array by D Positions

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:

// Solution-1: Using a Temp Array
// 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:

// Solution-2: Using Reversal Algorithm
// 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.

How to Left Rotate an Array by D Positions

Comments

Array

How to Remove Duplicates from a Sorted Array

More from this blog

How to Find the Element that Appears Once in an Array

How to Find the Maximum Consecutive Ones in an Array

How to Find the Missing Number in an Array

Intersection of Two Sorted Arrays

Union of Two Sorted Arrays

Solution 1: Brute Force Approach (using a Temp Array)

Solution 2: Optimal Approach (using Reversal Algorithm)

Comparison

Edge Cases

Additional Notes

Conclusion

Command Palette

Comments

Array

How to Remove Duplicates from a Sorted Array

More from this blog

Solution 1: Brute Force Approach (using a Temp Array)

Solution 2: Optimal Approach (using Reversal Algorithm)

Comparison

Edge Cases

Additional Notes

Conclusion