2
\$\begingroup\$

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--;
        }

    }

}
\$\endgroup\$
3
  • 1
    \$\begingroup\$ Drop your switch statement, if you break this down into ASM it will actually be slower than an IF else statement, unless you plan on adding many more cases then keep it. change your reverse method to use a decremented for instead of a while. everything else looks good to me. \$\endgroup\$ – THE AMAZING Apr 21 '16 at 19:28
  • \$\begingroup\$ Thank You, Can you tell me which of these two methods is more efficient ? \$\endgroup\$ – Dhrubojyoti Bhattacharjee Apr 21 '16 at 19:35
  • 1
    \$\begingroup\$ Not enough for a full review, but arrayRotate1 and arrayRotate2 are awful names. The names should indicate what the difference is between them, unless you're just 'trying out' different versions to see which works better for you. \$\endgroup\$ – Mast Apr 21 '16 at 20:20
1
\$\begingroup\$

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();
    }
  }
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.