Right Rotate 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];
    }
}

Logic:

Adjust k: Ensure k is within the valid range by taking k % n.
Store in Temp: Store the last k elements in a temporary array.
Shift Elements: Shift the remaining elements of the array to the right by k positions.
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);
}

Logic:

Adjust k: Ensure k is within the valid range by taking k % n.
Reverse First Part: Reverse the first n - k elements.
Reverse Second Part: Reverse the remaining 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 = [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.

How to Right Rotate an Array by D Positions

Comments

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

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