find_leader.py

'''
Given an array of integers containing duplicates, return the majority element in an array if present. A majority element appears more than n/2 times where n is the size of the array.
'''

def find_leader(arr):
    '''
    1. remove pairs of different elements from array
    2. the element that still exists is a candidate
    3. check majority of candidate, should be in len(arr) // 2 elements
    '''
    stack = []

    for x in arr:
        if stack and stack[-1] != x:
            stack.pop()
        if not stack or stack[-1] == x:
            stack.append(x)

    if not stack:
        return -1

    candidate = stack.pop()
    count = 0

    for x in arr:
        if x == candidate:
            count += 1
    if count > len(arr) // 2:
        return candidate

    return -1


def test():
    tests = [
        ([1, 3, 2, 3, 3], 3),
        ([1, 2, 3, 3], -1),
        ([1, 3], -1),
        ([1, 2, 3], -1),
        ([1, 1], 1)
    ]

    for arr, should in tests:
        leader = find_leader(arr)
        assert leader == should, "{}={} should be {}".format(arr, leader, should)

if "__main__" in __name__:
    test()