Left Rotate an Array

Posted in

Left Rotate an Array
vinaykhatri

Vinay Khatri
Last updated on June 16, 2024

    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