DEV Community

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

Posted on • Originally published at blog.masum.dev

How to Right Rotate an Array by D Positions

Right rotating an array involves shifting the elements of the array to the right 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 last D elements and then shifts the rest of the elements to the right.

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 rightRotate1(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 right
    for (int i = n - k; i < n; i++)
    {
        temp[i - n + k] = arr[i];
    }

    // Shifting the rest of elements to the right
    for (int i = n - k - 1; i >= 0; i--)
    {
        arr[i + k] = arr[i];
    }

    // Putting k elements back to main array
    for (int i = 0; i < k; i++)
    {
        arr[i] = temp[i];
    }
}
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 last k elements in a temporary array.

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

  4. Copy Back: Copy the elements from the temporary array back to the start 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 = [5, 6, 7, 1, 2, 3, 4]

  • Explanation: The last 3 elements [5, 6, 7] are stored in a temp array, the rest are shifted right and then the temp array is copied back to the start.


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 right
void rightRotate2(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 n-k elements
    reverseArray(arr, 0, n - 1 - k);

    // Reverse last k elements
    reverseArray(arr, n - 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 n - k elements.

  3. Reverse Second Part: Reverse the remaining 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 = [5, 6, 7, 1, 2, 3, 4]

  • Explanation:

    • Reverse the first 4 elements: [4, 3, 2, 1, 5, 6, 7]
    • Reverse the last 3 elements: [4, 3, 2, 1, 7, 6, 5]
    • Reverse the entire array: [5, 6, 7, 1, 2, 3, 4]

Comparison

  • Temp Array Method:

    • Pros: Simple and easy to understand.
    • Cons: Uses additional space for the temporary array, which may not be efficient for large values of k.
  • 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

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


Top comments (0)