Scribd
Upload
48 views

Solution 1 - Intermediate Array: Rotate Array in Java

Rotate Array in Java

Uploaded by

adamfunk
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
48 views

Solution 1 - Intermediate Array: Rotate Array in Java

Rotate Array in Java

Uploaded by

adamfunk
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 1

Home Java Examples Python Examples C++ Examples Scala Examples Coding Interview Simple Java Contact

Rotate Array in Java


Category: Algorithms >> Interview >> Java March 6, 2015

Rotate an array of n elements to the right by k steps.

For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4]. How many different
ways do you know to solve this problem?

Solution 1 - Intermediate Array


In a straightforward way, we can create a new array and then copy elements to the new array. Then change
the original array by using System.arraycopy().

public void rotate(int[] nums, int k) {


if(k > nums.length)
k=k%nums.length;

int[] result = new int[nums.length];

for(int i=0; i < k; i++){


result[i] = nums[nums.length-k+i];
}

int j=0;
for(int i=k; i<nums.length; i++){
result[i] = nums[j];
j++;
}

System.arraycopy( result, 0, nums, 0, nums.length );


}

Space is O(n) and time is O(n). You can check out the difference between System.arraycopy() and
Arrays.copyOf().

Solution 2 - Bubble Rotate


Can we do this in O(1) space?

This solution is like a bubble sort.

public static void rotate(int[] arr, int order) {


if (arr == null || order < 0) {
throw new IllegalArgumentException("Illegal argument!");
}

for (int i = 0; i < order; i++) {


for (int j = arr.length - 1; j > 0; j--) {
int temp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = temp;
}
}
}

However, the time is O(n*k).

Here is an example (length=7, order=3):

i=0
0 1 2 3 4 5 6
0 1 2 3 4 6 5
...
6 0 1 2 3 4 5
i=1
6 0 1 2 3 5 4
...
5 6 0 1 2 3 4
i=2
5 6 0 1 2 4 3
...
4 5 6 0 1 2 3

Solution 3 - Reversal
Can we do this in O(1) space and in O(n) time? The following solution does.

Assuming we are given {1,2,3,4,5,6} and order 2. The basic idea is:

1. Divide the array two parts: 1,2,3,4 and 5, 6


2. Reverse first part: 4,3,2,1,5,6
3. Reverse second part: 4,3,2,1,6,5
4. Reverse the whole array: 5,6,1,2,3,4

public static void rotate(int[] arr, int order) {


if (arr == null || arr.length==0 || order < 0) {
throw new IllegalArgumentException("Illegal argument!");
}

if(order > arr.length){


order = order %arr.length;
}

//length of first part


int a = arr.length - order;

reverse(arr, 0, a-1);
reverse(arr, a, arr.length-1);
reverse(arr, 0, arr.length-1);

public static void reverse(int[] arr, int left, int right){


if(arr == null || arr.length == 1)
return;

while(left < right){


int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
left++;
right--;
}
}

References:
1. Programming Pearls

Related Posts:
1. LeetCode – Next Permutation (Java)
2. LeetCode – 4Sum (Java)
3. LeetCode – Sort Colors (Java)
4. LeetCode – Rotate Image (Java)

Category >> Algorithms >> Interview >> Java

If you want someone to read your code, please put the code inside <pre><code> and </code></pre> tags. For
example:
<pre><code>
String foo = "bar";
</code></pre>

Copyright © 2010 - 2021 Program Creek

You might also like