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)][4];
    int i, j;

    memset(pre_sum_arr, 0, sizeof(pre_sum_arr));
    for(i = 0 ; i  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 = 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]]);

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][4];

    memset(pre_sum_arr, 0, sizeof(pre_sum_arr));
    for(int i = 0 ; i  0)){
                ans[i] = j + 1;
                break;
            }
        }
    }

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

StackExchange Code Review Q#45467, answer score: 5