HackRank - Array Rotate Optimization

Question

I am working on a basic Array rotate code for a Hacker Rank challenge. The code is complete and passes all test cases, except for 2 which it times out on. I was wondering if there is a way to make this code more efficient. Thank you in advance.

class Result {

    /*
     * Complete the 'rotLeft' function below.
     *
     * The function is expected to return an INTEGER_ARRAY.
     * The function accepts following parameters:
     *  1. INTEGER_ARRAY a - List Array
     *  2. INTEGER d - Number of times to be retated
     */

    public static List<Integer> rotLeft(List<Integer> a, int d) {
        // Write your code here
        int lowestVal;
        int size = a.size()-1;
        for (int x = 0; x < d; x++)
        {
            lowestVal = a.get(0);
            for (int i = 0; i < size; i++)
            {
                a.set(i, a.get(i+1));
            }
            a.set(size, lowestVal);
        }
        return a;
    }

}

Answer 1

You should not need to do this yourself. Consider

d %= a.size();
if (d == 0) {
    return a;
}

List<Integer> results = new ArrayList<>();
results.addAll(a.subList(d, a.size()));
results.addAll(a.subList(0, d));

return results;

If d is initially 0, it will rotate in constant time. This is the same as your function.

If d becomes 0 (when d is a multiple of a.size()), it will still rotate in constant time. Whereas your function will rotate d times to get back the original list.

If d is 1, this will copy each element of the list once. This is the same as your function.

If d is greater than 1 and not evenly divisible by a.size(), this will copy each element of the list once. Whereas your function will copy each element d times. So d * a.size() copies. This is a particularly large improvement when d is greater than a.size().

Behind the scenes, this does the same work as one of your for loops. But you don't have to operate it manually. And you don't have to nest with another for loop.

Answer 2

Is it a list or an array you are to work with? They are not exactly equivalent. If the data is an array, you can perhaps use System.arrayCopy() in your solution.

Do you have to rotate in place or can the result be a new array (or list)?

If you are rotating more than one place, you should be able to do so in one go, rather than multiple single-place rotations, which will improve performance significantly.

Answer 3

The term "list array" is inapproriate (it's generally understood to mean an array of lists).

What you're doing is rotating left (by a distance of 1) d times, while it would be more elegant (and efficient) to rotate left (by a distance of d) just 1 time. Also, in the process you're changing your input (parameter a). That's not always evil, but it is in your case since the lack of mentioning that (in the documentation of the function) makes callers not expect that.

Here's an nicer version using high-level calls only:

public static List<Integer> rotLeft(List<Integer> a, int d) {
    d %= a.size();
    if (d < 0) d += a.size();
    List<Integer> newPrefix = a.subList(d, a.size());
    List<Integer> newPostfix = a.subList(0, d);
    List<Integer> result = new ArrayList<>(a.size());
    result.addAll(newPrefix);
    result.addAll(newPostfix);
    return result;
}

If creating newPrefix and newPostfix seems inefficient: there're just views so don't worry about that.

PS: returning a itself (rather than a copy) if d==0 may seem like a good idea, but it is inadvisable unless you're in complete control of your callers. If there are external callers they'd be able to mess up your original list at any time.