Finding number of subarrays not including certain pairs

Question

How many contiguous subarrays of an array exist such that they do not contain certain pairs of positions of the array? For eg. if array ={11,22,33,45} and if we do not want to include say position number (1,3) and (2,4) then number of contiguous subarrays that exist are 7 which are as follows {{11},{22},{33},{44},{11,22},{22,33},{33,45}}.

My attempt at solving the problem:

If two pairs exist such that {...,a1, ...,a2 ,..,b1, ..,b2} where n is the number of elemnts and (...) indicate that there are elements in between these positions.

1st case :We cannot include {a1,b1} and {a2,b2} then we have to just count the number of possible combinations which is n*(n+1)/2 - no. of possible combinations including {a2,b1} which covers all the possible

case 2. If we cannot include pairs {a1,b2} and {a2,b1} then we just subtract number of possibilties containing {a2,b1} which covers all the possible cases.

3rd case: if we can't include pairs {a1,a2} and {b1,b2} then we have to individually subtract possible subarrays including these positions

The problem I'm facing is I am not able to derive a formula and extend these cases to more than 2 pairs to count the number of possible solutions even after formulating the cases. So, I need help regarding that.

Source: This is an interview question asked to my friend which he could not answer.

Answer 1

It is hard to achieve a simple formula. Maybe using inclusion-exclusion principle can be possible, but I don't think that's a good idea. If I were your friend, I would answer this:

Let's define a subarray $[i..j]$ is valid when there are no invalid pairs inside it. Also let's denote the array's size as $n$, and the indexes are integers from 1 to $N$.

Some (maybe obvious) facts:

• If $[i..j]$ is valid, $[(i+1)..j]$ and $[i..(j-1)]$ are also valid too.
• If $[i..j]$ is not valid, $[i..(j+1)]$, $[i..(j+2)]$, ..., $[i..n]$ are also not valid too.

Let's define $r_i$ as the rightmost index where $[i..r_i]$ is valid. With these two facts, we can conclude that $r_1 \le r_2 \le \cdots \le r_{n}$ ($\{r_{i}\}$ is monotonically increasing) So using the two pointers method, we can get $r_{i}$ for all possible $i$.

Then, it is easy to get the answer: $\sum_{i=1}^{n} (r_{i} - i + 1)$.