Java – An efficient way to cycle an array left n positions using only a single one-dimensional array.

An efficient way to cycle an array left n positions using only a single one-dimensional array…. here is a solution to the problem.

An efficient way to cycle an array left n positions using only a single one-dimensional array.

Given an array containing n integers and a number d, a left rotation is performed on the array. Given the example of array [1,2,3,4,5], the shift will always be <= size of the array and ask for shift 1, then the output will be -> [2,3,4,5,1]. I wrote the code below and it works fine, can it be optimized further because my time complexity is O(n^2).

Code:

public static int[] arrayLeftRotation(int[] a, int n, int k) {

    if (n == 1 || n == k)
        return a;
    else {
        int track = 0;
        while (track < k) {
            int start = a[0];
            for (int i = 0; i < n - 1; i++) {
                a[i] = a[i + 1];
            }
            a[n - 1] = start;
            track++;
        }

return a;
    }

}

Solution

There is a clever trick in O(n) to do this in place time:

  • invert the entire array (i.e. between indices 0 (inclusive) and n (exclusive)’;
  • Inverts the array parts between 0 (inclusive) and (n-k) (exclusive).
  • Inverts the array parts between indexes (n-k) (inclusive) and n (exclusive).

(This assumes 0 <= k <= n; If this is not the case, simply find a different value of k to a value that produces an equivalent rotation according to the above, such as k = k % n if k >= 0

).

Each reversal operation is O(n), there are 3, so O(n) is still comprehensive. Inverting arrays in place is also easy, so there is no additional memory overhead.

Related Problems and Solutions