1
\$\begingroup\$

I am working on this problem: https://www.hackerrank.com/challenges/determining-dna-health/problem passing some test cases and time-out on others (no wrong answers).

The code is here:

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;

public class Solution {

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

    public static void main(String[] args) {
        int n = scanner.nextInt();
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

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

        Map<Integer, String> genes = new HashMap<>();
        for (int i = 0; i < n; i++) {
            genes.put(i, genesItems[i]);
        }

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

        Map<Integer, String> health = new HashMap<>();
        for (int i = 0; i < n; i++) {
            health.put(i, healthItems[i]);
        }

        int s = scanner.nextInt();
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

        long min = Long.MAX_VALUE;
        long max = Long.MIN_VALUE;

        for (int sItr = 0; sItr < s; sItr++) {
            String[] firstLastd = scanner.nextLine().split(" ");

            int first = Integer.parseInt(firstLastd[0]);
            int last = Integer.parseInt(firstLastd[1]);
            String d = firstLastd[2];

            long sum = 0;
            for (int i = first; i <= last; i++) {
                for (int index = d.indexOf(genes.get(i)); index >= 0; index = d.indexOf(genes.get(i), index + 1)) {
                    sum += Integer.parseInt(health.get(i));
                }
            }
            if (sum < min) {
                min = sum;
            }
            if (sum > max) {
                max = sum;
            }
        }

        System.out.println(min + " " + max);
        scanner.close();
    }
}
\$\endgroup\$
2
\$\begingroup\$

The Algorithm

This has a bad worst-case complexity,

for (int i = first; i <= last; i++) {
    for (int index = d.indexOf(genes.get(i)); index >= 0; index = d.indexOf(genes.get(i), index + 1)) {
        sum += Integer.parseInt(health.get(i));
    }
}

Consider a strand "aaaaaaaaaaaaaaaaaaaaaaa" and genes {"aaaaa", "aaaaa" ...

Now for every gene, at almost every position of the strand, there will be a string comparison. The amount of character comparisons is approximately TotalSize(genes) * strand.length, so that can easily lead to a TLE if the data is a little annoying, which of course it will be.

Here are a couple of other techniques you could try,

  • Building a suffix array and LCP array for the strand, so for every gene the number of occurrences in the strand can be counted in O(geneLength + log strandLength) (so without even visiting the occurrences!) by binary-searching for the start and end of the contiguous range in the SA that contains all those occurrences. A suffix trie is good as well but more dangerous for the memory footprint. SA and suffix trie can both be constructed in linear time (in the length of the string), but it is non-trivial to implement. The LCP array can be given as a secondary result of SA construction (depending on the algorithm) or otherwise created in linear time as well by using the SA.
  • Building a trie with the healthy genes, then go over the strand while descending down the trie, backing up as needed. This has a bunch of edge-cases that need to be considered. There are slow cases, for example if a gene is very big (half the length of the strand) and matches nearly everywhere (for example if the strand and gene are both only the same character), which I think is still a quadratic case. Some additional trickery may be able to work around that.

The solutions that I could find quickly seemed to use the second approach, but I think the first one would be a "safer" choice in terms of avoiding a quadratic worst-case complexity, though the second one seems useful enough in practice (it has been successfully used, after all).

Unnecessary Map

When the keys of a map are a dense and non-changing range of integers like this,

Map<Integer, String> genes = new HashMap<>();
for (int i = 0; i < n; i++) {
    genes.put(i, genesItems[i]);
}

Using an ArrayList or plain array is a little more efficient and maybe more convenient (the array genesItems is already available anyway). Though of course this does not significantly contribute to TLEs in competitive programming.

The skeleton code under the problem uses arrays.

Avoid re-parsing

The inner loop contains Integer.parseInt(health.get(i)), but that should usually be done up front when reading in the problem data. The skeleton code under the problem parses up front.

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