isDominator.py

#data = [1, 2, 3, 4, 4, 4]
#data = [1, 1, 2, 2, 3, 3]
#data = [5, 6, 9, 7, 7]
data = [1,2,1,2,3,3,3] # special case len(stack==3)
#data = [2,2,3,3,3,3,4,4] # special case len(stack==0)
#data = [1,1,2,2,3,3,4,4] # special case len(stack==0)

stack = []

# O(n)
def isDominator(num):
	count = 0;
	for i in data:
		if i == num:
			count += 1
	if count >= len(data)/2.0:
		print("%d dominates the sequence" % num)
	else:
		print("No one dominates the sequenece")

# O(n)
def main():
	for i in data:
		if len(stack)==0:
			stack.append(i)
		else:
			if stack[len(stack)-1] == i:
				stack.append(i)
			else:
				pop = stack[len(stack)-1]
				stack.pop()
		print i
		print stack

	if len(stack)==0:
		isDominator(pop)
	if len(stack)==1:
		isDominator(stack[0])
	if len(stack)==2:
		isDominator(stack[0])
		if(stack[1]!=stack[0]):
			isDominator(stack[1])
	if len(stack)==3:
		isDominator(stack[0])

if __name__ == "__main__":
	main()