7
\$\begingroup\$

A list is said to have a “majority element” if more than half of its entries are identical. In this classical problem the goal consists of determining whether a list a of length n has a majority element, and, if so, to find that element.

A tuple the final method returns, which contains

a) Whether the list contains a majority element (Boolean).

b) The majority element if it exists. Otherwise this value is irrelevant (the function could simply return None).

c) The number of occurrences of the majority element (0 if it does not exist).

I simply post my code here that if I get your advices.

def count(element, arr):
    if len(arr) == 0:
        return 0
    if arr[0] == element:
        return 1 + count(element, arr[1:])
    return count(element, arr[1:])


def getMajorityElementHelper(arr, l, h):
    if l > h:
        return False, None, 0

    if (h - l) == 0:
        return True, arr[l], 1

    mid = l + ((h - l) // 2)

    left = getMajorityElementHelper(arr, l, mid)
    right = getMajorityElementHelper(arr, mid + 1, h)

    if left[0]:
        # range of right part which is arr[mid + 1:h + 1]
        c = count(left[1], arr[mid + 1:h + 1])
        if (c + left[2]) > ((h + l + 1) / 2):
            return True, left[1], left[2] + c

    if right[0]:
        # range of left part which is arr[l:mid + 1]
        c = count(right[1], arr[l:mid + 1])
        if (c + right[2]) > ((h + l + 1) / 2):
            return True, right[1], right[2] + c

    return False, None, 0


def getMajorityElement(arr):
    return getMajorityElementHelper(arr, 0, len(arr) - 1)


if __name__ == '__main__':
    print("main started")

    print(getMajorityElement([3, 4, 4, 1, 4]))   #  (True, 4, 3)
    print(getMajorityElement([3, 4, 4]))   #  (True, 4, 2)
    print(getMajorityElement([4, 4, 3]))   #  (True, 4, 2)
    print(getMajorityElement([4]))   #  (True, 4, 1)
    print(getMajorityElement([]))   #  (False, None, 0)
    print(getMajorityElement([3, 4, 4, 1, 1]))   #  (False, None, 0)
\$\endgroup\$
1
  • 3
    \$\begingroup\$ Are you aware of Boyer-Moore algorithm? \$\endgroup\$
    – vnp
    Jan 9 at 19:55

3 Answers 3

20
\$\begingroup\$

Boyer-Moore for the curious

You have a good answer already suggesting the use of a Counter. For simplicity, that's what I would do.

However, I had never heard of the Boyer-Moore algorithm for finding a majority value in a sequence. Its advantage is that it can achieve O(n) performance without allocating additional memory to count all of the values, as one does when using a Counter. To do its bookkeeping, Boyer-Moore needs to hold only an integer and single value from the sequence. When I read the pseudocode on Wikipedia, it wasn't clear why it worked: the code seemed trivially simple and I could not immediately see how a few increments and decrements could achieve the needed goal. Also, the algorithm was interesting because it had an odd footnote: before returning a candidate value, you have make a final pass over the sequence actually counting how many times it occurred. It was a select-and-verify algorithm rather than a just-select-the-right-answer algorithm.

I wrote a Python implementation and tried to convince myself it works (yes, of course!) and to get some intuition about how/why. First some terminology:

xs : The input sequence.
x  : A value from the sequence.
M  : The actual majority value, if any. This is unknown.
m  : The currently selected candidate, which might or might not be M.
n  : The net-majority status of m since m was selected.

Here's the function I wrote:

def majority_element(xs):
    # Handle empty input.
    if not xs:
        return None

    # Find a candidate value for the majority (m).
    #
    # At any moment, n represents the net-majority status of m.
    # A value of zero for n means we have seen non-m values the same
    # number of times as m values since m was selected.
    n = 0
    for x in xs:
        if n == 0:
            # Net majority status is unclear. Pick a new candidate.
            m = x
            n = 1
        else:
            # Otherwise, increment/decrement the net-majority status of m.
            n += (1 if x == m else -1)

    # Return the candidate only if it is truly the majority.
    if xs.count(m) > len(xs) / 2:
        return m
    else:
        return None

And some code to test it:

from collections import Counter
from random import shuffle

def main():
    # A list with an even number of zeros and ones.
    N = 100
    ZEROS = [0 for _ in range(N)]
    ONES = [1 for _ in range(N)]
    EVEN = ZEROS + ONES
    shuffle(EVEN)

    # Some test cases using that list.
    TESTS = (
        (None, []),
        (None, EVEN),
        (1, EVEN + [1]),
        (1, [1] + EVEN),
        (0, [0] + EVEN),
        (0, EVEN + [0]),
    )

    # Check.
    for exp, xs in TESTS:
        got = majority_element(xs)
        if got == exp:
            print('ok')
        else:
            print(xs, exp, got, Counter(xs))

if '__name__' == '__main__':
    main()

And here is some rough intuition behind its success. In order for a value M to be the majority value in a sequence, it must be a majority value in at least one subsection of the sequence. At a very crude level, one can imagine three flavors of majority-having sequences:

# Front loaded: M sits predominantly toward front of sequence.
1 1 1 1 1 1 0 0 0

# Back loaded: M sits predominantly toward back of sequence.
0 0 0 1 1 1 1 1 1

# Evenly loaded: M is dispersed in a fairly even way across the sequence.
0 1 1 0 1 1 0 1 1

In the front-loaded case, n will increase and the non-M values at the end of the list won't be enough to counteract that growth. In the back-loaded case, a non-M value will be selected as a candidate, but eventually the net-majority counter will become zero and the algorithm will select an M value. In the even-loaded case, you can subdivide the sequence into smaller sub-sequences and the same front-loaded/back-loaded logic can be applied to each sub-sequence. The algorithm will select the majority within the first sub-sequence and the remaining sub-sequences (because they are also evenly loaded) won't be able to counteract that verdict.

\$\endgroup\$
6
  • \$\begingroup\$ The guard-clause is a premature pessimisation for sequences, right? The only thing it does is allowing falsy values like false and none. \$\endgroup\$ Jan 10 at 17:08
  • \$\begingroup\$ @Deduplicator I assume your are referring to if not xs, with the implication that we could remove the guard? If so, deleting the guard is less simple than it appears: m will be undefined. One could initialize m, but then the question becomes, initialize with what value? What if the majority element in xs is None itself? I suppose we could initialize this like: m = object(), but that seems opaque and no simpler. But perhaps I'm overlooking something or misunderstanding your point. \$\endgroup\$
    – FMc
    Jan 10 at 17:48
  • \$\begingroup\$ @Deduplicator I guess the function already doesn't really handle the case where xs contains None. Perhaps a better implementation would mimic the built-in min() function: accept an optional default argument and raise if the sequence is empty and provided no default. \$\endgroup\$
    – FMc
    Jan 10 at 17:58
  • \$\begingroup\$ Or return a tuple: count of majority element, majority element or 0, None if there is none. \$\endgroup\$ Jan 10 at 18:06
  • \$\begingroup\$ Playing around with the algorithm, I note that the "more than half" requirement of the Boyer-Moore majority vote algorithm is to be understood as > 50%. For example, considering the list [1, 0, 2, 0] we can see that this algorithm doesn't designate 0 as the majority element unless I'm mistaken. I also find it interesting to note that if it is known that there is a majority element the second pass is not necessary, in which case the algorithm is streaming. \$\endgroup\$ Jan 11 at 15:21
6
\$\begingroup\$

I'd just use the collections.Counter for this:

import collections
from typing import Any, List, Tuple

def get_majority_element(arr: List[Any]) -> Tuple[bool, Any, int]:
  cnter = collections.Counter(arr)
  ele, count = cnter.most_common(1)[0]
  if count > (len(arr) / 2):
    return True, ele, count
  else:
    return False, None, 0

Some other loose points

def count(element, arr):
    if len(arr) == 0:
        return 0
    if arr[0] == element:
        return 1 + count(element, arr[1:])
    return count(element, arr[1:])

This is a recursive function that creates a lot of subset copies of the array. It's quite costly. I suspect that maybe that is the point of the exercise, to implement some recursive divide and conquer algorithm, but I don't see why you would need to do that for just the counting bit... It does look like it at least works, but you also have a decent bit of branching and duplication; consider how many different return ... alternatives you have.

Thinking more about this, why would you use a divide and conquer algorithm in the first place? You have no info about the list being sorted in any place, and you're just counting elements. Even if you want to avoid using collections.Counter you should still have the same approach: create a hashmap, iterate over the sequence and add each element to the list plus keep track of its current count, and then check to see if the count of any element is more or equal to the total number of elements.

By the way, you don't need to check if len(arr) == 0 - you can just do if not arr.

Try to change your practices when it comes to naming variables and functions:

def getMajorityElementHelper(arr, l, h):

We typically use snake_case for function names in python, and l and h could definitely be more explicit - always consider the importance of readability.

\$\endgroup\$
1
  • 2
    \$\begingroup\$ Did you mean count > len(arr) / 2? According to the definition, if exactly half of the elements have the same value, then it's not a "majority element" (and there may well be another element with the same count). \$\endgroup\$ Jan 9 at 19:37
1
\$\begingroup\$

Unless there's an explicit reason to avoid doing so, there are some standard Python functions that can dramatically streamline this process. Specifically, the ability for set() to grab a list of unique elements from the array and array.count() to grab the count of a given element in the array.

Combining those together, we can simplify the process of finding the majority element and returning it down to something like this

def getMajorityElement(input_list):
    goal_length = len(input_list)/2
    for value in set(input_list):
        if input_list.count(value)>goal_length:
            return True,value,input_list.count(value)
    return False,None,0

Depending on the practical use-cases of the code, it could potentially be dramatically sped up with some simple checks (such as returning immediately if len(set(input)) > goal_length), since the number of unique elements being more than half the list precludes a majority element existing).

However, the extra code complexity of something like that likely isn't worthwhile unless you know your input data's structure will fit a pattern that lends itself to such things (such as the majority value tending towards the larger/smaller end such that sorting the unique values could help or the unique value count hovering around half the list length such that a check for >50% unique is worth running). Most of the time, slightly less code efficiency is a small price to pay for more readable code.

\$\endgroup\$
1
  • 2
    \$\begingroup\$ Simpler, but inefficient, as we're computing O(n) count() for O(n) elements of the set. \$\endgroup\$ Jan 10 at 21:22

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.