1
\$\begingroup\$

I tried to solve this Left Rotation problem on HackerRank. My code works out for most test cases, but for some it doesn't, probably because they have large number of data. So there seems to be some optimization or performance issue in my code, and I can't really figure out how to fix it. Any help will be greatly appreciated :)

public class Solution {

    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) {
        String[] nd = scanner.nextLine().split(" ");
        int c;
        int n = Integer.parseInt(nd[0]);

        int d = Integer.parseInt(nd[1]);

        int[] a = new int[n];

        int arr[] = new int[n];

        String[] aItems = scanner.nextLine().split(" ");
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

        for (int i = 0; i < n; i++) {
            int aItem = Integer.parseInt(aItems[i]);
            a[i] = aItem;
        }

        scanner.close();

        for (int k=1;k<=d;k++) {
            for (int j=0;j<n;j++) {
                if (j==n-1) 
                { c=0;}
                else 
                { c=j+1;}
                arr[j]=a[c];
            }
            System.arraycopy(arr, 0, a, 0, n);
        }

        for (int j=0;j<n;j++) {
            System.out.print(arr[j]+ " ");
        }
    }
}
\$\endgroup\$
2
\$\begingroup\$
        String[] nd = scanner.nextLine().split(" ");
        int c;
        int n = Integer.parseInt(nd[0]);

        int d = Integer.parseInt(nd[1]);

First, why declare c here? You don't use it until much later. So let's take it out of here and define it closer to its first use. I would also rename it, as I find c insufficiently descriptive.

Second, why use nextLine this way? Consider

        int numbersCount = scanner.nextInt();
        int rotationCount = scanner.nextInt();

I don't know that this is any faster, but it's more direct in code.

I would also add

        rotationCount %= numbersCount;

You could do this in the declaration, but I find it more readable separate.

What this does is remove any superfluous rotations. If we are rotating numbersCount times exactly, we're already done. Because that's just the original array. By taking the modulus or remainder, we're getting rid of all those full cycle rotations. Since that's just wasted time, this purely improves those large rotations at the expense of an extra division for all rotations.

        int[] numbers = new int[numbersCount];
        for (int i = 0; i < numbers.length; i++) {
            numbers[i] = scanner.nextInt();
        }

Again, I wouldn't use nextLine here. The scanner is perfectly capable of this. If you want to read line by line, consider going to something like a BufferedReader that works that way.

You have

                if (j==n-1) 
                { c=0;}
                else 
                { c=j+1;}
                arr[j]=a[c];

So we finally find c. It's the index into the old array. But it could have been more readably written

                int originalIndex = (j + 1 == numbers.length) ? 0 : j + 1;

or

                int originalIndex = j + 1;
                if (originalIndex == numbers.length) {
                    originalIndex = 0;
                }

And whatever you do, please don't do things like {c=0;}. It's hardly any shorter. It's just different. Unless different indicates something, it's not helpful.

But I would actually skip the rotation. Instead, break the output into two pieces:

        for (int i = rotationCount; i < numbers.length; i++) {
            System.out.print(numbers[i] + " ");
        }

        for (int i = 0; i < rotationCount; i++) {
            System.out.print(numbers[i] + " ");
        }

This will display the output as rotated without rotating.

Or just read it rotated.

        int rotationPoint = numbers.length - rotationCount;
        for (int i = rotationPoint; i < numbers.length; i++) {
            numbers[i] = scanner.nextInt();
        }

        for (int i = 0; i < rotationPoint; i++) {
            numbers[i] = scanner.nextInt();
        }

Then the output could be something like

        System.out.println(String.join(" ", numbers));

There's no need to rotate at all, much less to rotate one at a time.

class Solution {

    public static void main(String[] args) {
        System.out.println(String.join(" ", readInputRotated());
    }

    public static int[] readInputRotated() {
        try (Scanner scanner = new Scanner(System.in)) {
            int[] rotated = new int[scanner.nextInt()];

            int rotationPoint = rotated.length - scanner.nextInt();
            for (int i = rotationPoint; i < rotated.length; i++) {
                rotated[i] = scanner.nextInt();
            }

            for (int i = 0; i < rotationPoint; i++) {
                rotated[i] = scanner.nextInt();
            }

            return rotated;
        }
    }

}

This also uses the try-with-resources form to manage the Scanner lifecycle without explicitly calling close.

Your original code was \$\mathcal{O}(mn)\$ where \$m\$ and \$n\$ are the number of rotations and the input size. This is \$\mathcal{O}(n)\$ (because you read the input) and the "rotation" is \$\mathcal{O}(1)\$.

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