Problem
I have started learning Java and was trying to solve some easy problems from different websites like HackerRank and leetcode.I am relatively new to programming so please don’t mind if this is too naive. I found a problem in LeetCode to rotate array.The problem can be found here
I have implemented the solution using two different methods:
The first method(my initial solution) rotateArray1 is very straightforward where we divide the array into two parts and then copy the elements back into the main array.
I found the logic for the second method in programcreek which says :
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
This is my solution where I implemented both the methods.I am trying to get better at writing good code for my solutions. Please give me your suggestions and also can anyone please tell me which one of these two methods is more efficiant in terms of time complexity.
import java.util.Scanner;
/*Problem: 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]. */
public class RoatateArray {
public static Scanner Keyboard = new Scanner(System.in);
public static void main(String[] args) {
int size = Keyboard.nextInt();
int[] array = new int[size];
fillArray(array);
System.out.println("Array before rotation is :");
printArray(array);
System.out
.println("nEnter the number of steps the array needs to be rotated");
int order = Keyboard.nextInt();
if (order == array.length) {
System.out
.println("The order of the array will be same after rotation of "
+ order + "steps");
} else {
System.out
.println("enter choice 1 : arrayRotate1 or choice 2 for : arrayrotate2");
int choice = Keyboard.nextInt();
switch (choice) {
case 1:
arrayRotate1(array, order);
break;
case 2:
arrayRotate2(array, order);
break;
default:
break;
}
}
}
private static void arrayRotate1(int[] array, int order) {
if (order > array.length) {
order = order % array.length;
}
int[] arr1 = new int[order];
int[] arr2 = new int[array.length - order];
System.arraycopy(array, array.length - order, arr1, 0, arr1.length);
System.arraycopy(array, 0, arr2, 0, arr2.length);
// copy arr1 and arr2 into original array
System.arraycopy(arr1, 0, array, 0, arr1.length);
System.arraycopy(arr2, 0, array, arr1.length, array.length - order);
printArray(array);
}
private static void printArray(int[] array) {
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + " ");
}
}
private static int[] fillArray(int[] array) {
for (int i = 0; i < array.length; i++) {
array[i] = Keyboard.nextInt();
}
return array;
}
private static void arrayRotate2(int[] array, int order) {
if (order > array.length) {
order = order % array.length;
}
// get the length of the first part
int a = array.length - order;
reverse(array, 0, a - 1);
reverse(array, a, array.length - 1);
reverse(array, 0, array.length - 1);
printArray(array);
}
private static void reverse(int[] array, int left, int right) {
while (left < right) {
int temp = array[left];
array[left] = array[right];
array[right] = temp;
left++;
right--;
}
}
}
Solution
If you use ArrayList instead of int[] you can write rotate2 like this (it’s less efficient):
public static List<Integer> rotate2(List<Integer> numsList, int k) {
k = k % numsList.size();
List<Integer> firstPart = numsList.subList(0, numsList.size() - k);
List<Integer> secondPart = numsList.subList(numsList.size() - k, numsList.size());
Collections.reverse(firstPart);
Collections.reverse(secondPart);
ArrayList<Integer> rotated = new ArrayList<>();
rotated.addAll(firstPart);
rotated.addAll(secondPart);
return rotated;
}
The arrayRotate1 can also be written this way, I don’t know whether it’s more readable or not but it’s definitely less efficient:
public static void rotate(int[] nums, int k) {
k = k % nums.length;
Queue<Integer> queue = new ArrayDeque<>(k);
for (int i = 0; i < Math.min(k, nums.length); i++) queue.add(nums[i]);
for (int i = 0; i < nums.length; i++) {
int index = (i + k) % nums.length;
queue.add(nums[index]);
nums[index] = queue.remove();
}
}