Wednesday, January 23, 2013

Majority Vote Algorithm with Linear Time & Constant Space

I saw a problem on some certain forum days ago:
Design an algorithm that, given a list of N elements in an array, finds all the elements that appear more that n/3 times in linear time and using constant space only.

Well, another constant space problem. Without this constrain, we can easily achieve an linear time algorithm by using a hashmap or just another array.
I didn't have good solutions. And then I searched online, and found that there was a particular name for this problem: Majority Vote. And there's a neat algorithm here .

While this algorithm seemed not that straightforward to me at first, the idea behind it was quite simple:
The majority ( if there exists ) will remain the same when we delete 3 different elements from list each time, taking the problem I stated at first as the example.

No comments:

Post a Comment