4
\$\begingroup\$

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

2 Answers 2

3
\$\begingroup\$

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];
        }
    }
}
\$\endgroup\$
5
  • \$\begingroup\$ You should align d to the length of arr: d %= arr.length;. Else your algorithm fails - and you also optimize the swapping. \$\endgroup\$
    – user73941
    Feb 10, 2020 at 8:44
  • 1
    \$\begingroup\$ @HenrikHansen, good comment. OP should take notice. \$\endgroup\$ Feb 10, 2020 at 9:24
  • \$\begingroup\$ Your solution fails if d is a divisor of arr.length. For example, using arr= new int[]{0, 1, 2, 3} and d=2 it outputs [0, 1, 0, 3] \$\endgroup\$
    – Imus
    Feb 10, 2020 at 13:30
  • \$\begingroup\$ @Imus, thanks. that was a nasty bug indeed. I fixed the proposed solution, however, now it doesn't look as clean and simple as intended (yeah, thanks a lot! :)) \$\endgroup\$ Feb 10, 2020 at 14:14
  • \$\begingroup\$ Interesting solution. I prefer OP's solution for readability though. Without benchmarking I can't say which one would be more efficient though (given that the java compiler will optimise certain things better than others). \$\endgroup\$
    – Imus
    Feb 10, 2020 at 14:27
1
\$\begingroup\$

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.

\$\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.