# 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 ? 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. 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. 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. 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:

A new puppy in New York is happy with it's New York life.

You first start looking at the words in the text as pairs where the first pair is (a,new), the second is (new,puppy), (puppy,in), ... ,(York,life). The resulting trie will look something like this:

In order to find which pair appears the most times you need to count how many times you reach each leaf.

• What you showed isn't a Trie because words shouldn't be repeated: Instead of saving space, you use more space. This tree has no advantage over a max priority queue, and takes more time to find out the most frequent pair (counting leaves). Feb 3 '19 at 22:48
• It is a trie. Consider the case you insert the word "haha" letter by letter. Wouldn't each letter occupy one node even though they are repeated? Also, I don't use more space. You have to store each pair at least once, you can't do better than that! Of course you can store only once the pairs that appear multiple times but my represenation does exactly that. Finally, I don't think counting how many times you reach each leaf is slower than what you propose. After all, you need to check that the pair is already in the trie! That being said I agree that counting might not be the optimal way Feb 4 '19 at 21:39