You are given a list of integers nums where each number represents a vote to a candidate. Return the ids of the candidates that have greater than n/3 votes, If there's not a majority vote, return -1. 
Example 1:
Input:
n = 11
nums = [2, 1, 5, 5, 5, 5, 6, 6, 6, 6, 6]
Output:
[5,6]
Explanation:
5 and 6 occur more n/3 times.
 
Example 2:
Input:
n=5
nums = [1,2,3,4,5]
Output:
[-1]
Your Task:
You don't need to read input or print anything. Your task is to complete the function Solve() which takes a integer n denoting a number of element and a list of numbers and return the list of number which occur more than n/3 time.
Expected Time Complexity: O(n)
Expected Space Complexity: O(1)
Constraint:
1 <=  n  <= 5 * 10^{4}
-10^{9} <= nums[i] <= 10^{9}

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Starter code: #User function Template for python3



class Solution:

    def Solve(self, n, a):

        # Code here

Solutions:
class Solution:

	def Solve(self, n, a):
		(count1, count2) = (0, 0)
		(element1, element2) = (0, 0)
		for num in a:
			if count1 == 0 and element2 != num:
				count1 += 1
				element1 = num
			elif num == element1:
				count1 += 1
			elif count2 == 0 and element1 != num:
				count2 += 1
				element2 = num
			elif num == element2:
				count2 += 1
			else:
				count1 -= 1
				count2 -= 1
		finalAnswer = []
		finalCount1 = 0
		finalCount2 = 0
		for num in a:
			if num == element1:
				finalCount1 += 1
			if num == element2:
				finalCount2 += 1
		if finalCount1 > n // 3:
			finalAnswer.append(element1)
		if finalCount2 > n // 3:
			finalAnswer.append(element2)
		return finalAnswer if len(finalAnswer) > 0 else [-1]


class Solution:

	def Solve(self, n, a):
		d = []
		for i in range(0, len(a)):
			if a.count(a[i]) > n // 3:
				if a[i] not in d:
					d.append(a[i])
		if len(d) != 0:
			return d
		else:
			d.append(-1)
			return d


from collections import Counter

class Solution:

	def Solve(self, n, a):
		cnt = Counter(a)
		lst = []
		for (tg, val) in cnt.items():
			if val > n / 3:
				lst.append(tg)
		if len(lst) == 0:
			lst.append(-1)
		return lst


class Solution:

	def Solve(self, n, a):
		c = n // 3
		obj = {}
		arr = []
		for i in a:
			if i in obj:
				obj[i] = obj[i] + 1
			else:
				obj[i] = 1
			if obj[i] > c:
				if i not in arr:
					arr.append(i)
		if len(arr) == 0:
			return [-1]
		return arr


class Solution:

	def Solve(self, n, a):
		(cnt1, cnt2) = (0, 0)
		(el1, el2) = (None, None)
		for i in range(n):
			if cnt1 == 0 and el2 != a[i]:
				cnt1 = 1
				el1 = a[i]
			elif cnt2 == 0 and el1 != a[i]:
				cnt2 = 1
				el2 = a[i]
			elif a[i] == el1:
				cnt1 += 1
			elif a[i] == el2:
				cnt2 += 1
			else:
				cnt1 -= 1
				cnt2 -= 1
		ls = []
		(cnt1, cnt2) = (0, 0)
		for i in range(n):
			if a[i] == el1:
				cnt1 += 1
			if a[i] == el2:
				cnt2 += 1
		mini = int(n / 3) + 1
		if cnt1 >= mini:
			ls.append(el1)
		if cnt2 >= mini:
			ls.append(el2)
		if len(ls) == 0:
			ls.append(-1)
		return ls


class Solution:

	def Solve(self, n, a):
		(count1, count2) = (0, 0)
		(element1, element2) = (None, None)
		for i in a:
			if count1 == 0 and i != element2:
				count1 += 1
				element1 = i
			elif count2 == 0 and i != element1:
				count2 += 1
				element2 = i
			elif i == element1:
				count1 += 1
			elif i == element2:
				count2 += 1
			else:
				count1 -= 1
				count2 -= 1
		count1 = a.count(element1)
		count2 = a.count(element2)
		ls = []
		if count1 > n // 3:
			ls.append(element1)
		if count2 > n // 3:
			ls.append(element2)
		if len(ls) == 0:
			ls.append(-1)
		return ls


from collections import Counter

class Solution:

	def Solve(self, n, a):
		x = Counter(a)
		r = []
		t = n // 3
		for j in x:
			if x[j] > t:
				r.append(j)
		if len(r) == 0:
			r.append(-1)
		return r


class Solution:

	def Solve(self, n, a):
		map = {}
		for i in range(n):
			if a[i] in map:
				map[a[i]] += 1
			else:
				map[a[i]] = 1
		ans = []
		for (x, y) in map.items():
			if y > n / 3:
				ans.append(x)
		if len(ans) > 0:
			return ans
		return [-1]


class Solution:

	def Solve(self, n, a):
		hashmap = {}
		ans = []
		flag = 0
		for i in a:
			hashmap[i] = 1 + hashmap.get(i, 0)
		for (key, value) in hashmap.items():
			if value > n // 3:
				ans.append(key)
				flag = 1
		return [-1] if flag == 0 else ans


class Solution:

	def Solve(self, n, a):
		(ele1, ele2) = (-1, -1)
		(cnt1, cnt2) = (0, 0)
		nums = a
		for i in range(n):
			curr = nums[i]
			if cnt1 == 0 and nums[i] != ele2:
				cnt1 = 1
				ele1 = nums[i]
			elif cnt2 == 0 and nums[i] != ele1:
				cnt2 = 1
				ele2 = nums[i]
			elif nums[i] == ele1:
				cnt1 += 1
			elif nums[i] == ele2:
				cnt2 += 1
			else:
				cnt1 -= 1
				cnt2 -= 1
		ans = []
		(cnt1, cnt2) = (0, 0)
		for i in range(n):
			if nums[i] == ele1:
				cnt1 += 1
			elif nums[i] == ele2:
				cnt2 += 1
		if cnt1 > n // 3:
			ans.append(ele1)
		if cnt2 > n // 3:
			ans.append(ele2)
		if len(ans) == 0:
			ans.append(-1)
		return ans


class Solution:

	def Solve(self, n, nums):
		ele1 = None
		cnt1 = 0
		ele2 = None
		cnt2 = 0
		for i in nums:
			if cnt1 == 0 and i != ele2:
				cnt1 = 1
				ele1 = i
			elif cnt2 == 0 and i != ele1:
				cnt2 = 1
				ele2 = i
			elif ele1 == i:
				cnt1 += 1
			elif ele2 == i:
				cnt2 += 1
			else:
				cnt1 -= 1
				cnt2 -= 1
		c1 = 0
		c2 = 0
		for i in nums:
			if i == ele1:
				c1 += 1
			if i == ele2:
				c2 += 1
		ans = []
		if len(nums) // 3 < c1:
			ans.append(ele1)
		if len(nums) // 3 < c2:
			ans.append(ele2)
		if len(ans):
			return ans
		return [-1]


from collections import Counter

class Solution:

	def Solve(self, n, a):
		n1 = len(a)
		lst = []
		n2 = n1 // 3
		d1 = {}
		for i in a:
			if i not in d1:
				d1[i] = 1
			else:
				d1[i] += 1
		for i in d1:
			if d1[i] > n2:
				lst.append(i)
		if len(lst) < 1:
			return [-1]
		else:
			return lst


class Solution(object):

	def Solve(self, n, nums):
		candidate1 = candidate2 = 0
		count1 = count2 = 0
		for num in nums:
			if num == candidate1:
				count1 += 1
			elif num == candidate2:
				count2 += 1
			elif count1 == 0:
				candidate1 = num
				count1 += 1
			elif count2 == 0:
				candidate2 = num
				count2 += 1
			else:
				count1 -= 1
				count2 -= 1
		result = []
		for candidate in [candidate1, candidate2]:
			if nums.count(candidate) > n // 3:
				result.append(candidate)
		return result if result else [-1]


class Solution:

	def Solve(self, n, a):
		l = []
		cnt1 = 0
		cnt2 = 0
		el1 = float('-inf')
		el2 = float('-inf')
		for i in range(n):
			if cnt1 == 0 and el2 != a[i]:
				el1 = a[i]
				cnt1 = 1
			elif cnt2 == 0 and el1 != a[i]:
				el2 = a[i]
				cnt2 = 1
			elif el1 == a[i]:
				cnt1 += 1
			elif el2 == a[i]:
				cnt2 += 1
			else:
				cnt1 -= 1
				cnt2 -= 1
		cnt1 = 0
		cnt2 = 0
		for i in range(n):
			if a[i] == el1:
				cnt1 += 1
			if a[i] == el2:
				cnt2 += 1
		if cnt1 > n // 3:
			l.append(el1)
		if cnt2 > n // 3:
			l.append(el2)
		if len(l) > 0:
			return l
		else:
			return [-1]


class Solution:

	def Solve(self, n, a):
		dict1 = {}
		lst = []
		count = 0
		for i in a:
			if i in dict1:
				dict1[i] = dict1[i] + 1
			else:
				dict1[i] = 1
			if dict1[i] > n // 3:
				if i not in set(lst):
					lst.append(i)
		if len(lst) == 0:
			return [-1]
		return lst


class Solution:

	def Solve(self, n, a):
		r = n // 3
		d = dict()
		for i in a:
			d[i] = d.get(i, 0) + 1
		l = []
		for (k, v) in d.items():
			if v > r:
				l.append(k)
		if len(l) > 0:
			return l
		else:
			l.append(-1)
			return l


class Solution:

	def Solve(self, n, a):
		(f, s) = (None, None)
		(c1, c2) = (0, 0)
		for i in range(n):
			if f == a[i]:
				c1 += 1
			elif s == a[i]:
				c2 += 1
			elif c1 == 0:
				(f, c1) = (a[i], 1)
			elif c2 == 0:
				(s, c2) = (a[i], 1)
			else:
				c1 -= 1
				c2 -= 1
		(c1, c2) = (0, 0)
		for x in a:
			if x == f:
				c1 += 1
			elif x == s:
				c2 += 1
		cp = n // 3
		if c1 > cp and c2 > cp:
			return [f, s]
		elif c1 > cp:
			return [f]
		elif c2 > cp:
			return [s]
		return [-1]


class Solution:

	def Solve(self, n, a):
		d = {}
		ans = []
		for i in a:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		for x in d.keys():
			if d[x] > n // 3:
				ans.append(x)
		if len(ans) == 0:
			return [-1]
		else:
			return ans


class Solution:

	def Solve(self, n, a):
		d = {}
		l1 = []
		num = n / 3
		for i in a:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		for i in d:
			if d[i] > num:
				l1.append(i)
		if l1 == []:
			return [-1]
		else:
			return l1


class Solution:

	def Solve(self, n, a):
		hmap = {}
		result = []
		for val in a:
			hmap[val] = hmap.get(val, 0) + 1
		for (key, value) in hmap.items():
			if value > n // 3:
				result.append(key)
		return result if len(result) > 0 else [-1]


class Solution:

	def Solve(self, n, a):
		li = []
		count = 0
		prev = a[0]
		for i in sorted(a):
			if prev == i:
				count += 1
			else:
				count = 1
				prev = i
			if count > n // 3 and i not in li:
				li.append(i)
		if len(li) == 0:
			li.append(-1)
		return li


class Solution:

	def Solve(self, n, a):
		mpp = {}
		for i in a:
			if i not in mpp:
				mpp[i] = 1
			else:
				mpp[i] += 1
		x = n // 3
		li = []
		for i in mpp:
			if mpp[i] > x:
				li.append(i)
		if len(li) == 0:
			li.append(-1)
		return li


class Solution:

	def Solve(self, n, a):
		freq = {}
		ans = []
		for i in range(n):
			freq[a[i]] = freq.get(a[i], 0) + 1
		for ele in freq:
			if freq[ele] > n // 3:
				ans.append(ele)
		if len(ans) != 0:
			return ans
		else:
			return [-1]


class Solution:

	def Solve(self, n, a):
		(count1, count2) = (0, 0)
		(ele1, ele2) = (None, None)
		for ele in a:
			if count1 == 0 and ele != ele2:
				ele1 = ele
			if count2 == 0 and ele != ele1:
				ele2 = ele
			if ele == ele1:
				count1 += 1
			elif ele == ele2:
				count2 += 1
			else:
				count1 -= 1
				count2 -= 1
		res = []
		if a.count(ele1) > n // 3:
			res.append(ele1)
		if a.count(ele2) > n // 3:
			res.append(ele2)
		return res if len(res) else [-1]


class Solution:

	def Solve(self, n, a):
		c1 = 0
		c2 = 0
		l = []
		(el1, el2) = (float('-inf'), float('-inf'))
		for i in a:
			if i == el1:
				c1 += 1
			elif i == el2:
				c2 += 1
			elif c1 > 0 and c2 > 0:
				c1 -= 1
				c2 -= 1
			elif c1 == 0:
				el1 = i
				c1 = 1
			elif c2 == 0:
				el2 = i
				c2 = 1
		l = []
		if a.count(el1) > n // 3:
			l.append(el1)
		if a.count(el2) > n // 3:
			l.append(el2)
		if len(l) == 0:
			return [-1]
		return l


class Solution:

	def Solve(self, n, a):
		e1 = a[0]
		e2 = -1
		c1 = 0
		c2 = 0
		for i in range(n):
			if e1 == a[i]:
				c1 += 1
			elif e2 == a[i]:
				c2 += 1
			elif a[i] != e2 and c1 == 0:
				e1 = a[i]
				c1 += 1
			elif c2 == 0 and a[i] != e1:
				e2 = a[i]
				c2 += 1
			else:
				c1 -= 1
				c2 -= 1
		c1 = 0
		c2 = 0
		l = []
		for i in range(n):
			if a[i] == e1:
				c1 += 1
			elif a[i] == e2:
				c2 += 1
		if c1 > n // 3:
			l.append(e1)
		if c2 > n // 3:
			l.append(e2)
		if l == []:
			return [-1]
		else:
			return l


class Solution:

	def Solve(self, n, a):
		d = {}
		ar = []
		for i in a:
			d[i] = d.get(i, 0) + 1
		for (k, v) in d.items():
			if v > n / 3:
				ar.append(k)
		if len(ar) > 0:
			return ar
		return [-1]


class Solution:

	def Solve(self, n, a):
		if n == 0:
			return -1
		d = {}
		lst = list()
		for i in a:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		for i in d:
			if d[i] > n // 3:
				lst.append(i)
		if len(lst) == 0:
			lst.append(-1)
			return lst
		else:
			return lst


from collections import Counter

class Solution:

	def Solve(self, n, a):
		ans = sorted((_ for (_, __) in Counter(a).items() if __ > n // 3))
		return ans if ans else [-1]


class Solution:

	def Solve(self, n, a):
		s = {}
		p = []
		k = n // 3
		for i in a:
			if i in s:
				s[i] += 1
			else:
				s[i] = 1
		for j in s:
			if s[j] > k:
				p.append(j)
		if len(p) >= 1:
			return p
		else:
			p.append(-1)
			return p


class Solution:

	def Solve(self, n, nums):
		(n, num1, num2, cnt1, cnt2) = (len(nums), -1, -1, 0, 0)
		for num in nums:
			if num == num1:
				cnt1 += 1
			elif num == num2:
				cnt2 += 1
			elif cnt1 == 0:
				(num1, cnt1) = (num, 1)
			elif cnt2 == 0:
				(num2, cnt2) = (num, 1)
			else:
				(cnt1, cnt2) = (cnt1 - 1, cnt2 - 1)
		ans = []
		cnt1 = cnt2 = 0
		for num in nums:
			if num == num1:
				cnt1 += 1
			elif num == num2:
				cnt2 += 1
		if cnt1 > n // 3:
			ans.append(num1)
		if cnt2 > n // 3:
			ans.append(num2)
		return ans if len(ans) != 0 else [-1]


class Solution:

	def Solve(self, n, a):
		b = {}
		for i in a:
			if i not in b:
				b[i] = 1
			else:
				b[i] += 1
		c = []
		sort = sorted(b, key=lambda x: b[x], reverse=True)
		for i in sort:
			if b[i] > n // 3:
				c += [i]
		c.sort()
		if len(c) > 0:
			return c
		return [-1]


class Solution:

	def Solve(self, n, nums):
		number1 = -1
		number2 = -1
		count1 = 0
		count2 = 0
		for num in nums:
			if num == number1:
				count1 += 1
			elif num == number2:
				count2 += 1
			elif count1 == 0:
				number1 = num
				count1 = 1
			elif count2 == 0:
				number2 = num
				count2 = 1
			else:
				count1 -= 1
				count2 -= 1
		count1 = 0
		count2 = 0
		for num in nums:
			if number1 == num:
				count1 += 1
			elif number2 == num:
				count2 += 1
		lis = []
		if count1 > len(nums) // 3:
			lis.append(number1)
		if count2 > len(nums) // 3:
			lis.append(number2)
		if len(lis) == 0:
			lis.append(-1)
			return lis
		return lis


class Solution:

	def Solve(self, n, a):
		d = {}
		num = []
		check_point = n / 3
		for elem in a:
			d.update({elem: d.get(elem, 0) + 1})
			if d[elem] > check_point:
				num.append(elem)
				d[elem] = float('-inf')
		return num if num else [-1]


class Solution:

	def Solve(self, n, a):
		n1 = -1
		c1 = 0
		n2 = -1
		c2 = 0
		for i in range(n):
			if a[i] == n1:
				c1 += 1
			elif a[i] == n2:
				c2 += 1
			elif c1 == 0:
				n1 = a[i]
				c1 = 1
			elif c2 == 0:
				n2 = a[i]
				c2 = 1
			else:
				c1 -= 1
				c2 -= 1
		lst = []
		c1 = c2 = 0
		for i in range(n):
			if a[i] == n1:
				c1 += 1
			elif a[i] == n2:
				c2 += 1
		if c1 > n // 3:
			lst.append(n1)
		if c2 > n // 3:
			lst.append(n2)
		if len(lst) == 0:
			lst.append(-1)
		return lst


class Solution:

	def Solve(self, n, a):
		count1 = 0
		count2 = 0
		ele1 = 1000000000.0
		ele2 = 1000000000.0
		ans = []
		k = n // 3
		for i in range(n):
			if count1 == 0 and a[i] != ele2:
				count1 = 1
				ele1 = a[i]
			elif count2 == 0 and a[i] != ele1:
				count2 = 1
				ele2 = a[i]
			elif a[i] == ele1:
				count1 += 1
			elif a[i] == ele2:
				count2 += 1
			else:
				count1 -= 1
				count2 -= 1
		c1 = 0
		c2 = 0
		for i in a:
			if i == ele1:
				c1 += 1
			elif i == ele2:
				c2 += 1
		if c1 > k:
			ans.append(ele1)
		if c2 > k:
			ans.append(ele2)
		if len(ans) == 0:
			return [-1]
		return ans


class Solution:

	def Solve(self, n, a):
		k = n // 3
		mp = {}
		ans = []
		for i in a:
			if not i in mp:
				mp[i] = 1
			else:
				mp[i] += 1
		for pair in mp.items():
			if pair[1] > k:
				ans.append(pair[0])
		if len(ans) == 0:
			return [-1]
		return ans


class Solution:

	def Solve(self, n, a):
		k = n // 3
		a.sort()
		ans = []
		count = 1
		for i in range(1, n):
			if a[i] == a[i - 1]:
				count += 1
			else:
				if count > k:
					ans.append(a[i - 1])
				count = 1
		if count > k:
			ans.append(a[-1])
		if len(ans) == 0:
			return [-1]
		else:
			return ans


class Solution:

	def Solve(self, n, a):
		vis_node = {}
		mp = {}
		for val in a:
			if val not in mp:
				mp[val] = 1
			else:
				mp[val] += 1
		li = []
		for val in a:
			if val not in vis_node and mp[val] > n // 3:
				li.append(val)
				vis_node[val] = 1
		if li:
			return li
		return [-1]


class Solution:

	def Solve(self, n, nums):
		dict = {}
		cut_off = n // 3
		ans = []
		for i in range(len(nums)):
			if nums[i] not in dict:
				dict[nums[i]] = 1
			else:
				dict[nums[i]] += 1
		for i in dict:
			if dict[i] > cut_off:
				ans.append(i)
		if len(ans) != 0:
			return ans
		else:
			return [-1]


class Solution:

	def Solve(self, n, a):
		counter = {}
		for i in a:
			if not i in counter:
				counter[i] = 1
			else:
				counter[i] += 1
		answer = []
		for key in counter:
			if counter[key] * 3 > n:
				answer.append(key)
		return answer if answer else [-1]


class Solution:

	def Solve(self, n, a):
		el1 = -1
		el2 = -1
		c1 = 0
		c2 = 0
		for i in a:
			if i == el1:
				c1 += 1
			elif i == el2:
				c2 += 1
			elif c1 == 0:
				el1 = i
				c1 = 1
			elif c2 == 0:
				el2 = i
				c2 = 1
			else:
				c1 -= 1
				c2 -= 1
		(c1, c2) = (0, 0)
		for nums in a:
			if el1 == nums:
				c1 += 1
			if el2 == nums:
				c2 += 1
		ans = []
		if c1 > len(a) // 3:
			ans.append(el1)
		if c2 > len(a) // 3:
			ans.append(el2)
		if len(ans) == 0:
			return [-1]
		return ans


class Solution:

	def Solve(self, n, a):
		myDict = {}
		occr = n // 3
		for num in a:
			if num not in myDict:
				myDict[num] = 1
			else:
				myDict[num] += 1
		res = []
		for key in myDict.keys():
			if myDict[key] > occr:
				res.append(key)
		if len(res) == 0:
			return [-1]
		else:
			return res


class Solution:

	def Solve(self, n, a):
		ans = []
		count1 = count2 = 0
		num1 = num2 = -1
		for num in a:
			if num == num1:
				count1 += 1
			elif num == num2:
				count2 += 1
			elif count1 == 0:
				num1 = num
				count1 += 1
			elif count2 == 0:
				num2 = num
				count2 += 1
			else:
				count1 -= 1
				count2 -= 1
		c1 = c2 = 0
		for num in a:
			if num == num1:
				c1 += 1
			elif num == num2:
				c2 += 1
		if c1 > n // 3:
			ans.append(num1)
		if c2 > n // 3:
			ans.append(num2)
		return ans if ans else [-1]


class Solution:

	def Solve(self, n, a):
		ans = []
		hashmap = {}
		for num in a:
			hashmap[num] = hashmap.get(num, 0) + 1
		for key in hashmap:
			if hashmap.get(key) > n // 3:
				ans.append(key)
		return ans if ans else [-1]


from collections import Counter

class Solution:

	def Solve(self, n, a):
		l = []
		arr = Counter(a)
		for i in range(len(a)):
			if arr[a[i]] > int(n / 3):
				l.append(a[i])
		if len(l) >= 1:
			return list(set(l))
		return [-1]


class Solution:

	def Solve(self, n, a):
		candid1 = candid2 = None
		life1 = life2 = 0
		ans = []
		for num in a:
			if candid1 == num:
				life1 += 1
			elif candid2 == num:
				life2 += 1
			elif life1 == 0:
				candid1 = num
				life1 = 1
			elif life2 == 0:
				candid2 = num
				life2 = 1
			else:
				life1 -= 1
				life2 -= 1
		life1 = life2 = 0
		for num in a:
			if candid1 == num:
				life1 += 1
			elif candid2 == num:
				life2 += 1
		if life1 > n // 3:
			ans.append(candid1)
		if life2 > n // 3:
			ans.append(candid2)
		if len(ans) > 0:
			return ans
		else:
			return [-1]


class Solution:

	def Solve(self, n, a):
		l = []
		for i in a:
			if a.count(i) > n / 3:
				l.append(i)
		l = set(l)
		if len(l) == 0:
			return [-1]
		return l


from collections import Counter, OrderedDict

class Solution:

	def Solve(self, n, a):
		(cnt1, cnt2, ele1, ele2) = (0, 0, 0, 0)
		l = []
		for i in a:
			if cnt1 == 0:
				ele1 = i
				cnt1 += 1
			elif cnt2 == 0:
				ele2 = i
				cnt2 += 1
			elif ele1 == i:
				cnt1 += 1
			elif ele2 == i:
				cnt2 += 1
			else:
				cnt1 -= 1
				cnt2 -= 1
		(cnt1, cnt2) = (0, 0)
		for i in a:
			if ele1 == i:
				cnt1 += 1
			elif ele2 == i:
				cnt2 += 1
		if cnt1 > n // 3:
			l.append(ele1)
		if cnt2 > n // 3:
			l.append(ele2)
		if l == []:
			return [-1]
		return l


from collections import Counter

class Solution:

	def Solve(self, n, a):
		m = dict(Counter(a))
		l = []
		for (i, j) in m.items():
			if j > n / 3:
				l.append(i)
		if l == []:
			l.append(-1)
		return l


class Solution:

	def Solve(self, n, a):
		total = n // 3
		dicti = {}
		arr = []
		for i in range(n):
			if a[i] in dicti:
				dicti[a[i]] += 1
			else:
				dicti[a[i]] = 1
		for (k, v) in dicti.items():
			if v > total:
				arr.append(k)
		if len(arr) >= 1:
			return arr
		else:
			return [-1]


class Solution:

	def Solve(self, n, a):
		dic = {}
		u = n // 3
		arr = []
		for i in a:
			if i in dic:
				dic[i] += 1
			else:
				dic[i] = 1
		for l in dic.keys():
			if dic[l] > u:
				arr.append(l)
		if len(arr) == 0:
			arr.append(-1)
			return arr
		return arr


class Solution:

	def Solve(self, n, a):
		d = {}
		for i in a:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		l = []
		for i in d:
			if d[i] > n // 3:
				l.append(i)
		if len(l):
			return l
		return [-1]


class Solution:

	def Solve(self, n, a):
		num1 = num2 = -1
		c1 = c2 = 0
		for i in a:
			if i == num1:
				c1 += 1
			elif i == num2:
				c2 += 1
			elif c1 == 0:
				num1 = i
				c1 = 1
			elif c2 == 0:
				num2 = i
				c2 = 1
			else:
				c1 -= 1
				c2 -= 1
		ans = []
		flag = 0
		if a.count(num1) > n // 3:
			ans.append(num1)
			flag = 1
		if a.count(num2) > n // 3:
			ans.append(num2)
			flag = 1
		if flag == 0:
			return [-1]
		else:
			return ans


class Solution:

	def Solve(self, n, a):
		cnt1 = 0
		first = -1
		sec = -1
		cnt2 = 0
		for i in range(n):
			if a[i] == first:
				cnt1 += 1
			elif a[i] == sec:
				cnt2 += 1
			elif cnt1 == 0:
				first = a[i]
				cnt1 += 1
			elif cnt2 == 0:
				sec = a[i]
				cnt2 += 1
			else:
				cnt1 -= 1
				cnt2 -= 1
		f_c = a.count(first)
		s_c = a.count(sec)
		res = []
		if f_c > n // 3:
			res.append(first)
		if s_c > n // 3:
			res.append(sec)
		if res:
			return res
		return [-1]


class Solution:

	def Solve(self, n, a):
		d = {}
		out = []
		for e in a:
			if a.count(e) > n // 3:
				d[e] = 1
		for e in d:
			if d[e] == 1:
				out.append(e)
		if len(out) == 0:
			out = [-1]
		return out


class Solution:

	def Solve(self, n, a):
		num1 = -1
		num2 = -1
		c1 = 0
		c2 = 0
		for i in range(n):
			if a[i] == num1:
				c1 += 1
			elif a[i] == num2:
				c2 += 1
			elif c1 == 0:
				num1 = a[i]
				c1 += 1
			elif c2 == 0:
				num2 = a[i]
				c2 += 1
			else:
				c1 -= 1
				c2 -= 1
		res = []
		c1 = c2 = 0
		for i in range(n):
			if a[i] == num1:
				c1 += 1
			elif a[i] == num2:
				c2 += 1
		if c1 > n // 3:
			res.append(num1)
		if c2 > n // 3:
			res.append(num2)
		if len(res) > 0:
			return res
		return [-1]


class Solution:

	def Solve(self, n, a):
		m = max(a)
		hash = [0] * (m + 1)
		l = []
		k = [-1]
		sum = 0
		for i in range(n):
			hash[a[i]] += 1
		for j in range(m + 1):
			if hash[j] > n / 3:
				l.append(j)
				sum += 1
			else:
				continue
		if sum == 0:
			return k
		else:
			return l


class Solution:

	def Solve(self, n, a):
		majority = n / 3
		s = {}
		for i in a:
			if i in s:
				s[i] += 1
			else:
				s[i] = 1
		list = []
		for k in s:
			if s[k] > majority:
				list.append(k)
		if list == []:
			return [-1]
		return list


class Solution:

	def Solve(self, n, a):
		freq = {}
		for el in a:
			if el in freq:
				freq[el] += 1
			else:
				freq[el] = 1
		res = []
		for (el, f) in freq.items():
			if f > n / 3:
				res.append(el)
		if len(res) == 0:
			return [-1]
		return res


import collections

class Solution:

	def Solve(self, n, a):
		list1 = []
		freq = collections.Counter(a)
		for (key, value) in freq.items():
			if value > n // 3:
				list1.append(key)
		if len(list1) == 0:
			return [-1]
		else:
			return list1


from collections import Counter

class Solution:

	def Solve(self, n, arr):
		a = Counter(arr)
		res = []
		for (i, j) in a.items():
			if j > n // 3:
				res.append(i)
		return res if res else [-1]


class Solution:

	def Solve(self, n, a):
		from collections import Counter
		x = len(a) // 3
		ans = []
		dic = Counter(a)
		for i in dic.keys():
			if dic[i] > x:
				ans.append(i)
		if ans:
			return ans
		return [-1]


class Solution:

	def Solve(self, n, a):
		A = list(set(a))
		l = []
		for i in A:
			if a.count(i) > n / 3:
				l.append(i)
		if l == []:
			return [-1]
		else:
			return l


class Solution:

	def Solve(self, n, nums):
		dt = {}
		for i in nums:
			if i in dt:
				dt[i] += 1
			else:
				dt[i] = 1
		n = len(nums) / 3
		res = []
		for (key, value) in dt.items():
			if value > n:
				res.append(key)
		if len(res) > 0:
			return res
		else:
			res.append(-1)
			return res


from collections import Counter

class Solution:

	def Solve(self, n, a):
		s = []
		c = Counter(a)
		for k in c:
			if c[k] > n / 3:
				s.append(k)
		if s:
			return s
		else:
			return [-1]


class Solution:

	def Solve(self, n, a):
		d = {}
		for i in a:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		l = []
		for i in a:
			if d[i] > n / 3:
				l.append(i)
		x = set(l)
		y = list(x)
		if len(y) == 0:
			y.append(-1)
			return y
		else:
			return y


class Solution:

	def Solve(self, N, nums):
		if not nums:
			return []
		(count1, count2, candidate1, candidate2) = (0, 0, 0, 1)
		for n in nums:
			if n == candidate1:
				count1 += 1
			elif n == candidate2:
				count2 += 1
			elif count1 == 0:
				(candidate1, count1) = (n, 1)
			elif count2 == 0:
				(candidate2, count2) = (n, 1)
			else:
				(count1, count2) = (count1 - 1, count2 - 1)
		ans = [n for n in (candidate1, candidate2) if nums.count(n) > len(nums) // 3]
		ans.sort()
		return ans if ans else [-1]


from collections import Counter

class Solution:

	def Solve(self, n, a):
		res = []
		count = Counter(a)
		key = n // 3
		for i in count.keys():
			if count[i] > key:
				res.append(i)
		if res:
			return res
		else:
			return [-1]


class Solution:

	def Solve(self, n, a):
		nums = a
		x = len(nums) // 3
		dic = {}
		l = []
		for i in nums:
			if i in dic:
				dic[i] += 1
			else:
				dic[i] = 1
		k = []
		for (i, j) in dic.items():
			if j > x:
				k.append(i)
		if len(k) > 0:
			return k
		else:
			return [-1]


class Solution:

	def Solve(self, n, a):
		b = []
		if n == 0:
			return [-1]
		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 // 3:
				b.append(i)
		if len(b) < 1:
			return [-1]
		return b


class Solution:

	def Solve(self, n, a):
		temp = dict()
		m = int(n / 3)
		for i in a:
			if temp.get(i) == None:
				temp[i] = 1
			else:
				temp[i] = temp[i] + 1
		ans = []
		for i in temp:
			if temp[i] > m:
				ans.append(i)
		if len(ans) == 0:
			return [-1]
		return ans


from collections import Counter

class Solution:

	def Solve(self, n, a):
		c = Counter(a)
		f = []
		for i in c:
			if c[i] > n / 3:
				f.append(i)
		if len(f) != 0:
			return f
		else:
			return [-1]


class Solution:

	def Solve(self, n, a):
		res = []
		d = {}
		s = int(n / 3)
		for i in a:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		for (i, j) in d.items():
			if j > s:
				res.append(i)
		if len(res) > 0:
			return res
		else:
			return [-1]


class Solution:

	def Solve(self, n, a):
		ans = []
		num1 = -1000
		num2 = -1000
		c1 = 0
		c2 = 0
		for item in a:
			if item == num1:
				c1 += 1
			elif item == num2:
				c2 += 1
			elif c1 == 0:
				num1 = item
				c1 = 1
			elif c2 == 0:
				num2 = item
				c2 = 0
			else:
				c1 -= 1
				c2 -= 1
		(count1, count2) = (0, 0)
		for item in a:
			if item == num1:
				count1 += 1
			if item == num2:
				count2 += 1
		if count1 > len(a) // 3:
			ans.append(num1)
		if count2 > len(a) // 3:
			ans.append(num2)
		ans = sorted(ans)
		if ans:
			return ans
		else:
			ans = [-1]
			return ans


class Solution:

	def Solve(self, n, a):
		ans = []
		ll = set(a)
		for i in ll:
			if a.count(i) > n // 3:
				ans.append(i)
		return [-1] if len(ans) == 0 else ans


class Solution:

	def Solve(self, n, arr):
		dic = {}
		for i in arr:
			if i in dic:
				dic[i] += 1
			else:
				dic[i] = 1
		majority = []
		for i in dic:
			if dic[i] > n // 3:
				majority.append(i)
		if majority:
			return majority
		majority.append(-1)
		return majority


class Solution:

	def Solve(self, n, a):
		arr = []
		ele1 = -1
		ele2 = -1
		count1 = 0
		count2 = 0
		for i in range(n):
			if a[i] == ele1:
				count1 += 1
			elif a[i] == ele2:
				count2 += 1
			elif count1 == 0:
				ele1 = a[i]
				count1 = 1
			elif count2 == 0:
				ele2 = a[i]
				count2 = 1
			else:
				count1 -= 1
				count2 -= 1
		flag = 0
		if n >= 1 and a.count(ele1) > n // 3:
			arr.append(ele1)
			flag = 1
		if n > 1 and a.count(ele2) > n // 3:
			arr.append(ele2)
			flag = 1
		if flag != 1:
			arr.append(-1)
		return arr


class Solution:

	def Solve(self, n, a):
		h = {}
		for i in range(n):
			if a[i] in h.keys():
				h[a[i]] += 1
			else:
				h[a[i]] = 1
		k = []
		for i in h:
			if h[i] > n / 3:
				k += [i]
		if not k:
			k += [-1]
		return k


class Solution:

	def Solve(self, n, a):
		max = n / 3
		h = dict()
		for i in a:
			c = h.get(i, 0)
			h[i] = c + 1
		r = [i for (i, j) in h.items() if j > max]
		return r if len(r) > 0 else [-1]


class Solution:

	def Solve(self, n, a):
		s = list(set(a))
		a.sort()
		l = []
		for i in s:
			z = a.count(i)
			if z > n / 3:
				l.append(i)
		if l == []:
			return [-1]
		return l


class Solution:

	def Solve(self, n, arr):
		(cand1, count1) = (None, 0)
		(cand2, count2) = (None, 0)
		for i in arr:
			if cand1 == i:
				count1 += 1
			elif cand2 == i:
				count2 += 1
			elif count1 == 0:
				cand1 = i
				count1 += 1
			elif count2 == 0:
				cand2 = i
				count2 += 1
			else:
				(count1, count2) = (count1 - 1, count2 - 1)
		l1 = [x for x in (cand1, cand2) if arr.count(x) > n // 3]
		if len(l1) == 0:
			l1.append(-1)
			return l1
		return l1