HackerEarth: Find array index with cumulative sum till there matching a given target

Question

The problem was like this:

Given an array:

[1, 2, 1, 3, 4]

where each index value shows the production of that particular day. So, at index 0, production is 1, index 1 - production is 2, so on...

Then we're given some targets (N numbers of them). For a given target T, we've to find the index till which the cumulative production matches the target.

For e.g., a target of 4 will be achieved by index 2 (1 + 2 + 1 = 4 >= 4). Similarly, a target of 10 will be achieved by index 4 (1 + 2 + 1 + 3 + 4 = 11 >= 10). Basically, the target is achieved for index i, if cumulative sum till that index is greater than target. We've find the minimum index for each target.

For the above array, sample input and output would be:

4, 2, 10
2, 1, 4

My idea for the problem is: While reading the array as input, I pre-process the array to store cumulative at each index. So, I'll convert the above array to:

[1, 3, 4, 7, 11]

and then for the given target, I'll find the minimum value in array greater than that target (can easily be done using binary search).

Assuming the total number of targets input is Q and size of initial array is T, my algorithm would be O(Qlog(T)), which seems to be quite fine. But, it failed with TLE for input #5 on hackerearth.

Then I thought of maintaining a target cache (Map<Long, Integer>), which I'll populate after reading each array element. That map will store the index of each possible target till the maximum value.

For the above array, the map which I build would be like:

{1=0, 2=1, 3=1, 4=2, 5=3, 6=3, 7=3, 8=4, 9=4, 10=4, 11=4}

So, for each target, I can just do map.get(target), to get the index. For this solution, pre-processing numbers, and building map should be O(maxTarget), where maxTarget is the maximum value a target can get. And then fetching result is just O(1). But again, this also failed with TLE.

I'm completely out of thought to modify this to make the last input pass. Here's my code for 2nd approach (map):

public static void main(String[] args) throws Exception {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String line = br.readLine();
    int T = Integer.parseInt(line);

    String input = br.readLine();
    StringTokenizer tokenizer = new StringTokenizer(input, " ");

    long[] numbers = new long[T];
    Map<Long, Integer> targetCache = new HashMap<Long, Integer>();

    int i = 0;
    while (tokenizer.hasMoreTokens()) {
        int nextTarget = Integer.parseInt(tokenizer.nextToken());
        long previousTarget = i == 0 ? 0 : numbers[i - 1];
        numbers[i] = previousTarget + nextTarget;
        long currentCumulativeTarget = numbers[i];
        for (long j = previousTarget + 1; j <= currentCumulativeTarget; j++) {
            targetCache.put(j, i);
        }
        i++;
    }
    System.out.println(targetCache);

    int Q = Integer.parseInt(br.readLine());
    for (int x = 0; x < Q; x++) {
        long target = Long.parseLong(br.readLine());
        Integer index = targetCache.get(target);
        // If target can't be matched, print -1
        System.out.println(index == null ? -1 : index);
    }
}

How can the above solution be optimized further? Any leads? BTW, I can't test the solution, as that was the part of a interview test, and I can't see that question again.

Answer 1

With Java performance it is important to create methods other than the main method. Java compilation is method-based, and it often relates to how often the method is called. Since the main method is only called once, it is seldom optimized very well.

In addition to that, Java println is also slow, as it requires access to the console, and it is synchronizes, and flushes it. As a result, many println calls are also slower than fewer larger printlns. So, batch up your output as much as you can.

All in all, create methods, batch the output, and .... use a binary search. Then, use some useful Java native methods. Split is a good one, and also try-with-resources for the input streams. With the format of your input, a Scanner may be simpler too....

private static int[] readInts(Scanner scanner) {
    int size = scanner.nextInt();
    int[] values = new int[size];
    for (int i = 0; i < size; i++) {
        values[i] = scanner.nextInt();
    }
    return values;
}

private static void accumulateValues(int[] values) {
    for (int i = 1; i < values.length; i++) {
        values[i] += values[i - 1];
    }
}

public static void main(String[] args) {
    try (Scanner scanner = new Scanner(System.in)) {
        int[] values = readInts(scanner);
        accumulateValues(values);
        int[] searches = readInts(scanner);
        int[] results = new int[searches.length];
        for (int i = 0; i < searches.length; i++) {
            results[i] = Arrays.binarySearch(values, searches[i]);
            if (results[i] < 0) {
                results[i] = -results[i] - 1;
            }
        }
        StringBuilder sb = new StringBuilder();
        for (int r : results) {
            sb.append(r).append("\n");
        }
        System.out.println(sb.toString());
    }
}