GATE CS 2024 Set 2 | Question 42

Consider an array X that contains n positive integers. A subarray of X is defined to be a sequence of array locations with consecutive indices.

The C code snippet given below has been written to compute the length of the longest subarray of X that contains at most two distinct integers. The code has two missing expressions labelled \((P)\) and \((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 len1 is the length of the longest subarray ending with X[i] that contains all equal values, and len2 is the length of the longest subarray ending with X[i] that contains at most two distinct values.)

Option A: \((P)\) len1+1 \((Q)\) len2+1
Option B: \((P)\) 1 \((Q)\) len1+1 (correct)
Option C: \((P)\) 1 \((Q)\) len2+1
Option D: \((P)\) len2+1 \((Q)\) len1+1

Answer

(B)

Explanation

During iteration i, first holds the previous element and second the other value in the current two-value window.

X[i] == second: the window still has only two values, so len2 grows by 1. But X[i] differs from the previous element, so the run of equal values ending at X[i] starts again: (P) is 1.
A new value: the window must drop second. The longest valid subarray ending at X[i] is the final run of first values, of length len1, plus X[i]: (Q) is len1+1.

For example, for 1, 2, 1, 3 the correct value at 3 is 2 (the subarray 1, 3), which len1+1 gives, while len2+1 would give 4.

Answer: B