Skip to content

Instantly share code, notes, and snippets.

@isRuslan
Created May 4, 2017 20:04
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save isRuslan/73f79a8a50453b0c84306b1cd76ce68b to your computer and use it in GitHub Desktop.
'''
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()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment