GATE CS 2024 Set 2 Q32 — Algorithm Design: Greedy Techniques

​​​​Consider an array $\mathrm{X}$ that contains $\mathrm{n}$ positive integers. A subarray of $\mathrm{X}$ is defined to be a sequence of array locations with consecutive indices.

The $\mathrm{C}$ code snippet given below has been written to compute the length of the longest subarray of $\mathrm{X}$ that contains at most two distinct integers. The code has two missing expressions labelled $\text{(P)}$ and $\text{(Q)}$.

int first=0, second=0, len1=0, len2=0, maxlen=0;
for (int i=0; i < n; i++) {
    if (X[i] == first) {
        len2++; len1++;
    } else if (X[i] == second) {
        len2++;
        len1 = (P); 

        second = first;
    } else {
        len2 = (Q);
        
        len1 = 1; second = first;
    }
    if (len2 > maxlen) {
        maxlen = len2;
    }
    first = X[i];
}

Which one of the following options gives the CORRECT missing expressions?

(Hint: At the end of the $i$-th iteration, the value of $len 1$ is the length of the longest subarray ending with $\mathrm{X}[i]$ that contains all equal values, and $len 2$ is the length of the longest subarray ending with $\mathrm{X}[i]$ that contains at most two distinct values.)