Left Rotate an Array

Posted in

Left Rotate an Array

Vinay Khatri
Last updated on November 3, 2022

    Problem

    Given an array of integers, you need to rotate it by k times.

    Sample Input

    [1, 2, 3] k=1

    Sample Output

    [2, 3, 1]

    Approach 1

    We can place the first k elements in some other array and shift remaining elements to the beginning. Later, we can insert the first k elements at the last. The approach takes O(N) time and O( k ) auxiliary space.

    C

    #include <stdio.h>
    voidsolve(int arr[], int k, int n)
    {
     int auxArray[k];
     for (int i = 0; i < k; i++) {
     auxArray[i] = arr[i];
     }
     for (int i = k; i < n; i++) {
     arr[i-k] = arr[i];
     }
     for (int i = n-k; i < n; i++) {
     arr[i] = auxArray[i-(n-k)];
     }
    }
    intmain()
    {
     int arr[] = { 1, 2, 3 };
     int k = 1;
     int n = sizeof(arr)/sizeof(arr[0]);
     solve(arr, k, n);
     for (int i = 0; i < n; i++) {
     printf("%d ", arr[i]);
     }
     return0;
    }

    Output

    2 3 1

    Approach 2

    If we reverse first k elements, then the remaining elements and then the entire array, we may observe that this will always give the required array. This approach takes O(N) time and O(1) auxiliary space.

    C

    #include <stdio.h>
    voidreverseHelper(int arr[], int low, int high)
    {
     for (int i = low, j = high; i < j; i++, j--)
     {
     int temp = arr[i];
     arr[i] = arr[j];
     arr[j] = temp;
     }
    }
    voidsolve(int arr[], int k, int n)
    {
     reverseHelper(arr, 0, k - 1);
     reverseHelper(arr, k, n - 1);
     reverseHelper(arr, 0, n - 1);
    }
    intmain(void)
    {
     int arr[] = { 1, 2, 3 };
     int k = 1;
     int n = sizeof(arr)/sizeof(arr[0]);
     solve(arr, k, n);
     for (int i = 0; i < n; i++) {
     printf("%d ", arr[i]);
     }
     return0;
    }

    Output

    2 3 1

    C++

    #include <bits/stdc++.h>
    usingnamespacestd;
    voidreverseHelper(int arr[], int low, int high)
    {
     for (int i = low, j = high; i < j; i++, j--)
     {
     int temp = arr[i];
     arr[i] = arr[j];
     arr[j] = temp;
     }
    }
    voidsolve(int arr[], int k, int n)
    {
     reverseHelper(arr, 0, k - 1);
     reverseHelper(arr, k, n - 1);
     reverseHelper(arr, 0, n - 1);
    }
    intmain(void)
    {
     int arr[] = { 1, 2, 3 };
     int k = 1;
     int n = sizeof(arr)/sizeof(arr[0]);
     solve(arr, k, n);
     for (int i = 0; i < n; i++) {
     cout<<arr[i]<<" ";
     }
     return0;
    }

    Output

    2 3 1

    Python

    defswap(arr, i, j):
     temp = arr[i]
     arr[i] = arr[j]
     arr[j] = temp
    defreverse(arr, start, finish):
     (i, j) = (start, finish)
     while i < j:
     swap(arr, i, j)
     i = i + 1
     j = j - 1
    defsolve(arr, k):
     reverse(arr, 0, k - 1)
     reverse(arr, k, len(arr) - 1)
     reverse(arr, 0, len(arr) - 1)
    arr = [1, 2, 3]
    k = 1
    solve(arr, k)
    print(arr)

    Output

    2 3 1

    People are also reading:

    Leave a Comment on this Post

    0 Comments