# Codility ‘GenomicRangeQuery’ Solution

##### 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

```

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.