Codility Genomic Range Query

Posted on October 19, 2013

Last updated on October 18, 2013

In this article I will provide a solution to the Genomic Range Query sample Codility problem. The problem description is long and copyrighted, so have a look at the link for the detailed problem description, and try to attempt it first yourself.

The optimal idea is to keep a prefix sum of the number of occurences of each letter from the set $$[G,C,T,A]$$ for every position in the target string. Then, to evalute the minimal nucleotide between indices $$(a,b)$$, we can easily compute the total number of occurences of each of the nucleotides in $$O(1)$$ time, and pick the smallest one. This leads to a total running time of $$O(N+M)$$. The following Java code scores 100/100 on Codility: