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


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!

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.