GATE CS 2006 Q54 — Asymptotic Worst Case Time and Space Complexity

The problem asks us to find the largest span $(i, j)$ such that:

This can be rewritten as:

Let $c_k = a_k - b_k$. Since $a_k, b_k \in \{0, 1\}$, the value of $c_k$ can only be $-1$, $0$, or $1$.

Let $S_p$ be the prefix sum of array $c$ up to index $p$:

The condition $\sum_{k=i}^{j} c_k = 0$ is equivalent to:

To find the largest span $(i, j)$ where $S_j = S_{i-1}$, we want to maximize $j - i + 1$. This means for each unique prefix sum value, we want to find its first occurrence and its last occurrence.

Algorithm Steps:

1. Compute the prefix sums $S_0, S_1, \dots, S_n$. Since $c_k \in \{-1, 0, 1\}$, the prefix sum $S_p$ must lie in the range $[-n, n]$.
2. Initialize an auxiliary array first_occurrence of size $2n + 1$ with $-1$ to store the first index at which each prefix sum value is seen. (We can map the range $[-n, n]$ to $[0, 2n]$ by adding an offset of $n$).
3. Traverse the prefix sums from $p = 0$ to $n$:
   • If first_occurrence[S_p] is $-1$, set it to $p$.
   • Otherwise, a span with sum $0$ exists from index $\text{first\_occurrence}[S_p] + 1$ to $p$. The length of this span is $p - \text{first\_occurrence}[S_p]$. Update the maximum span length if this is larger than the current maximum.

Complexity Analysis:

• Time Complexity: We perform a single pass over the array of size $n$. Each lookup and update in the auxiliary array takes $O(1)$ time. Thus, the total time complexity is $\Theta(n)$.
• Space Complexity: The auxiliary array of size $2n + 1$ requires $\Theta(n)$ extra space.

Therefore, the fastest algorithm takes $\Theta(n)$ time and space.