BlogsDope image BlogsDope

Rotate an array by K positions

Nov. 16, 2020 C PYTHON ALGORITHM ARRAY 173

Problem Statement


We are given an array of size N and a value K. We have to rotate the array by K positions.

Let’s understand by example.

Input :

A[ ] = { 1, 2, 3, 4, 5, 6, 7 }
K = 3

Output :

5, 6, 7, 1, 2, 3, 4 

Solution


Rotation using an extra array

A simple solution is to use an extra array and store the elements in the order they are required in the result. We will run two loops, one for storing the last K elements and the other for storing the rest of the elements. In the first loop, store the last K elements in the same order (as that in the old array) filling the starting positions of the new array. Then fill the rest of the elements in the new array in the exact order.

Complexity analysis

The time complexity for the above solution is $O(N)$ as we are traversing the array only once, but we are also using extra space, so we also have space complexity of $O(N)$.

Pseudocode for the above approach:

Extra array : arr[ ]
Original array : a[ ]

For i = 0 to K-1
    arr[i] = a[N-K+i]

For i = K to N-1
    arr[i] = a[i-K]

For i = 0 to N-1
    a[i]= arr[i]

Implementation of the above approach

  • C/C++
  • Python
// Program to rotate the given
// array by K positions

#include <bits/stdc++.h>

using namespace std;

// Function to rotate the given
// array by K positions

void rotate_array(int a[], int N, int K)
{

    int arr[N];

    fill(arr, arr + N, 0);

    // add last K elements
    for (int i = 0; i < K; i++)
        arr[i] = a[N - K + i];

    // add remaining elements

    for (int i = K; i < N; i++)
        arr[i] = a[i - K];

    // assign new values to the
    // array
    for (int i = 0; i < N; i++)
        a[i] = arr[i];
}

// Driver code

int main()
{
    int a[7] = {1, 2, 3, 4, 5, 6, 7};

    int K = 3;

    int N = sizeof(a) / sizeof(int);

    // Function Call

    rotate_array(a, N, K);

    for (int i = 0; i < N; i++)
        cout << a[i] << " ";
}
# Program to rotate the given
# array by K positions

# Function to rotate the given
# array by K positions


def rotate_array(a, N, K):
    arr = []
    for i in range(N):
        arr.append(0)

    # add last K elements
    for i in range(K):
        arr[i] = a[N - K + i]

    # add remaining elements
    for i in range(K, N):
        arr[i] = a[i - K]

    # assign new values to the
    # array
    for i in range(N):
        a[i] = arr[i]


# Driver code
a = [1, 2, 3, 4, 5, 6, 7]
K = 3
N = len(a)

# Function Call

rotate_array(a, N, K)

for i in range(N):
    print(a[i], end=" ")

By rotating the array K times

We can rotate the array K times by one position resulting in the final array rotated by K positions. Save the last element and shift the rest of the elements by one position to the right and then overwrite the first element with the saved last element. 

Complexity analysis

The time complexity for the above approach is $O(N* K)$. Shifting all the elements by one position takes linear time and this process is repeated for K times.

The Pseudocode for the above approach

 for count = 0 to count = K-1
         end = a[N-1]
         for i = N-1 to i = 1
             a[i] = a[i-1]
          a[0] = end

Implementation of the above approach

  • C/C++
  • Python
// Program to rotate the given
// array by K positions

#include <bits/stdc++.h>

using namespace std;

// Function to rotate the given
// array by K positions

void rotate_array(int a[], int N, int K)
{
    // Rotating the array K times by one
    //position

    for (int count = 0; count < K; count++)
    {
        // saving last element

        int end = a[N - 1];

        for (int i = N - 1; i > 0; i--)
            a[i] = a[i - 1];
        a[0] = end;
    }
}

// Driver code

int main()
{
    int a[7] = {1, 2, 3, 4, 5, 6, 7};

    int K = 3;

    int N = sizeof(a) / sizeof(int);

    // Function Call

    rotate_array(a, N, K);

    for (int i = 0; i < N; i++)
        cout << a[i] << " ";
}
# Program to rotate the given
# array by K positions

# Function to rotate the given
# array by K positions


def rotate_array(a, N, K):
    # Rotating the array K times by one
    # position

    for count in range(K):

        # saving the last element

        end = a[N - 1]

        for i in range(N - 1, 0, -1):
            a[i] = a[i - 1]

        a[0] = end


# Driver code

a = [1, 2, 3, 4, 5, 6, 7]
K = 3
N = len(a)

# Function Call

rotate_array(a, N, K)

for i in range(N):
    print(a[i], end=" ")

Most efficient approach

There is an observation in the problem that we are shifting the last K elements in the starting of the array by pushing the elements in the starting to the end of the array in the exact order. We can achieve this by reversing the last K elements, then reversing the remaining elements, and then finally reversing the whole array.

This is pure observation and can be well understood by a diagram.

For a[7] = { 1, 2, 3, 4, 5, 6, 7 }
K = 3 

Initial array:

1234567

Array after reversing last K elements:

1234765

Array after reversing first N-K elements:

4321765

After reversing the modified array:

5671234

Complexity analysis

The time complexity for the above approach is $O(N)$ because we will use a linear reversing algorithm and we are just calling the reverse function three times.

Pseudocode for the above approach

For reversing :
start, end
while start < end :
    swap( a[start ], a[end] )
     start++
     end--

Reverse last K elements
Reverse first N-K elements
Reverse the whole array

Implementation of the above approach

  • C/C++
  • Python
// Program to rotate the given
// array by K positions

#include <bits/stdc++.h>
using namespace std;

//Function for reversing the
// array

void reverse(int a[], int start, int end)
{
    while (start < end)
    {
        swap(a[start], a[end]);
        start++;
        end--;
    }
}

// Function to rotate the given
// array by K positions

void rotate_array(int a[], int N, int K)
{
    // reverse last K elements
    reverse(a, N - K, N - 1);

    // reverse first N-K elements
    reverse(a, 0, N - K - 1);

    // reverse the whole array
    reverse(a, 0, N - 1);
}

// Driver code

int main()
{
    int a[7] = {1, 2, 3, 4, 5, 6, 7};

    int K = 3;

    int N = sizeof(a) / sizeof(int);

    // Function Call

    rotate_array(a, N, K);

    for (int i = 0; i < N; i++)
        cout << a[i] << " ";
}
# Program to rotate the given
# array by K positions

# Function for reversing the
# array


def reverse(a, start, end):
    while start < end:
        a[start], a[end] = a[end], a[start]
        start += 1
        end -= 1


# Function to rotate the given
# array by K positions


def rotate_array(a, N, K):
    # reverse last K elements
    reverse(a, N - K, N - 1)

    # reverse first N-K elements
    reverse(a, 0, N - K - 1)

    # reverse the whole array
    reverse(a, 0, N - 1)


# Driver code

a = [1, 2, 3, 4, 5, 6, 7]
K = 3
N = len(a)

# Function Call

rotate_array(a, N, K)

for i in range(N):
    print(a[i], end=" ")



Liked the post?
Editor's Picks
0 COMMENT

Please login to view or add comment(s).