# How many times does a pair of numbers co-occur in a list?

Imagine you have N distinct people and that you have a record of where these people are, exactly M of these records to be exact.

For example

1,50,299
1,2,3,4,5,50,287
1,50,294


So you can see that 'person 1' is at the same place with 'person 50' three times. Here M = 3 obviously since there's only 3 lines. My question is given M rows, and a threshold value (i.e person A and B have been at the same place more than threshold times), what do you suggest the most efficient way of returning these co-occurrences?

So far I've built an N by N table, and looped through each row of M, incrementing table(N,X) every time N co occurs with X in a row. Obviously this is an awful approach and takes 0(MN^2) depending on how you implement. Any tips would be appreciated!

• You're using $M$ in two different ways. In contrast, your running time is stated in terms of the undefined quantity $n$. – Yuval Filmus Nov 20 '17 at 20:27
• You can always try proving that your problem is 3SUM-hard. – Yuval Filmus Nov 20 '17 at 20:29
• @YuvalFilmus thanks for the help, but since we haven't covered that in class, I doubt I'd be able to use it. – user124806 Nov 20 '17 at 20:36
• Since it is possible that all persons co-appear together, you can't really do better than $N^2$. – Yuval Filmus Nov 20 '17 at 21:06