Rotate array to the left

Question

I am a beginner in programming. To rotate the array to left, I have written the below code. Please point out how to optimize the code and anything I am doing which is not good programming practice.

package arrays;

import java.util.Scanner;

public class ArrayLeftRotation {

    public static int[] LeftRotation(int numberOfLeftRotations, int[] a, int[] b) {

        int n1 = numberOfLeftRotations, n2 = numberOfLeftRotations;
        /*
         * First for loop Given array a0=1,a1=2,a3=4,a4=5,a5=6,a6=7; First we
         * are shifting the first 3 elements to last 3 slots and the array looks
         * like below a0=1,a1=2,a2=3,a3=,a4=1,a5=2,a6=3; The above step we are
         * performing through below logic
         * a[array.length-numberOfLeftRotations]=b[i]; GIVEN ARRAY LENGTH -
         * NUMBER OF LEFT ROTATIONS IS THE STARTING POINT TO MOVE THE FIRST
         * ELEMENTS OF THE ARRAY TO LAST
         */
        for (int i = 0; i < numberOfLeftRotations; i++) {
            a[a.length - n1] = b[i];
            n1--;
        }
        /*
         * Second for loop After executing the above loop the array look like
         * below a0=1,a1=2,a2=3,a3=,a4=1,a5=2,a6=3; now except the last three
         * slots every thing needs to be changed
         * a0=4,a1=5,a2=6,a3=7,a4=1,a5=2,a6=3; we achieved the above array
         * result through below logic a[i]=b[numberOfLeftRotations]; REPLACED
         * THE REMAINING SLOTS WITH THE VALUES STARTING FROM
         * NUMBEROFLEFTROTATIONS
         */
        for (int i = 0; i < a.length - numberOfLeftRotations; i++) {
            a[i] = b[n2];
            n2++;
        }
        return a;
    }

    public static int[] LeftRotation(int numberOfLeftRotations, int[] a) {

        return a;

    }

    public static int[] printArray(int[] a) {

        for (int i = 0; i < a.length; i++) {
            System.out.println(a[i]);
        }
        return a;
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter number of Left Rotations need to be done");
        int l = sc.nextInt();
        System.out.println("Enter number of elements in an array");
        int e = sc.nextInt();
        int[] a = new int[e];

        for (int i = 0; i < a.length; i++) {
            a[i] = sc.nextInt();
        }

        int[] b = a.clone();

        LeftRotation(l, a, b);
        printArray(a);

    }
}

Answer 1

Your class has 4 methods:

1. int[] LeftRotate(int, int[], int[])
2. int[] LeftRotate(int, int[])
3. int[] printArray(int[])
4. void main(String[])

The second method is never called, and can be removed.

The first and third methods (and the second) all return an int[], the a parameter, but the returned values are never assigned to anything. This return value can be removed, and the methods declared to return void.

In the first method, you are looping over increasing i values, decrementing n1, and assigning to a[a.length - n1]. This “double negative” makes the code harder to understand; decrementing n1 increases the destination index value. You already have a i index which in incrementing. You could instead:

for(int i = 0; i < numberOfLeftRotations; i++) {
    a[a.length - numberOfLeftRotations + i] = b[i];
}

This is a little easier to understand; you are only changing i, increasing it, and adding it to a starting point for the destination. We can make it a little clearer:

int dest_start = a.length - numberOfLeftRotations;
for(int i = 0; i < numberOfLeftRotations; i++) {
    a[dest_start + i] = b[i];
}

That is much more understandable. Do the same for the second loop.

---

The above is just a cleanup of your existing code. We can restructure / refactor the code to make it better and easier to use.

When you want to left-rotate an array, you always need to create a new array for the destination. You can make the left-rotate function create the destination array for the caller.

int[] LeftRotate(int numberOfLeftRotations, int[] source) {
    int[] dest = new int[source.length];
    // ... copy rotated version from dest into source
    return dest;
}

And use it as:

int[] b = LeftRotation(l, a);

In fact, this is probably what was intended for your second method. The code to copy the rotated version from dest to source could just be a call of the first “helper” method:

int[] LeftRotate(int numberOfLeftRotations, int[] source) {
    int[] dest = new int[source.length];
    LeftRotate(numberOfLeftRotations, dest, source);
    return dest;
}

Your first method should still be void, as it is not returning anything that wasn’t just passed to it.

---

Copying sequential elements from one array to another is a common operation, and Java provides a method which does just that: System.arraycopy(). Using this, your left rotation can be performed very efficiently in two statements:

System.arraycopy(source, 0, dest, dest.length - numberOfLeftRotations, numberOfLeftRotations);
System.arraycopy(source, numberOfLeftRotations, dest, 0, dest.length - numberOfLeftRotations);

---

Use better variable names. a and b are unclear; source and dest give context to the reader. numberOfLeftRotations is a very descriptive, but it is perhaps a little long. numLeftRotations is just as clear and doesn’t result in lines becoming excessively long. numRotations or rotations might be even better; the reader would know they are left rotations, because the variables are contained within a “left rotate” function.

Convention is for only Class names to begin with upper case letters; method names should not. You should name the method leftRotate, not LeftRotate.

Answer 2

@AJNeufeld's Answer covers all of the logical review quite effectively, but I would like to add a note on your naming schemes.

As it stands calling your current code would look something like:

ArrayLeftRotation.LeftRotation(source, /*some number*/a)

It would be significanly more succinct to rename the Class from ArrayLeftRotation to RotateArray or even Rotate, and the simply rename your LeftRotation method left() (using lowercase method names as mentioned in above answer)

Your new call looks much cleaner as:

Rotate.left(source, /*some number*/ a)

This also offers a built in symmetry should you extend the code to rotate the opposite direction, as such a call would be similar: Rotate.right()

Answer 3

A rotation is a modular arithmic operation.

The congruent value of any number n is (n % size + size) % size.

public static int[] LeftRotation(int numberOfLeftRotations, int[] a, int[] b) {
        int n1 = numberOfLeftRotations, n2 = numberOfLeftRotations;
        for (int i = 0; i < numberOfLeftRotations; i++) {
            a[a.length - n1] = b[i];
            n1--;
        }
        for (int i = 0; i < a.length - numberOfLeftRotations; i++) {
            a[i] = b[n2];
            n2++;
        }
        return a;
    }

So the above code could be rewritten as below to allow for:

1. both left and right rotations with k number of rotations
2. both positive and negative rotations (left and right rotations are complements)
3. rotations with k > source.length

code

    public class Rotate
    {
        public static <T> T[] leftFrom(T[] source, int k)
        {
            if (source == null)
                throw new IllegalArgumentException("source");
            @SuppressWarnings("unchecked")
            T[] target = (T[]) new Object[source.length];
            if (target.length == 0) return target;
            for (int i = 0; i < target.length; i++)
            {
                target[i] = source[mod(i + k, target.length)];
            }
            return target;
        }

        public static <T> T[] rightFrom(T[] source, int k)
        {
            if (source == null)
                 throw new IllegalArgumentException("source");
            @SuppressWarnings("unchecked")
            T[] target = (T[]) new Object[source.length];
            if (target.length == 0) return target;
            for (int i = 0; i < target.length; i++)
            {
                target[i] = source[mod(i - k, target.length)];
            }
            return target;
        }

        public static <T> void left(T[] source, int k)
        {
            T[] target = leftFrom(source, k);
            System.arraycopy(target, 0, source, 0, target.length);
        }

        public static <T> void right(T[] source, int k)
        {
            T[] target = rightFrom(source, k);
            System.arraycopy(target, 0, source, 0, target.length);
        }

        private static int mod(int a, int n)
        {
            assert n > 0;
            return (a % n + n) % n;
        }
    }

Examples

        import java.lang.reflect.Array;
        import java.util.Arrays;

        public void Examples()
        {
            Integer[] source = new Integer[] { 0, 1, 2 };

            // rotate left
            areEqual(new[] { 0, 1, 2 }, Rotate.leftFrom(source, 0));
            areEqual(new[] { 1, 2, 0 }, Rotate.leftFrom(source, 1));
            areEqual(new[] { 2, 0, 1 }, Rotate.leftFrom(source, 2));
            areEqual(new[] { 0, 1, 2 }, Rotate.leftFrom(source, 3));
            // rotate left overflow (k ~ k % source.length)
            areEqual(new[] { 1, 2, 0 }, Rotate.leftFrom(source, 4));
            // rotate left retrograde (rotate left k ~ rotate right (-k))
            areEqual(new[] { 2, 0, 1 }, Rotate.leftFrom(source, -1));

            // rotate right
            areEqual(new[] { 0, 1, 2 }, Rotate.rightFrom(source, 0));
            areEqual(new[] { 2, 0, 1 }, Rotate.rightFrom(source, 1));
            areEqual(new[] { 1, 2, 0 }, Rotate.rightFrom(source, 2));
            areEqual(new[] { 0, 1, 2 }, Rotate.rightFrom(source, 3));
            // rotate right overflow (k ~ k % source.length)
            areEqual(new[] { 2, 0, 1 }, Rotate.rightFrom(source, 4));
            // rotate right retrograde (rotate right k ~ rotate left (-k))
            areEqual(new[] { 1, 2, 0 }, Rotate.rightFrom(source, -1));

            // rotate and assign
            areEqual(new[] { 0, 1, 2 }, source); // unchanged so far
            Rotate.left(source, 1);
            areEqual(new[] { 1, 2, 0 }, source);
            Rotate.right(source, 1);
            areEqual(new[] { 0, 1, 2 }, source);
        }

        static void areEqual(int[] a, int[] b)
        {
            assert Arrays.equals(a, b);
        }