Given an array A of N elements. 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 in the array.
 
Example 1:
Input:
N = 3 
A[] = {1,2,3} 
Output:
-1
Explanation:
Since, each element in 
{1,2,3} appears only once so there 
is no majority element.
Example 2:
Input:
N = 5 
A[] = {3,1,3,3,2} 
Output:
3
Explanation:
Since, 3 is present more
than N/2 times, so it is 
the majority element.
Your Task:
The task is to complete the function majorityElement() which returns the majority element in the array. If no majority exists, return -1.
 
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
 
Constraints:
1 ≤ N ≤ 10^{7}
0 ≤ A_{i} ≤ 10^{6}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Complete search

Data structures

Greedy algorithms

Starter code: #User function template for Python 3



class Solution:

    def majorityElement(self, A, N):

        #Your code here

Solutions:
class Solution:

	def majorityElement(self, A, N):
		flag = True
		re = N // 2
		dict = {}
		if N == 1:
			return A[0]
		else:
			for i in A:
				if i in dict:
					dict[i] += 1
				else:
					dict[i] = 0
		for i in dict:
			if dict[i] >= re:
				flag = False
				return i
		if flag == True:
			return -1


class Solution:

	def majorityElement(self, A, N):
		if N == 1:
			return A[0]
		else:
			my_list = A
			size = N / 2
			element_count = {}
			for element in my_list:
				if element in element_count:
					element_count[element] += 1
				else:
					element_count[element] = 1
			max_count = max(element_count.values())
			if max_count == 1 or max_count <= size:
				return -1
			else:
				max_elements = [element for (element, count) in element_count.items() if count == max_count]
				for maxelements in max_elements:
					return maxelements


from collections import defaultdict

class Solution:

	def majorityElement(self, A, N):
		value = -1
		count = 0
		for a in A:
			if count == 0:
				value = a
				count += 1
			elif a == value:
				count += 1
			else:
				count -= 1
		return value if A.count(value) > N / 2 else -1


from collections import defaultdict

class Solution:

	def majorityElement(self, A, N):
		dic = defaultdict(int)
		for a in A:
			dic[a] += 1
			if dic[a] > N / 2:
				return a
		return -1


class Solution:

	def majorityElement(self, A, N):
		c = N / 2
		dict = {}
		if N == 1:
			return A[0]
		for x in A:
			if x not in dict:
				dict[x] = 1
			elif x in dict:
				dict[x] += 1
				if dict[x] > c:
					return x
		return -1


from collections import Counter, defaultdict

class Solution:

	def majorityElement(self, arr, N):
		c = Counter(arr)
		(v, cnt) = c.most_common(1)[0]
		if cnt > len(arr) // 2:
			return v
		return -1


class Solution:

	def majorityElement(self, array, n):
		(result, count) = (array[0], 1)
		for data in array[1:]:
			count = count + 1 if data == result else count - 1
			if count == 0:
				(result, count) = (data, 1)
		count = 0
		for data in array:
			if data == result:
				count += 1
		if not count > n // 2:
			result = -1
		return result


class Solution:

	def majorityElement(self, A, N):
		half = N // 2
		hash = {}
		for ele in A:
			if ele not in hash:
				hash[ele] = 1
			else:
				hash[ele] += 1
		for (k, v) in hash.items():
			if v > half:
				return k
		return -1


class Solution:

	def majorityElement(self, A, N):
		mp = {}
		for i in range(N):
			if A[i] in mp:
				mp[A[i]] += 1
			else:
				mp[A[i]] = 1
		for i in mp.keys():
			if mp[i] > N // 2:
				return i
		return -1


from collections import Counter

class Solution:

	def majorityElement(self, A, N):
		k = Counter(A)
		if N == 1:
			return A[0]
		for i in A:
			if k[i] > N // 2:
				return i
		return -1


class Solution:

	def majorityElement(self, A, N):
		elem = 0
		count = 0
		maxcount = 0
		for ele in A:
			if count == 0:
				elem = ele
			if ele == elem:
				count += 1
			else:
				count -= 1
		for val in A:
			if val == elem:
				maxcount += 1
		return elem if maxcount > N // 2 else -1


class Solution:

	def majorityElement(self, A, N):
		elem = A[0]
		count = 1
		maxCount = 0
		for idx in range(1, N):
			if A[idx] == elem:
				count += 1
			elif count == 0:
				elem = A[idx]
				count = 1
			else:
				count -= 1
		for val in A:
			if val == elem:
				maxCount += 1
		return elem if maxCount > N // 2 else -1


class Solution:

	def majorityElement(self, A, N):
		hashmap = {}
		ele = N // 2
		for i in A:
			if i in hashmap:
				hashmap[i] += 1
			else:
				hashmap[i] = 1
			if hashmap[i] > ele:
				return i
		return -1


class Solution:

	def findCandidate(self, 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]

	def isMajority(self, 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

	def majorityElement(self, A, N):
		cand = self.findCandidate(A)
		if self.isMajority(A, cand) == True:
			return cand
		else:
			return -1


class Solution:

	def majorityElement(self, A, N):
		d = dict()
		for element in A:
			if element in d:
				d[element] += 1
			else:
				d[element] = d.get(element, 0) + 1
		for element in d:
			if d[element] > N / 2:
				return element
		return -1


class Solution:

	def majorityElement(self, arr, n):
		d = {}
		m = -1
		ans = -1
		if n == 1:
			return arr[0]
		for i in arr:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		for (i, j) in d.items():
			if j > n // 2:
				return i
		return -1


class Solution:

	def majorityElement(self, A, N):
		maj = 0
		count = 0
		for i in range(N):
			if count == 0:
				maj = A[i]
			if maj == A[i]:
				count += 1
			else:
				count -= 1
		count = 0
		for i in range(N):
			if maj == A[i]:
				count += 1
		if count > N / 2:
			return maj
		return -1


class Solution:

	def majorityElement(self, A, N):
		count = 0
		num = 0
		for i in range(N):
			if count == 0:
				num = A[i]
				count += 1
			elif num == A[i]:
				count += 1
			else:
				count -= 1
		c = 0
		for i in range(N):
			if A[i] == num:
				c += 1
		if c > N // 2:
			return num
		else:
			return -1


class Solution:

	def majorityElement(self, A, N):
		dict1 = {}
		maj = -1
		majVal = -1
		if N == 1:
			return A[0]
		for i in range(N):
			if A[i] in dict1:
				dict1[A[i]] += 1
			else:
				dict1[A[i]] = 1
		for key in dict1:
			if dict1[key] > maj:
				maj = dict1[key]
				majVal = key
		if maj > N // 2:
			return majVal
		else:
			return -1


class Solution:

	def majorityElement(self, a, N):
		d = {}
		for n in a:
			if n in d:
				d[n] = d[n] + 1
			else:
				d[n] = 1
		for n in a:
			if d[n] > N / 2:
				return n
		return -1


class Solution:

	def majorityElement(self, A, N):
		max = A[0]
		occur = 1
		for i in range(1, len(A)):
			if occur == 0:
				occur += 1
				max = A[i]
			elif A[i] == max:
				occur += 1
			else:
				occur -= 1
		if A.count(max) > N / 2:
			return max
		return -1


class Solution:

	def majorityElement(self, A, N):
		dic = {}
		for i in A:
			dic[i] = 1 + dic.get(i, 0)
		for (k, v) in dic.items():
			if v > N // 2:
				return k
		return -1


class Solution:

	def majorityElement(self, A, N):
		n = len(A)
		freq = {}
		for num in A:
			freq[num] = freq.get(num, 0) + 1
		for (num, count) in freq.items():
			if count > n // 2:
				return num
		return -1


from collections import Counter

class Solution:

	def majorityElement(self, A, N):
		f = Counter(A)
		for (i, j) in f.items():
			if j > N // 2:
				return i
		return -1


class Solution:

	def majorityElement(self, A, N):
		count = {}
		for a in A:
			if a in count:
				count[a] = count[a] + 1
			else:
				count[a] = 1
		for (k, v) in count.items():
			if v > N / 2:
				return k
		return -1


class Solution:

	def majorityElement(self, A, N):
		count = 1
		i = 1
		candidate = A[0]
		while i < len(A):
			if candidate == A[i]:
				count += 1
			else:
				count -= 1
			if count == 0:
				candidate = A[i]
				count = 1
			i += 1
		count = 0
		for ele in A:
			if candidate == ele:
				count += 1
		if count > N // 2:
			return candidate
		return -1


class Solution:

	def majorityElement(self, A, N):
		c = 0
		majr = 0
		for i in range(0, N):
			if c == 0:
				majr = i
				c = 1
			elif A[majr] == A[i]:
				c = c + 1
			else:
				c = c - 1
		C = 0
		for i in range(len(A)):
			if A[majr] == A[i]:
				c = c + 1
		if c > N // 2:
			return A[majr]
		return -1


class Solution:

	def majorityElement(self, A, N):
		count = 0
		candidate = None
		for i in range(N):
			if count == 0:
				candidate = A[i]
				count = 1
			elif A[i] == candidate:
				count += 1
			else:
				count -= 1
		count = 0
		for i in range(N):
			if A[i] == candidate:
				count += 1
		if count > N / 2:
			return candidate
		else:
			return -1


from collections import Counter

class Solution:

	def majorityElement(self, A, N):
		m = {}
		for n in A:
			m[n] = m.get(n, 0) + 1
			if m[n] > N // 2:
				return n
		return -1


class Solution:

	def majorityElement(self, A, N):
		majcnt = 0
		majele = -1
		for i in A:
			if majcnt == 0:
				majele = i
				majcnt = 1
			elif majele == i:
				majcnt += 1
			else:
				majcnt -= 1
		cnt = 0
		for i in A:
			if i == majele:
				cnt += 1
		if cnt > N // 2:
			return majele
		else:
			return -1


class Solution:

	def majorityElement(self, A, N):
		mapp = {}
		mid = N // 2
		for i in range(N):
			if A[i] in mapp:
				mapp[A[i]] += 1
			else:
				mapp[A[i]] = 1
		for k in mapp.keys():
			if mapp[k] > mid:
				return k
		return -1


class Solution:

	def possible(self, l, n):
		val = l[0]
		cnt = 1
		for i in range(1, n):
			if l[i] == val:
				cnt += 1
			else:
				cnt -= 1
			if cnt == 0:
				val = l[i]
				cnt = 1
		return val

	def majorityElement(self, A, N):
		val = self.possible(A, N)
		return val if A.count(val) > N // 2 else -1


class Solution:

	def majorityElement(self, A, N):
		d = {}
		count = 0
		for i in A:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		for (items, value) in d.items():
			if value > N / 2:
				return items
		return -1


class Solution:

	def majorityElement(self, A, N):
		element = None
		counter = 0
		for i in range(N):
			if counter == 0:
				counter = 1
				element = A[i]
			elif element == A[i]:
				counter += 1
			else:
				counter -= 1
		new_count = 0
		for i in range(N):
			if A[i] == element:
				new_count += 1
		if new_count > N // 2:
			return element
		else:
			return -1


class Solution:

	def majorityElement(self, A, N):
		freq_dict = {}
		for i in A:
			if i in freq_dict:
				freq_dict[i] += 1
			else:
				freq_dict[i] = 1
		for (i, count) in freq_dict.items():
			if count > N // 2:
				return i
		return -1


class Solution:

	def majorityElement(self, A, N):
		if N == 1:
			return A[0]
		Map = {}
		for ele in A:
			if ele in Map:
				Map[ele] += 1
				if Map[ele] > N / 2:
					return ele
			else:
				Map[ele] = 1
		return -1


class Solution:

	def majorityElement(self, A, N):
		d = {}
		for e in A:
			if e in d:
				d[e] = d[e] + 1
			else:
				d[e] = 1
			if d[e] > N / 2:
				return e
		return -1


from collections import Counter

class Solution:

	def majorityElement(self, A, N):
		counter = Counter(A)
		for (num, freq) in counter.items():
			if freq > N / 2:
				return num
		return -1


class Solution:

	def majorityElement(self, A, N):
		d = {}
		f = 0
		ans = 0
		for ele in A:
			if ele in d.keys():
				d[ele] += 1
			else:
				d[ele] = 1
		for keys in d.keys():
			if d[keys] > N / 2:
				ans = keys
				f = 0
				break
			else:
				f = 1
		if f == 0:
			return ans
		else:
			return -1


class Solution:

	def majorityElement(self, A, n):
		dic = {}
		ans = -1
		for i in A:
			if i not in dic:
				dic[i] = 1
			else:
				dic[i] += 1
		for (key, value) in dic.items():
			if value > n // 2:
				ans = key
		return ans


class Solution:

	def majorityElement(self, A, N):
		c = {}
		for i in A:
			c[i] = c.get(i, 0) + 1
			if c[i] > N / 2:
				return i
		return -1


class Solution:

	def majorityElement(self, A, N):
		count_dict = {}
		for elem in A:
			count_dict[elem] = count_dict.get(elem, 0) + 1
			if count_dict[elem] > N / 2:
				return elem
		return -1


class Solution:

	def find_majority_candidate(self, A, N):
		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]

	def is_majority_candidate(self, A, N, a):
		n = N // 2
		count = 0
		for i in range(N):
			if A[i] == a:
				count += 1
		if count > n:
			return True
		return False

	def majorityElement(self, A, N):
		a = self.find_majority_candidate(A, N)
		f = self.is_majority_candidate(A, N, a)
		if f:
			return a
		return -1


class Solution:

	def majorityElement(self, A, N):
		A.sort()
		n = N // 2
		i = 0
		while i < N:
			j = i
			if i + 1 < N and A[i] == A[i + 1]:
				while i + 1 < N and A[i] == A[i + 1]:
					i = i + 1
			k = i
			if k - j + 1 > n:
				return A[i]
			i = i + 1
		return -1


class Solution:

	def majorityElement(self, A, N):
		majority = True
		dic = {}
		for i in range(N):
			if A[i] in dic:
				dic[A[i]] += 1
			else:
				dic[A[i]] = 1
		for key in dic:
			if dic[key] > N // 2:
				return key
		return -1


class Solution:

	def majorityElement(self, A, N):
		temp = N // 2
		hashed = {}
		for i in A:
			hashed[i] = 1 + hashed.get(i, 0)
		for i in hashed:
			if hashed[i] > temp:
				return i
		return -1


from collections import Counter

class Solution:

	def majorityElement(self, A, N):
		A = Counter(A)
		max = N // 2
		v = 0
		for (i, j) in A.items():
			if j > max:
				max = j
				v = i
		if v == 0:
			return -1
		else:
			return v


from collections import defaultdict

class Solution:

	def majorityElement(self, A, N):
		count = 0
		maxcount = 0
		for i in range(0, N):
			if count == 0:
				count = 1
				ele = A[i]
			elif ele == A[i]:
				count += 1
			else:
				count -= 1
		for val in A:
			if val == ele:
				maxcount += 1
		return ele if maxcount > N // 2 else -1


from collections import defaultdict

class Solution:

	def majorityElement(self, A, N):
		hmap = defaultdict(int)
		for i in range(0, N):
			if A[i] not in hmap:
				hmap[A[i]] = 1
			else:
				hmap[A[i]] += 1
		for (k, v) in hmap.items():
			if v > N // 2:
				return k
		return -1


class Solution:

	def majorityElement(self, A, N):
		dict_ = dict()
		for number in A:
			dict_[number] = dict_.get(number, 0) + 1
		for number in A:
			if dict_[number] > N // 2:
				return number
		return -1


from collections import Counter

class Solution:

	def majorityElement(self, A, N):
		counterA = Counter(A)
		rep = N // 2
		for (i, j) in counterA.items():
			if j > rep:
				return i
		if rep + 1 not in counterA.values():
			return -1


class Solution:

	def majorityElement(self, A, N):
		dict = {}
		for num in A:
			if num not in dict:
				dict[num] = 1
			else:
				dict[num] += 1
		maxCount = max(dict, key=dict.get)
		if dict[maxCount] > N // 2:
			return maxCount
		else:
			return -1


from collections import Counter

class Solution:

	def majorityElement(self, A, N):
		counterA = Counter(A)
		target = N // 2
		for (indx, val) in counterA.items():
			if val > target:
				return indx
		return -1


class Solution:

	def majorityElement(self, A, N):
		count = 1
		maj_ele = A[0]
		for i in range(1, N):
			num = A[i]
			if num == maj_ele:
				count += 1
			else:
				count -= 1
			if count == 0:
				count = 1
				maj_ele = num
		total = 0
		for num in A:
			if num == maj_ele:
				total += 1
		if total > int(N / 2):
			return maj_ele
		return -1


class Solution:

	def majorityElement(self, A, N):
		A.sort()
		mid = A[N // 2]
		if A.count(mid) > N // 2:
			return mid
		else:
			return -1


class Solution:

	def majorityElement(self, A, N):
		hashmap = {}
		for i in A:
			hashmap[i] = 1 + hashmap.get(i, 0)
		for (key, value) in hashmap.items():
			if value > N // 2:
				return key
		else:
			return -1


class Solution:

	def majorityElement(self, a, n):
		count = 0
		b = 0
		for i in range(0, n):
			if count == 0:
				count = 1
				b = a[i]
			elif a[i] == b:
				count += 1
			else:
				count -= 1
		count1 = 0
		for i in range(0, n - 1):
			if a[i] == b:
				count += 1
		if count > n // 2:
			return b
		return -1


class Solution:

	def majorityElement(self, A, N):
		d = {}
		for i in range(N):
			if N == 1:
				return A[0]
			if A[i] not in d:
				d[A[i]] = 1
			else:
				d[A[i]] += 1
			if d[A[i]] > N / 2 and d[A[i]] != 1:
				return A[i]
		return -1


class Solution:

	def majorityElement(self, A, N):
		A.sort()
		x = 0
		x1 = A[0]
		for i in A:
			if i == x1:
				x = x + 1
				if x > N // 2:
					return i
			else:
				x1 = i
				x = 1
		return -1


class Solution:

	def majorityElement(self, A, N):
		lis = {}
		x = N // 2
		for i in A:
			if i in lis:
				lis[i] = lis[i] + 1
			else:
				lis[i] = 1
			if lis[i] > x:
				return i
		return -1


class Solution:

	def majorityElement(self, A, N):
		(m1, c1) = (None, 0)
		for i in A:
			if i == m1:
				c1 += 1
			elif c1 == 0:
				m1 = i
				c1 = 1
			else:
				c1 -= 1
		ans = -1
		if A.count(m1) > N / 2:
			ans = m1
		return ans


class Solution:

	def majorityElement(self, A, N):
		d = {}
		ans = -1
		for i in range(N):
			if A[i] not in d:
				d[A[i]] = 1
			else:
				d[A[i]] = d[A[i]] + 1
		for k in d:
			if d[k] > N / 2:
				ans = k
				break
		return ans


class Solution:

	def majorityElement(self, A, N):
		count = {}
		(res, maxcount) = (-1, 0)
		for n in A:
			count[n] = 1 + count.get(n, 0)
			res = n if count[n] > maxcount else res
			maxcount = max(maxcount, count[n])
		return res if maxcount > N / 2 else -1


class Solution:

	def majorityElement(self, A, N):
		dic = {}
		ans = -1
		maxi = 0
		if N == 1:
			return A[0]
		for ele in A:
			if ele in dic:
				dic[ele] += 1
			else:
				dic[ele] = 1
		for x in dic:
			if dic[x] > N // 2:
				maxi = dic[x]
				ans = x
		if maxi == 1:
			return -1
		else:
			return ans


class Solution:

	def majorityElement(self, A, N):
		cnt = 0
		cur = 0
		for i in range(N):
			if cnt == 0:
				cur = A[i]
				cnt = 1
			elif cur == A[i]:
				cnt += 1
			else:
				cnt -= 1
		c = 0
		for el in A:
			if el == cur:
				c += 1
		return cur if c > N // 2 else -1


from collections import Counter

class Solution:

	def majorityElement(self, A, N):
		k = N // 2
		dic = Counter(A)
		for (key, v) in dic.items():
			if dic[key] > k:
				return key
		return -1


class Solution:

	def majorityElement(self, A, N):
		if N == 1:
			return A[0]
		A.sort()
		count = 1
		curr = A[0]
		for idx in range(1, N):
			if A[idx] == curr:
				count += 1
			else:
				count = 1
				curr = A[idx]
			if count > N / 2:
				return curr
		return -1


class Solution:

	def majorityElement(self, A, N):
		s = N // 2
		max = -1
		ans = -1
		if N == 1:
			return A[0]
		d = dict()
		for i in A:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		for i in d:
			if d[i] > N // 2:
				max = 1
				ans = i
		if max == -1:
			return -1
		else:
			return ans


from collections import *

class Solution:

	def majorityElement(self, A, N):
		dic = Counter(A)
		maj = 0
		num = 0
		for (key, val) in dic.items():
			if val > maj:
				maj = val
				num = key
		if maj > N / 2:
			return num
		return -1


from collections import defaultdict
import math

class Solution:

	def majorityElement(self, A, N):
		d = defaultdict(int)
		for i in A:
			d[i] += 1
		for i in d:
			if d[i] > N / 2:
				return i
		return -1


class Solution:

	def majorityElement(self, A, N):
		freq = {}
		for i in A:
			if i not in freq:
				freq[i] = 1
			else:
				freq[i] += 1
		for key in freq:
			if freq[key] > N // 2:
				return key
		return -1