Thursday, July 14, 2016

Left shift or Rotating an Array

Given an array and a number, rotate the array to the left by given number positions i.e; shift the array elements to the left.
Example: The array [1, 2, 3, 4, 5] after rotating by 3  gives [ 4, 5, 1, 2, 3].

Approach 1:
Use then temporary array to hold elements to shift at the end. Now shift remaining elements to the front. Append elements in temp array to end.

Approach 2:
Shift one element at a time. This way you will have to move all elements till required rotations are not achieved.

Approach 3:
Reverse elements to be shifted first. Then reverse remaining elements in place then reverse the whole array.
Example: 1, 2, 3, 4, 5 rotate left by 3 then
3, 2, 1, 4 ,5 -> Step1
3, 2, 1, 5, 4 -> Step 2
4, 5, 1, 2, 3 -> Step 3 
Below is the code for this approach.
public class ArrayRotation {
    public static void main(String[] args) {
        int[] array = {1, 2, 3, 4, 5};
        int size = array.length;
        int rotations = 3;

        array = rotate(array, 0, rotations - 1);
        array = rotate(array, rotations, size - 1);
        array = rotate(array, 0, size - 1);

        for (int i = 0; i < size; i++)
            System.out.print(array[i] + " ");

    }

    public static int[] rotate(int[] array, int start, int rotation) {
        for (int i = start; i < rotation; i++, rotation--) {
            int temp = array[i];
            array[i] = array[rotation];
            array[rotation] = temp;
        }
        return array;
    }
}

Comments are welcome.

No comments:

Post a Comment