Block Swap Algorithm or Array Rotation in Java

It is very interesting problem frequently asked in interviews of top IT companies like Google, Amazon, TCS, Accenture, etc. By solving the problem, one wants to check the logical ability, critical thinking, and problem-solving skill of the interviewee. So, in this section, we are going to discuss block swap algorithm and array rotation in Java with different approaches and logic. Also, we will create Java programs for the same.

Array Rotation Example

Input:

int arr[] = {7, 9, 8, 0, 5, 1, 6, 4}, s = 8, d = 2

Output: result[] = {8, 0, 5, 1, 6, 4, 7, 9}

Explanation: s is the size of the input array. d = 2 means we have to rotate the array 2 times. When we rotate the first time, we get

{9, 8, 0, 5, 1, 6, 4, 7}. Now, we rotate the array a second time, and we get the following.

Let's see another example.

Input:

int arr[] = {6, 8, 7, 9, 0, 5, 1, 3, 2, 4}, s = 10, d = 5

Output: result[] = {5, 1, 2, 3, 4, 6, 8, 7, 9, 0}

Explanation: After rotating the array 5 times, we get the following:

{5, 1, 2, 3, 4, 6, 8, 7, 9, 0}, which is our answer.

Block Swap Algorithm

In this section, we have used block swap algorithm to rotate array. Observe the algorithm:

Step 1: Divide the input array into two sub-arrays with div as division point. Let them be A = arr[0 ... div - 1] and B = arr[div ... n - 1].

Step 2: Until the size of A and B are equal, follow the following steps:

1. If the size of A is greater than B, then divide A into two portions, A1 and A2, such that the size of A1 is equal to the size of A2. Swap the sub-arrays A1 and B. It changes the array from A1A2B to BA2A1.
2. If the size of B > A, divide B into two parts, B1 and B2, in such a way that the size of B2 is the same as the size of B. Swap the subarrays A and B2. It changes the array from AB1B2 to B2B1A.

Step 3: When the A and B sizes are equal, swap them.

Approach: Using Recursion

The following program uses the above-mentioned algorithm.

FileName: RotateArray.java

Output:

The input array: 
7 9 8 0 5 1 6 4 
The new array after rotating 2 times, we get
8 0 5 1 6 4 7 9 

The input array: 
6 8 7 9 0 5 1 3 2 4 
The new array after rotating 5 times, we get
5 1 3 2 4 6 8 7 9 0