Majority Element

Source

Imports

With the exception of the defaultdict, everything imported is for testing. 

# python standard library
from collections import defaultdict
from datetime import (
    datetime,
    timedelta,
    )
import random

# pypi
from expects import (
    equal,
    expect,
)
import numpy

The Majority Element Problem

Check whether a sequence contains an element that appears more than half of the time. Note that the problem doesn't ask if one of the elements appears more than all the other elements, but rather whether it appears more than half the time (it isn't a simple majority).

Input A sequence of n integers
Output 1 if there is a majority element, 0 otherwise.
Constraints \(1 \le n \le 10^5; 0 \le a_i \le 10^9\) for all \(1 \le i \le n\)

Constants

class Constraints:
    min_length = 1
    max_length = 10**5
    min_value = 1
    max_value = 10**9
    max_time = timedelta(seconds=5)

class Outcome:
    has_majority = 1
    no_majority = 0

Samples

These are values to test against. The initial cases are for the naive-implementation and the last two are for an implementation that is more efficient. 

class TestKeys:
    votes = 'input'
    expected = 'output'

SAMPLES = dict(
    one={
	TestKeys.votes: [2, 3, 9, 2, 2],
	TestKeys.expected: 1,
    },
    two={
	TestKeys.votes: [1, 2, 3, 1],
	TestKeys.expected: 0,
    },
    three={
	TestKeys.votes: [random.randint(1, Constraints.max_value),],
	TestKeys.expected: 1,
	       }
)

vote = random.randint(1, Constraints.max_value)
SAMPLES["four"] = {
    TestKeys.votes: [vote, vote],
    TestKeys.expected: 1,
}
SAMPLES["five"] = {
    TestKeys.votes: [vote, vote + 1],
    TestKeys.expected: 0,
}

Now we're going to add two cases that have the maximum allowed number of values to make sure our solution can finish in a reasonable time. 

half = Constraints.max_length//2

left_size = half + 10
right_size = half - 10

left = numpy.ones(left_size) * random.randrange(Constraints.max_value)
right = numpy.random.randint(Constraints.min_value,
		      Constraints.max_value + 1,
		      right_size)
three = numpy.concatenate((left, right))
SAMPLES["six"] = {
    TestKeys.votes: three,
    TestKeys.expected: 1,
}

This next case isn't necessarily guaranteed to be true (numpy might generate an array with one element that is in the majority), but I think that the chance of it failing is pretty close to zero. 

SAMPLES["seven"] = {
    TestKeys.votes: numpy.random.randint(Constraints.min_value,
				  Constraints.max_value + 1,
				  Constraints.max_length),
    TestKeys.expected: 0,

}

The Naive Solution

This is a translation of the pseudocode given with the problem. It has a runtime of \(O(n^2)\) 

def naive_majority(voters):
    """Decides if there is a majority element

    Args:
     voters: list of elements to check

    Returns:
     int: 1 if there is a majority element, 0 otherwise
    """
    half = len(voters)//2
    for index, voter in enumerate(voters):
	count = 0
	for other_voter in voters:
	    if voter == other_voter:
		count += 1
	if count > half:
	    return Outcome.has_majority
    return Outcome.no_majority

Now we can test if it is correct. 

for sample in "one two three four five".split():
    values = SAMPLES[sample]
    actual = naive_majority(values[TestKeys.votes])
    expected = values[TestKeys.expected]
    print("{} actual: {} expected: {}".format(sample,
					      actual,
					      expected))

    expect(actual).to(equal(expected))

Although it looks correct the grader says it times out. 

Failed case #11/21: time limit exceeded (Time used: 9.98/5.00, memory used: 21266432/536870912.)

Iterative Version

Although this is the divide-and conquer section, the more intuitive way for me is to just count and sort the items to see if the item with the most votes is the majority. The counting of the votes is \(O(n)\) and the sort adds \(O(n \log n)\). 

def iterative_majority(votes):
    """Decides if there is a majority among the votes

    Args:
     votes (list): collection to check

    Returns:
     int: 1 if there is a majority, 0 otherwise
    """
    half = len(votes)//2
    counts = defaultdict(lambda: 0)
    for vote in votes:
	counts[vote] += 1

    sorted_counts = sorted((count for count in counts.values()), reverse=True)
    return (Outcome.has_majority if sorted_counts[0] > half
	    else Outcome.no_majority)

def test_implementation(implementation):
    """runs the implementation against the samples

    Args:
     implementation: callable to test

    Raises:
     AssertionError: answer wasn't the expected
    """
    for sample, values in SAMPLES.items():
	start = datetime.now()
	actual = implementation(values[TestKeys.votes])
	expected = values[TestKeys.expected]
	elapsed = datetime.now() - start
	print("({}) elapsed: {} actual: {} expected: {}".format(
	    sample,
	    elapsed,
	    actual,
	    expected))
	expect(actual).to(equal(expected))
	assert elapsed < Constraints.max_time

test_implementation(iterative_majority)

This version passes the grader. 

Good job! (Max time used: 0.14/5.00, max memory used: 22638592/536870912.)

Iterative Two

We can get rid of the sort since only have to check the count. This reduces the runtime to \(O(n)\), although since the for-loop is now pure python it might not actually speed things up much. 

def iterative_majority_two(votes):
    """Decides if there is a majority among the votes

    Args:
     votes (list): collection to check

    Returns:
     int: 1 if there is a majority, 0 otherwise
    """
    half = len(votes)//2
    counts = defaultdict(lambda: 0)
    for vote in votes:
	counts[vote] += 1

    for count in counts.values():
	if count > half:
	    return Outcome.has_majority
    return Outcome.no_majority

test_implementation(iterative_majority_two)

This one also passes the grader. 

Good job! (Max time used: 0.14/5.00, max memory used: 22626304/536870912.)

It took exactly the same amount of time in the grader (although that might be because the time difference is less than their rounding), but used up a little less memory.