Majority element

Find the majority element in the array. A majority element in an array A[] of size n is an element that appears more than n/2 times (and hence there is at most one such element).

break_it_down

• It can be efficiently solved using,moores_voting_algorithm

Code ✅

Q. Why is it consuming so much memory? Is the space complexity more?

class Solution(object):
 
	def majorityElement(self, A):
		
		"""
		
		:type nums: List[int]
		
		:rtype: int
		
		"""
 
		maj_index = 0
		
		count = 1
		
		for i in range(len(A)):
		
		if A[maj_index] == A[i]:
		
		count += 1
		
		else:
		
		count -= 1
		
		if count == 0:
		
		maj_index = i
		
		count = 1
		
		return A[maj_index]

moores_voting_algorithm details

# Program for finding out majority element in an array
 
# Function to find the candidate for Majority
 
 
def findCandidate(A):
	maj_index = 0
	count = 1
	for i in range(len(A)):
		if A[maj_index] == A[i]:
			count += 1
		else:
			count -= 1
		if count == 0:
			maj_index = i
			count = 1
	return A[maj_index]
 
# Function to check if the candidate occurs more than n/2 times
 
 
def isMajority(A, cand):
	count = 0
	for i in range(len(A)):
		if A[i] == cand:
			count += 1
	if count > len(A)/2:
		return True
	else:
		return False
 
# Function to print Majority Element
 
 
def printMajority(A):
	# Find the candidate for Majority
	cand = findCandidate(A)
 
	# Print the candidate if it is Majority
	if isMajority(A, cand) == True:
		print(cand)
	else:
		print("No Majority Element")
 
 
# Driver code
A = [1, 3, 3, 1, 2]
 
# Function call
printMajority(A)
 

hashmap

# Program for finding out majority element in an array
 
# Function to find the candidate for Majority
 
 
def findCandidate(A):
	maj_index = 0
	count = 1
	for i in range(len(A)):
		if A[maj_index] == A[i]:
			count += 1
		else:
			count -= 1
		if count == 0:
			maj_index = i
			count = 1
	return A[maj_index]
 
# Function to check if the candidate occurs more than n/2 times
 
 
def isMajority(A, cand):
	count = 0
	for i in range(len(A)):
		if A[i] == cand:
			count += 1
	if count > len(A)/2:
		return True
	else:
		return False
 
# Function to print Majority Element
 
 
def printMajority(A):
	# Find the candidate for Majority
	cand = findCandidate(A)
 
	# Print the candidate if it is Majority
	if isMajority(A, cand) == True:
		print(cand)
	else:
		print("No Majority Element")
 
 
# Driver code
A = [1, 3, 3, 1, 2]
 
# Function call
printMajority(A)