A Probabilistic "Solution" & invitation for discussion


  • 0

    The Boyer-Moore Majority Vote Algorithm would be the best solution for this problem, however I wanted to push for another solution giving the information that The majority element is the element that appears more than ⌊ n/2 ⌋ times.

    If we have an array with n elements and there's an element that appear more than 50% in this array, then there's more than 50% chance that when you pick random element from the array it would be our majority element.

    The idea would be to have a small lookup that holds the count of elements seen in the array. This lookup is constant size.

    The pseudo code goes something like

    lookup_map = new map with initial capacity = freq_size
    for i = 0 to n do
        r = random number between 0 to n - 1
        // if element exist already in lookup map, then increment its frequency
        if lookup_map contains arr[r]
             lookup_map.put(arr[r], lookup_map.get(arr[r]) + 1)
        // if element does not exist in map and map size still less than its capacity then add element
        else if lookup_map.size < freq_size
            lookup_map.put(arr[r], 1)
        // else pick the element with min freq in the lookup map, remove it, and add the new one
        else if(lookup_map.size = freq_size)
            key = get_el_with_min_freq(lookup_map)
            lookup_map.remove(key)
            lookup_map.put(arr[r], 1)
    
    return get_el_with_max_freq(lookup_map)
    

    After we run this routine we should verify the answer by scanning the array and counting the occurrences of the returned element, it must be more than ⌊ n/2 ⌋ to be valid.

    There're lots of details that are left out which is the reason for "invitation for discussion" in the title. For example, what should be the size o the lookup map? How to handle random numbers that already have been generated before? Is there a way to generate unique random numbers? Should we loop the whole array or could we stop before the end of it?

    The complexity of this algorithm would heavily depend on the implementation of the random number generation being used.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.