# Codility 'GenomicRangeQuery' Solution

Martin Kysel · August 5, 2014

##### Short Problem Definition:

Find the minimal nucleotide from a range of sequence DNA.

GenomicRangeQuery

##### Complexity:

expected worst-case time complexity is `O(N+M)`

expected worst-case space complexity is `O(N)`

##### Execution:

Remember the last position on which was the genome (A, C, G, T) was seen. If the distance between Q and P is lower than the distance to the last seen genome, we have found the right candidate.

##### Solution:
``````
def writeCharToList(S, last_seen, c, idx):
if S[idx] == c:
last_seen[idx] = idx
elif idx > 0:
last_seen[idx] = last_seen[idx -1]

def solution(S, P, Q):

if len(P) != len(Q):
raise Exception("Invalid input")

last_seen_A = [-1] * len(S)
last_seen_C = [-1] * len(S)
last_seen_G = [-1] * len(S)
last_seen_T = [-1] * len(S)

for idx in xrange(len(S)):
writeCharToList(S, last_seen_A, 'A', idx)
writeCharToList(S, last_seen_C, 'C', idx)
writeCharToList(S, last_seen_G, 'G', idx)
writeCharToList(S, last_seen_T, 'T', idx)

solution =  * len(Q)

for idx in xrange(len(Q)):
if last_seen_A[Q[idx]] >= P[idx]:
solution[idx] = 1
elif last_seen_C[Q[idx]] >= P[idx]:
solution[idx] = 2
elif last_seen_G[Q[idx]] >= P[idx]:
solution[idx] = 3
elif last_seen_T[Q[idx]] >= P[idx]:
solution[idx] = 4
else:
raise Exception("Should never happen")

return solution

``````