current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
up vote 2 down vote favorite
2

I have a solution to the HackerRank Circular Array Rotation challenge. It passes 7 test cases out of 15. The rest of them are getting timed out. I think it's because of the huge data set that has been given as the input.

Input Format

The first line contains 3 space-separated integers, n (the length of the array), k (the number of right circular rotations), and q (the number of queries).
The second line contains n space-separated integers a0, a1, a2, …, an-1.
Each of the q subsequent lines contains a single integer denoting m. For each of those queries, output am of the rotated array.

Constraints

  • 1 ≤ n ≤ 105
  • 1 ≤ ai ≤ 105
  • 1 ≤ k ≤ 105
  • 1 ≤ q ≤ 500

Can you point me out how can I improve this code in order to avoid those time out of test cases?

public class CircularArrayRotation {

    public static int[] circularArray(int[] beforeArray){
            int[] afterArray = new int[beforeArray.length];
            afterArray[0] = beforeArray[beforeArray.length-1];
            System.arraycopy(beforeArray,0,afterArray,1,beforeArray.length-1);
            return afterArray;
    }


    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int k = sc.nextInt();
        int q = sc.nextInt();
        sc.nextLine();
        int[] source = new int[n];
        String[] elements = sc.nextLine().split(" ");
        for (int i=0;i<elements.length;i++){
            source[i] = Integer.parseInt(elements[i]);
        }
        source = repeatCirculating(source,k);
        int[] ques = new int[q];
        for (int i=0;i<q;i++){
            int position = Integer.parseInt(sc.nextLine().trim());
            ques[i] = position;
        }
        for (int ask:ques) {
            System.out.println(source[ask]);
        }

    }

    public static int[] repeatCirculating(int[] source, int times){
        for (int i =0; i<times; i++){
            source = circularArray(source);
        }
        return  source;
    }
}
share|improve this question
up vote 6 down vote accepted

The array may be up to 105 elements long. If you actually perform the rotation, then you will be copying at least 105 elements. (You actually do ridiculously more work, as @JoeC and @OhadR have both pointed out.)

However, there will be at most 500 queries. It would be nice if you didn't have to modify 105 entries just to satisfy 500 queries. You don't actually need to perform the rotation — you only need to pretend to have performed the rotation.

import java.util.Scanner;

public class CircularArrayRotation {
    /**
     * Performs one query.
     *
     * @param a  The original array
     * @param k  The number of right circular rotations
     * @param m  The index of the rotated array to retrieve
     */
    public static <T> T query(T[] a, int k, int m) {
        int n = a.length;
        return a[(((m - k) % n) + n) % n];
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt(), k = sc.nextInt(), q = sc.nextInt();
        sc.nextLine();                          // End of first line

        String[] a = sc.nextLine().split(" ");  // Second line

        while (q-- > 0) {                       // Perform q queries
            System.out.println(query(a, k, sc.nextInt()));
        }
    }
}

Strictly speaking, you don't even need to parse the ai as integers — you just need to read and regurgitate them. You also don't need to store all q queries — you can just reply to each one as soon as you read m.

share|improve this answer
    
nice one, but you did not shift anything... it answers the question perfectly but im not sure this is what they really meant :) – OhadR Oct 30 '16 at 9:06
1  
Could you please elaborate on this (((m - k) % n) + n) % n expression? – Jude Oct 30 '16 at 9:06
2  
@OhadR It's a common pattern in computer science: many problems can be solved by adding a layer of indirection. When you fork a process, for example, you don't copy the memory, you do copy-on-write. Same principle applies here. – 200_success♦ Oct 30 '16 at 9:08
2  
@Jude a[m-k] is the basic expression. a[(m-k) % n] ensures that the index is between -n and n. a[(((m-k) % n) + n) % n] ensures that the index is between 0 and n. – 200_success♦ Oct 30 '16 at 9:10
    
you got a +1 from me :) – OhadR Oct 30 '16 at 9:12
up vote 1 down vote

If k == 1_000_000, then you will be performing 1,000,000 rotations of 1. Try 1 rotation of 1,000,000 instead.

share|improve this answer
    
I am using System.arrayCopy() which is a native method and I thought it would be faster than shifting the elements in the input array – Jude Oct 30 '16 at 9:08
    
It is... if you only call it once. – Joe C Oct 30 '16 at 17:36
up vote 1 down vote

allocation of new array each and every time is very very expensive. instead, try shifting the items in the same input array. I've pasted here only the function the moves the items:

public static int[] circularArray(int[] input)
{
    int tmp = input[input.length-1];
    for(int i = input.length-1; i > 0; --i)
    {
        input[i] = input[i-1];
    }
    input[0] = tmp;
    return input;
}
share|improve this answer
up vote 1 down vote 
        int[] source = new int[n];
        String[] elements = sc.nextLine().split(" ");
        for (int i=0;i<elements.length;i++){
            source[i] = Integer.parseInt(elements[i]);
        }
        source = repeatCirculating(source,k);

You are copying the entire array here. Do the rotation in the copy and you save the overhead of rotating. 

        String[] elements = sc.nextLine().split(" ");
        int[] source = new int[elements.length];
        for (int i = 0; i + k < source.length; i++) {
            source[i + k] = Integer.parseInt(elements[i]);
        }

        for (int i = 0, j = source.length - k; i < k; i++) {
            source[i] = Integer.parseInt(elements[j + i]);
        }

I switched the order of the array declarations. This ensures that they have the same number of elements.

But we can actually do better. Note that this never uses n and converts to and from an integer without ever using the value as an integer. 

        String[] elements = new String[n];
        for (int i = k; i < elements.length; i++) {
            elements[i] = sc.next();
        }

        for (int i = 0; i < k; i++) {
            elements[i] = sc.next();
        }

Now we can just print out the element as a string. We don't have to convert from an integer to print it. And we have everything in its proper place without doing any copies. We read each element into its proper place directly.

This also avoids converting the request to match the actual index locations, which would add a small amount of overhead to each request. At the cost of one extra for loop, this has no overhead not present in the original.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.