DEV Community

Cover image for How to Left Rotate an Array by D Positions
Mahbub Alam Masum
Mahbub Alam Masum

Posted on • Originally published at blog.masum.dev

How to Left Rotate an 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];
    }
}
Enter fullscreen mode Exit fullscreen mode

Logic:

  1. Adjust k: Ensure k is within the valid range by taking k % n.

  2. Store in Temp: Store the first k elements in a temporary array.

  3. Shift Elements: Shift the remaining elements of the array to the left by k positions.

  4. 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);
}
Enter fullscreen mode Exit fullscreen mode

Logic:

  1. Adjust k: Ensure k is within the valid range by taking k % n.

  2. Reverse First Part: Reverse the first k elements.

  3. Reverse Second Part: Reverse the remaining n-k elements.

  4. 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.


Image of Docusign

🛠️ Bring your solution into Docusign. Reach over 1.6M customers.

Docusign is now extensible. Overcome challenges with disconnected products and inaccessible data by bringing your solutions into Docusign and publishing to 1.6M customers in the App Center.

Learn more

Top comments (0)

AWS Security LIVE!

Tune in for AWS Security LIVE!

Join AWS Security LIVE! for expert insights and actionable tips to protect your organization and keep security teams prepared.

Learn More

👋 Kindness is contagious

Explore a sea of insights with this enlightening post, highly esteemed within the nurturing DEV Community. Coders of all stripes are invited to participate and contribute to our shared knowledge.

Expressing gratitude with a simple "thank you" can make a big impact. Leave your thanks in the comments!

On DEV, exchanging ideas smooths our way and strengthens our community bonds. Found this useful? A quick note of thanks to the author can mean a lot.

Okay