# Find the Most Frequent Ordered Word Pair In a Document

This is a problem from Skiena's excellent book The Algorithm Design Manual:

Give an algorithm for finding an ordered word pair(e.g."New York") occurring with the greatest frequency in a given webpage. Which data structure would you use? Optimize both time and space.

We need to look at all the words, so clearly we can't do better than O(n) time. One solution I can think of is inserting each ordered pair in a priority queue (O(n) time and space), and then returning the top item. However, the official site has a solution which suggests using a Trie. I understand that words may be repeated, or may be prefix/suffix of other words, so a Trie would save space, but can't figure out how to answer the question using it.

Ideas?

• I am not sure to understand how you use the priority queue and perform O(n) in time. Can you give details ? – Optidad Feb 4 '19 at 13:21
• @Vince You simply insert each pair in the max PQ with frequency 1 if not already present. If present, you increment the key. – Abhijit Sarkar Feb 5 '19 at 2:11
• and you access on key (pair of word) in a maxqueue in O(1) ? With finally no real interest on the maxqueue as you only need one maximum. – Optidad Feb 5 '19 at 9:03
• @Vince That's right. Clearly, you can't do better than O(n) time so the only problem worth considering here is how to save some space. If you've a better algo that saves space and is faster than O(n), you would be eligible for more than just some rep points here. – Abhijit Sarkar Feb 5 '19 at 9:38

In an $$n-$$word text you have exactly $$n-1$$ ordered word pairs (not distinct of course). If you use a Trie, you don't need to represent all $$n-1$$ pairs separately. Take for a example the following text: