# Genomic Range Query

Recently I worked on one of the Codility Training - Genomic Range Query (please refer to one of the evaluation report for the detail of this training).

The proper approach for this question is using prefix sum. Here is the implementation:

struct Results solution(char *S, int P[], int Q[], int M) {
struct Results result;
int* ans = (int*)calloc(M, sizeof(int));
int pre_sum_arr[strlen(S)];
int i, j;

memset(pre_sum_arr, 0, sizeof(pre_sum_arr));
for(i = 0 ; i < strlen(S) ; i++){
if(S[i] == 'A') pre_sum_arr[i] = 1;
else if(S[i] == 'C') pre_sum_arr[i] = 1;
else if(S[i] == 'G') pre_sum_arr[i] = 1;
else pre_sum_arr[i] = 1;
}

for(i = 1; i < strlen(S) ; i++){
for(j = 0 ; j < 4 ; j++){
pre_sum_arr[i][j] += pre_sum_arr[i - 1][j];
}
}

for(i = 0 ; i < M ; i++){
for(j = 0 ; j < 4 ; j++){
if((P[i] == 0 && pre_sum_arr[Q[i]][j]) || \
(pre_sum_arr[Q[i]][j] - pre_sum_arr[P[i] - 1][j] > 0)){
ans[i] = j + 1;
break;
}
}
}

result.A = ans;
result.M = M;
return result;
}


However, the evaluation report said that it exceeds the time limit for large-scale testing case (the report link is above).

The detected time complexity is O(M * N) instead of O(M + N). But in my view, it should be O(M + N) since I ran loop for N and M independently (N for calculating the prefix sum and M for getting the answer).

I also used an alternate solution for this question. I also think its complexity is O(M + N), but I got the same result. Here is my code:

struct _pre_min_idx{
int pre_1_idx;
int pre_2_idx;
int pre_3_idx;
};

int mapping(char c){
if(c == 'A') return 1;
if(c == 'C') return 2;
if(c == 'G') return 3;
if(c == 'T') return 4;
return -1;
}

typedef struct _pre_min_idx pre_min_idx;

struct Results solution(char *S, int P[], int Q[], int M) {
struct Results result;
// A = 1, C = 2, G = 3, T = 4
pre_min_idx pre_min_idx_arr[strlen(S)];
int* min_nuc_arr = (int*)calloc(M, sizeof(int));
int i;
int pre_1_idx = -1, pre_2_idx = -1, pre_3_idx = -1;

memset(pre_min_idx_arr, 0, sizeof(pre_min_idx_arr));
for(i = 0 ; i < strlen(S) ; i++){
if(S[i] == 'T'){
pre_min_idx_arr[i].pre_1_idx = pre_1_idx;
pre_min_idx_arr[i].pre_2_idx = pre_2_idx;
pre_min_idx_arr[i].pre_3_idx = pre_3_idx;
}
else if(S[i] == 'G'){
pre_min_idx_arr[i].pre_1_idx = pre_1_idx;
pre_min_idx_arr[i].pre_2_idx = pre_2_idx;
pre_min_idx_arr[i].pre_3_idx = -1;
pre_3_idx = i;
}
else if(S[i] == 'C'){
pre_min_idx_arr[i].pre_1_idx = pre_1_idx;
pre_min_idx_arr[i].pre_2_idx = -1;
pre_min_idx_arr[i].pre_3_idx = -1;
pre_2_idx = i;
}
else{
pre_min_idx_arr[i].pre_1_idx = -1;
pre_min_idx_arr[i].pre_2_idx = -1;
pre_min_idx_arr[i].pre_3_idx = -1;
pre_1_idx = i;
}
}

for(i = 0 ; i < M ; i++){
pre_min_idx pmi_Q = pre_min_idx_arr[Q[i]];
if(pmi_Q.pre_1_idx >= P[i])
min_nuc_arr[i] = 1;
else if(pmi_Q.pre_2_idx >= P[i])
min_nuc_arr[i] = 2;
else if(pmi_Q.pre_3_idx >= P[i])
min_nuc_arr[i] = 3;
else{
min_nuc_arr[i] = mapping(S[Q[i]]);
}
}
result.A = min_nuc_arr;
result.M = M;
return result;
}


The evaluation report is here.

Could anyone help me to figure out what the problem is for my solution? I get stuck for long time. Any performance improvement trick or advice will be appreciated.

strlen takes a linear time in the length of the string. Thus, for(i = 0 ; i < strlen(S) ; i++) will call it n times and the result will be quadratic.

Changing this and a few other details (moving stuff to the smallest possible scope) and you get this :

struct Results solution(char *S, int P[], int Q[], int M) {
int len = strlen(S);
int pre_sum_arr[len];

memset(pre_sum_arr, 0, sizeof(pre_sum_arr));
for(int i = 0 ; i < len ; i++){
if(S[i] == 'A') pre_sum_arr[i] = 1;
else if(S[i] == 'C') pre_sum_arr[i] = 1;
else if(S[i] == 'G') pre_sum_arr[i] = 1;
else                 pre_sum_arr[i] = 1;
}

for(int i = 1; i < len; i++){
for(j = 0 ; j < 4 ; j++){
pre_sum_arr[i][j] += pre_sum_arr[i - 1][j];
}
}

int* ans = (int*)calloc(M, sizeof(int));
for(int i = 0 ; i < M ; i++){
for(int j = 0 ; j < 4 ; j++){
if((P[i] == 0 && pre_sum_arr[Q[i]][j]) || \
(pre_sum_arr[Q[i]][j] - pre_sum_arr[P[i] - 1][j] > 0)){
ans[i] = j + 1;
break;
}
}
}

struct Results result;
result.A = ans;
result.M = M;
return result;
}

• Josay, thank you for pointing out where I missed, it helps a lot. Such a silly mistake I made :/ – Ming-Chen Mar 28 '14 at 0:02
• Might be dodgy putting int pre_sum_arr[len]; on the stack, if len is huge. – dmuir Apr 3 '15 at 11:32

Just a few notes not mentioned in other answers:

• You can typedef your struct right away.

typedef struct
{
int pre_1_idx;
int pre_2_idx;
int pre_3_idx;
} PreMinIdx;


Then initialize it with a more unique name.

PreMinIdx UniqueName;

• Use else ifs in your mapping() method. And since you aren't modifying the function parameter, declare it as const (as you should do with all function parameters you don't modify within the function).

int mapping(const char c)
{
if (c == 'A') return 1;
else if (c == 'C') return 2;
else if (c == 'G') return 3;
else if (c == 'T') return 4;
else return -1;
}

• Some of your variable name do not follow the standard naming conventions of beginning with a lowercase letter, and they aren't very descriptive.

char *S, int P[], int Q[], int M


Even short names such as str would be more descriptive.

• Declare i inside of your for loops.(C99)

for(int i = 0; i < strlen(S); i++)