left_rotate.cpp

#include <iostream>
using namespace std;
/*

Left rotate an array by d steps
or
Rotate an array in anti-clockwise direction by d steps

ip: arr[] = {1, 2, 3, 4, 5}, d=2
op: arr[] = {3, 4, 5, 1, 2}

Naive approach: LeftRotate the el d times
Time: Theta(n x d)

Efficient approach (method2):
copy first d elements in temp arr
in original array, from index d+1 to n-1,
shift all elements d positions back
then copy elemnts from temp to arr,
arr[n-d+i] = temp[i]
Time: theta(d) + theta(n-d) + theta(d)
i.e theta(n)
Space: theta(d)

eg: arr = [1, 2, 3, 4, 5], d = 2
copy els to temp
temp = [1, 2]

shift n-d els
arr = [3, 4, 5, 4, 5]

put els back to og array
arr = [3, 4, 5, 1, 2]

Efficient approach (method3):
Step 1) reverse first d els i.e from 0 to d-1
Step 2) reverse n-d els i.e from d to n-1
Step 3) reverse the entire array

eg: arr = [1, 2, 3, 4, 5], d=2

after first reverse
arr = [2, 1, 3, 4, 5]

after second reverse
arr = [2, 1, 5, 4, 3]

after third reverse 
arr = [3, 4, 5, 1, 2]

Time: O(d+n-d+n) = O(2n) = O(n)
Space: O(1)
*/

void leftRotateByOne(int arr[], int n)
{
    int temp = arr[0];
    for (int i = 1; i < n; i++)
        arr[i - 1] = arr[i];

    arr[n - 1] = temp;
}
void leftRotateBysteps(int arr[], int n, int steps)
{

    // in case steps>arr_size
    if (steps > n)
        steps = n - steps;

    for (int i = 0; i < steps; i++)
        leftRotateByOne(arr, n);
}

void leftRotateBysteps_method2(int arr[], int n, int d)
{
    int temp[d];
    // copy first d els into temp
    for (int i = 0; i < d; i++)
        temp[i] = arr[i];

    // shift the remanining n-d els
    for (int i = d; i < n; i++)
        arr[i - d] = arr[i];
    
    // copy element back to og arr
    for (int i = 0; i < d; i++)
        arr[n - d + i] = temp[i];
}

void reverse_method3(int arr[], int low, int high)
{
    while(low < high)
    {
        swap(arr[low], arr[high]);
        low++;
        high--;
    }
}

void leftRotateBysteps_method3(int arr[], int n, int d)
{
    // in case d>n
    d = d % n;

    reverse_method3(arr, 0, d - 1);
    reverse_method3(arr, d, n - 1);
    reverse_method3(arr, 0, n - 1);
}