Rotate an array by K positions

In this tutorial, we will see how to rotate an array be K positions.

Problem:

N=6 and k=2
If Arr[] = {1, 2, 3, 4, 5, 6} and k=2
then [rotated array](https://java2blog.com/search-element-in-sorted-and-rotated-array-java/ “rotated array”) will be  {5, 6, 1, 2,  3,  4}

Solution:

There are multiple ways to solve this problem.

Approach 1:

Move each number by 1 place and do it k times.

Time complexity: o(n*k)
Where n is number of elements and k denotes position shift.
Space complexity: o(1)

Approach 2:

You can rotate the array using temp array in o(n).

Time complexity: o(n)
Space complexity: o(n)

Approach 3:

This is the most optimized approach.
Algorithm for this approach works as below:

  • Reverse whole array.
  • Reverse first k elements
  • Reverse rest n-k elements.
For example:
let’s say Array is {1,2,3,4,5,6,7,8}
You want to rotate by k position.
It will work as below:
  • You rotate the whole array. So array became: {8,7,6,5,4,3,2,1}
  • Reverse first k elements, so array became : {7,8,6,5,4,3,2,1}
  • Reverse rest of elements, so array became  : {7,8,1,2,3,4,5,6}
Java code:
Time complexity: o(n)
Space complexity: o(1)

Complete Java program to rotate array by K positions:

When you run above program, you will get below output:

Was this post helpful?

Leave a Reply

Your email address will not be published. Required fields are marked *