Rotating an array by mentioned digit to rotate

Question

I have developed the program to rotate the array in java request you to please check it and let me know if there are any flaws in it or where further it can be improved

    package com.dataStructures.Arrays;

// Java program for reversal algorithm of array rotation
//Let the array be arr[] = [1, 2, 3, 4, 5, 6, 7], d =2 and n = 7
//        A = [1, 2] and B = [3, 4, 5, 6, 7]
//
//        Reverse A, we get ArB = [2, 1, 3, 4, 5, 6, 7]
//        Reverse B, we get ArBr = [2, 1, 7, 6, 5, 4, 3]
//        Reverse all, we get (ArBr)r = [3, 4, 5, 6, 7, 1, 2]

import java.util.Arrays;

class ArrayRotate {

    static void leftRotate(int[] arr, int d) {

        if (d == 0)
            return;
        int n = arr.length;
        reveresArray(arr, 0, d - 1);
        reveresArray(arr, d, n - 1);
        reveresArray(arr, 0, n - 1);
    }


    static void reveresArray(int[] arr, int start, int end) {
        int temp;
        while (start < end) {
            temp = arr[start];
            arr[start] = arr[end];
            arr[end] = temp;
            start++;
            end--;
        }
    }


    static void printArray(int[] arr) {
        Arrays.stream(arr).mapToObj(item -> item + " ").forEach(System.out::print);
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7};
        int n = arr.length;
        int d = 2;
        leftRotate(arr, d); // Rotate array by d
        printArray(arr);
    }
}

Answer 1

while the solution is functional. it is overly complex. rotation is a simple algorithm of index arithmetic: start with the first cell, with each iteration, you determine the source and destination indexes of one value, move that value into place, take the evicted value and set the next iteration to determine its new place.

so we start with idx 0 and determine its place is at idx 5. in the next iteration we start with idx 5 and determine its new place and so on.

static void leftRotate(int[] arr, int d) {
    int srcIdx, dstIdx;
    srcIdx = 0;
    int val = arr[srcIdx];
    // loop only used to count (i not used as index)
    for (int i = 0; i < arr.length ; i++) {
        dstIdx = srcIdx - d;
        if (dstIdx < 0) dstIdx = arr.length + dstIdx;  // rotate dst idx from start to end of arr
        int temp = arr[dstIdx];
        arr[dstIdx] = val;
        val = temp;  // set next iteration value to move
        srcIdx = dstIdx;  // set next iteration srcIdx
    }
}

also, printArray is redundant. use Arrays.tostring()

EDIT

thanks to @Imus, there is a nasty bug in my "simple" algorithm described above. The bug occurs when the array is divisible by d. in this case, following src-dst-src-dst chain results in processing the same indexes in a loop, while missing other indexes. The solution (that I found) is to detect such cases of "closed-loop" and advance the pointers one cell ahead. admittedly, it does make the solution more complex.

below is a fixed solution.

static void leftRotate(int[] arr, int d) {
    int srcIdx, dstIdx, loopDetectIdx;
    srcIdx = 0;
    loopDetectIdx = 0;  // detects processing in "closed loop" 
    int val = arr[srcIdx];
    for (int i = 0; i < arr.length ; i++) {
        dstIdx = srcIdx - d;
        // rotate dst idx from start to end of arr
        if (dstIdx < 0) dstIdx = arr.length + dstIdx;
        int temp = arr[dstIdx];
        arr[dstIdx] = val;
        System.out.println(srcIdx + "-" + dstIdx + " " + Arrays.toString(arr));
        val = temp;
        srcIdx = dstIdx;
        // if we already processed srcIdx, move all pointers one cell forward  
        if (srcIdx == loopDetectIdx) {
            srcIdx++;
            loopDetectIdx++;
            val = arr[srcIdx];
        }
    }
}

Answer 2

Your implementation looks good. It's an in memory algorithm so space wise you can't do better. Timewise you're looping over each element swapping it twice so that's perfectly fine.

The only remark left to give is the typo in reveresArray -> reverseArray.

It's also possible to print the array using System.out.println(Arrays.toString(arr)); so you don't really need your own method.