# Array Rotation In-Place

  • Suppose we are given an array of n integers and we have to rotate it by k positions to the left with space complexity of O(1) i.e. within the same array (in-place).
  • If we will shift elements one by one it will become hard to keep tack of all elements without using additional space.

  • So we will divide the array into sets/cycles where the number of sets will depend on the value of n and k.

  • Number of sets = gcd( n, k ) where gcd is greatest common divisor of n & k.

  • And we will shift every element in a set k places to the left by using the formula

    A[j] = A[ ( j + k ) % n]

  • So there will be two nested loops where the outer loop will run for the number of sets and the inner loop with shift elements of a set k positions to the left.

  • Let outer loop be from i=0 to i < gcd(n,k) i.e for the number of sets.

  • Inside the inner loop we will shift the elements k positions to the left for each set i.e starting for i=0.

    1. We will take a variable j for the inner loop and make j = i
    2. We will copy the value of first element of the set in a temporary varivale "temp"
    3. Then we will calculate d = (j + k) % n
    4. And make A[j] = A[d]
    5. Then we will move j to the index of the shifted element by making j = d
    6. And we will repeat the steps 2 to 5 until j == i, i.e. when j == i we will break out of the inner loop.
  • After the inner loop ends we will copy the value in temp at index j i.e A[j] = temp

  • And we will repeat the steps for every set.

  • Suppose we are given this array of 9 elements i.e n=9 and we have to rotate it by 3 positions i.e. k=3.

  • Then gcd of 9 & 3 will be 3, therefore we will divide this array into 3 sets and perform shift operation on elements of each set as follows:

# Source Code - C++

#include <iostream>

using namespace std;

int gcd(int a, int b)
  return a;
  return gcd(b, a%b);

void ArrayRotate (int A[], int n, int k)
 int d=-1,i,temp,j;

void displayArray(int A[],int n)
 int i;
  cout<<A[i]<<" ";

int main()
  int n,i,k;
  cout<<"Enter size of the Array\n";
  int A[n];
  cout<<"Enter Array elements\n";
  cout<<"Enter the value of k\n";
  return 0;

Time Complexity : O(n)

Space Complexity : O(1)

Learn More

  • Array Rotation In-Place