Given an array arr containing N words consisting of lowercase characters. Your task is to find the most frequent word in the array. If multiple words have same frequency, then print the word whose first occurence occurs last in the array as compared to the other strings with same frequency.
Example 1:
Input:
N = 3
arr[] = {geeks,for,geeks}
Output: geeks
Explanation: "geeks" comes 2 times.
Example 2:
Input:
N = 2
arr[] = {hello,world}
Output: world
Explanation: "hello" and "world" both
have 1 frequency. We print world as
its first occurence comes last in the
input array.
Your Task:
Complete mostFrequentWord function which takes array of strings and its length as arguments and returns the most frequent word. The printing is done by the driver code.
Expected Time Complexity: O(N * WORD_LEN).
Expected Auxiliary Space: O(N * WORD_LEN).
Constraints:
1 <= N <= 50000
1 <= |each string| <= 50
Sum of length of every string does not exceed 5*10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: String algorithms

Data structures

Starter code: #User function Template for python3

class Solution:
    
    #Function to find most frequent word in an array of strings.
    def mostFrequentWord(self,arr,n):
        # code here


Solutions:
class Solution:

	def mostFrequentWord(self, arr, n):
		k = {}
		l = []
		for i in arr:
			if i not in k:
				k[i] = 1
				l.append(i)
			else:
				k[i] += 1
		mm = -1
		for i in k:
			if k[i] > mm:
				mm = k[i]
		l = l[::-1]
		for i in l:
			if k[i] == mm:
				return i


class Solution:

	def mostFrequentWord(self, arr, n):
		ele = dict()
		root = TrieNode()
		for i in arr:
			if self.insert(root, i):
				ele[i] = 1
			else:
				ele[i] += 1
		maxVal = ele[arr[0]]
		maxKey = arr[0]
		prr = [arr[0]]
		for i in arr:
			if maxVal <= ele[i]:
				if prr.count(i) > 0:
					continue
				if maxKey != i:
					prr.append(i)
				maxKey = i
				maxVal = ele[i]
		return maxKey

	def insert(self, root, i):
		res = False
		for x in i:
			y = ord(x) - ord('a')
			if root.child[y] == None:
				res = True
				root.child[y] = TrieNode()
			root = root.child[y]
		if root.isEndOfWord == False:
			root.isEndOfWord = True
			res = True
		return res

class TrieNode:

	def __init__(self):
		self.child = [None] * 26
		self.isEndOfWord = False


class trie_element:

	def __init__(self):
		self.nxt = [None for _ in range(26)]
		self.count = 0
		self.first_appearance = 0

class Solution:

	def mostFrequentWord(self, arr, n):
		trie = trie_element()
		max_count = 0
		the_word = ''
		the_word_first_app = 0
		for i in range(n):
			word = arr[i]
			temp = trie
			for c in word:
				index = ord(c) - ord('a')
				if temp.nxt[index] is None:
					temp.nxt[index] = trie_element()
				temp = temp.nxt[index]
			temp.count += 1
			if temp.count == 1:
				temp.first_appearance = i
			if temp.count > max_count or (temp.count == max_count and temp.first_appearance > the_word_first_app):
				max_count = temp.count
				the_word = word
				the_word_first_app = temp.first_appearance
		return the_word


import collections

class Solution:

	def mostFrequentWord(self, arr, n):
		d = {}
		for i in range(n):
			if arr[i] not in d:
				d[arr[i]] = arr.index(arr[i])
		d1 = {}
		for i in range(n):
			if arr[i] not in d1:
				d1[arr[i]] = 1
			else:
				d1[arr[i]] = d1[arr[i]] + 1
		maxmum = 0
		for el in d1.keys():
			if maxmum < d1[el]:
				maxmum = d1[el]
				word_extract = el
			elif maxmum == d1[el]:
				if d[el] > d[word_extract]:
					word_extract = el
		return word_extract


class Solution:

	def mostFrequentWord(self, arr, n):
		k = {}
		for i in arr:
			if i not in k:
				k[i] = 1
			else:
				k[i] += 1
		m = max(k.values())
		ind = 0
		ans = ''
		for i in k.keys():
			if k[i] == m and arr.index(i) >= ind:
				ans = i
				ind = arr.index(i)
		return ans


class Solution:

	def mostFrequentWord(self, arr, n):
		d = {}
		d1 = {}
		temp = 0
		for i in arr:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
			temp = max(temp, d[i])
		count = 0
		for (i, j) in d.items():
			if j == temp:
				count += 1
		for i in arr:
			if d[i] == temp:
				if i not in d1:
					d1[i] = 1
				else:
					d1[i] += 1
				if len(d1) == count:
					return i


class Solution:

	def mostFrequentWord(self, arr, n):
		freq = dict()
		ans = ''
		mx = 0
		for i in arr[::-1]:
			if i in freq:
				freq[i] += 1
			else:
				freq[i] = 1
			if freq[i] > mx:
				mx = freq[i]
				ans = i
		return ans


class Solution:

	def mostFrequentWord(self, arr, n):
		dic = {}
		for i in range(len(arr)):
			if arr[i] in dic:
				dic[arr[i]][0] += 1
			else:
				dic[arr[i]] = [1, i]
		temp = max(dic.keys(), key=lambda x: (dic[x][0], dic[x][1]))
		return temp


class TrieNode:

	def __init__(self):
		self.isEnd = False
		self.count = 0
		self.children = [None] * 26
		self.firstOccurence = -1

class Solution:

	def mostFrequentWord(self, arr, n):
		root = TrieNode()
		for (i, word) in enumerate(arr):
			self.insert(root, word, i)
		first_occurence = -1
		max_freq = 0
		res = ''
		for (i, word) in enumerate(arr):
			(freq, occurence) = self.search(root, word)
			if freq >= max_freq and occurence > first_occurence:
				res = word
				max_freq = freq
				first_occurence = occurence
		return res

	def insert(self, root, word, occ):
		cur = root
		for i in range(len(word)):
			ch = ord(word[i]) - ord('a')
			if cur.children[ch] is None:
				cur.children[ch] = TrieNode()
			cur = cur.children[ch]
		cur.isEnd = True
		if cur.count == 0:
			cur.firstOccurence = occ
		cur.count += 1

	def search(self, root, word):
		cur = root
		for i in range(len(word)):
			ch = ord(word[i]) - ord('a')
			if cur.children[ch] is None:
				return [0, -1]
			cur = cur.children[ch]
		return [cur.count, cur.firstOccurence] if cur.isEnd else [0, -1]


class Solution:

	def mostFrequentWord(self, arr, n):
		freq = dict()
		for (i, word) in enumerate(arr):
			if word in freq:
				freq[word][0] += 1
			else:
				freq[word] = [1, i]
		res = arr[0]
		for i in range(len(arr)):
			word = arr[i]
			if freq[word] >= freq[res] and freq[word][1] > freq[res][1]:
				res = word
		return res


class Solution:

	def mostFrequentWord(self, arr, n):
		d = {}
		for i in arr:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		m = max(d.values())
		b = []
		for i in arr:
			if d[i] == m and i not in b:
				b.append(i)
		v = []
		if len(b) == 1:
			return b[0]
		else:
			for i in b:
				c = arr.index(i)
				v.append(c)
			x = max(v)
			return arr[x]


from collections import OrderedDict

class Solution:

	def mostFrequentWord(self, arr, n):
		dic = OrderedDict()
		ma = 0
		for i in arr:
			dic[i] = dic.get(i, 0) + 1
			if ma < dic[i]:
				ma = dic[i]
		k = 0
		for i in dic.keys():
			if dic[i] == ma:
				k = i
		return k


from collections import Counter as c

class Solution:

	def mostFrequentWord(self, arr, n):
		l = []
		for i in range(n):
			if arr[i] not in l:
				l.append(arr[i])
		a = c(arr)
		l.reverse()
		l.sort(key=lambda x: a[x], reverse=True)
		return l[0]


class Solution:

	def mostFrequentWord(self, arr, n):
		stri = arr[0]
		maxi = 1
		ind = 0
		d = {}
		d[arr[0]] = 1
		for i in arr[1:]:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
			if d[i] > maxi:
				if i != stri:
					stri = i
					ind = arr.index(i)
				maxi = d[i]
			elif d[i] == maxi:
				index = arr.index(i)
				if ind < index:
					stri = i
					ind = index
		return stri


from collections import Counter

class Solution:

	def mostFrequentWord(self, arr, n):
		dic = {}
		max_count = 0
		max_char = None
		for i in range(n - 1, -1, -1):
			dic[arr[i]] = dic.get(arr[i], 0) + 1
			if max_count < dic[arr[i]]:
				max_count = dic[arr[i]]
				max_char = arr[i]
		return max_char


class Solution:

	def mostFrequentWord(self, arr, n):
		dic = {}
		max_count = 0
		max_char = None
		for i in range(n - 1, -1, -1):
			dic[arr[i]] = dic.get(arr[i], 0) + 1
			if max_count < dic[arr[i]]:
				max_count = dic[arr[i]]
				max_char = arr[i]
		return max_char


class Solution:

	def mostFrequentWord(self, arr, n):
		a1 = {}
		d = []
		for i in arr:
			if i not in a1:
				a1[i] = 0
				d.append(i)
			a1[i] += 1
		res = ''
		c = 0
		for i in d:
			if a1[i] >= c:
				c = a1[i]
				res = i
		return res


class Solution:

	def mostFrequentWord(self, arr, n):
		mp = {}
		for i in arr:
			if i in mp:
				mp[i] += 1
			else:
				mp[i] = 1
		ans = ''
		mx = 0
		mp2 = {}
		for j in arr:
			if mp[j] >= mx:
				if j not in mp2:
					mx = mp[j]
					ans = j
					mp2[j] = 1
		return ans


class Solution:

	def mostFrequentWord(self, arr, n):
		d = {}
		for i in range(n):
			if arr[i] in d:
				d[arr[i]][1] += 1
			else:
				d[arr[i]] = [i, 1]
		max1 = 0
		res = ''
		l = 0
		for (i, j) in d.items():
			if j[1] > max1:
				res = i
				max1 = j[1]
				l = j[0]
			elif j[1] == max1:
				if j[0] > l:
					l = j[0]
					res = i
		return res


class Solution:

	def mostFrequentWord(self, arr, n):
		d = {}
		for i in range(n):
			if arr[i] not in d:
				d[arr[i]] = [1, i]
			else:
				d[arr[i]][0] += 1
		l = list(d.values())
		l = sorted(l, reverse=True)
		a = l[0]
		for i in d:
			if d[i] == a:
				return i


class Solution:

	def mostFrequentWord(self, arr, n):
		h = {}
		maxi = 0
		for i in range(n):
			if arr[i] in h:
				h[arr[i]] += 1
			else:
				h[arr[i]] = 1
			maxi = max(maxi, h[arr[i]])
		ans = 0
		for i in arr:
			if maxi == h[i]:
				h[i] -= 1
				ans = i
		return ans


class Solution:

	def mostFrequentWord(self, arr, n):
		num = []
		count = 0
		max_count = []
		d = {}
		for i in arr:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		high_occ = max(d.values())
		res = []
		for i in d:
			if d[i] == high_occ:
				res.append(arr.index(i))
		return arr[max(res)]


from collections import Counter

class Solution:

	def mostFrequentWord(self, arr, n):
		index = 0
		a = dict(Counter(arr))
		a1 = {i for i in a if a[i] == max(a.values())}
		a1 = list(a1)
		for i in a1:
			index = max(index, arr.index(i))
		return arr[index]


import heapq

class Solution:

	def mostFrequentWord(self, arr, n):
		freq = {}
		hq = []
		for i in range(len(arr)):
			if arr[i] not in freq:
				freq[arr[i]] = [1, -i]
			else:
				freq[arr[i]][0] += 1
		for word in freq:
			heapq.heappush(hq, [-freq[word][0], freq[word][1], word])
		return heapq.heappop(hq)[2]


class Solution:

	def mostFrequentWord(self, arr, n):
		dic = {}
		for i in arr:
			s = 1
			if i not in dic:
				dic[i] = 1
			else:
				dic[i] += 1
		l = []
		s = max(dic.values())
		k = 0
		for (i, j) in dic.items():
			if j == s:
				k += 1
		s1 = 0
		for i in arr:
			if dic[i] == s and i not in l:
				s1 += 1
				l.append(i)
				if s1 == k:
					return i


class Solution:

	def mostFrequentWord(self, arr, n):
		d = {}
		for i in arr:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		k1 = -1
		for i in arr:
			if d[i] >= k1:
				k1 = d[i]
				w = i
		d1 = 0
		for (k, v) in d.items():
			if v == k1:
				d1 += 1
		j = 0
		l1 = []
		for i in arr:
			if d[i] == k1 and i not in l1:
				q = i
				j += 1
				l1.append(i)
				if j == d1:
					return i


class Solution:

	def mostFrequentWord(self, arr, n):
		freq = dict()
		occurrence = dict()
		max = 0
		result = ''
		k = 1
		for i in range(0, n):
			if arr[i] in occurrence.keys():
				continue
			occurrence[arr[i]] = k
			k += 1
		for i in range(0, n):
			if arr[i] in freq.keys():
				freq[arr[i]] += 1
			else:
				freq[arr[i]] = 1
			if max <= freq[arr[i]]:
				if max < freq[arr[i]]:
					max = freq[arr[i]]
					result = arr[i]
				elif occurrence[result] < occurrence[arr[i]]:
					max = freq[arr[i]]
					result = arr[i]
		return result


class Solution:

	def mostFrequentWord(self, arr, n):
		(hashMap, maxi) = ({}, 0)
		result = 0
		for i in arr:
			if i in hashMap:
				hashMap[i] += 1
			else:
				hashMap[i] = 1
			maxi = max(maxi, hashMap[i])
		for i in arr:
			if maxi == hashMap[i]:
				hashMap[i] -= 1
				result = i
		return result


class TrieNode:

	def __init__(self):
		self.children = [None] * 26
		self.isEndOfWord = False
		self.idx = -1
		self.times = 0

class Trie:

	def __init__(self):
		self.root = self.getNode()

	def getNode(self):
		return TrieNode()

	def _charToIndex(self, ch):
		return ord(ch) - ord('a')

	def insert(self, key, idxx):
		pCrawl = self.root
		length = len(key)
		for level in range(length):
			index = self._charToIndex(key[level])
			if not pCrawl.children[index]:
				pCrawl.children[index] = self.getNode()
			pCrawl = pCrawl.children[index]
		pCrawl.isEndOfWord = True
		if pCrawl.idx == -1:
			pCrawl.idx = idxx
		pCrawl.times += 1
		return (pCrawl.idx, pCrawl.times)

	def search(self, key):
		pCrawl = self.root
		length = len(key)
		for level in range(length):
			index = self._charToIndex(key[level])
			if not pCrawl.children[index]:
				return False
			pCrawl = pCrawl.children[index]
		return pCrawl != None and pCrawl.isEndOfWord

	def delete(self, key, i=0):
		pCrawl = self.root
		if pCrawl == None:
			return pCrawl
		length = len(key)
		if i == length:
			if pCrawl.isEndOfWord:
				pCrawl.isEndOfWord = False
			if self.isEmpty(pCrawl):
				pCrawl = None
			return pCrawl
		index = self._charToIndex(key[i])
		pCrawl.children[index] = self.delete(key, i + 1)
		if self.isEmpty(pCrawl) and pCrawl.isEndOfWord == False:
			pCrawl = None
		return pCrawl

	def isEmpty(self, root1):
		for i in root1.children:
			if i != None:
				return False
		return True
from collections import defaultdict

class Solution:

	def mostFrequentWord(self, arr, n):
		d = defaultdict(lambda : 0)
		trie = Trie()
		ans = ''
		(ch1, ch2) = (-1, 0)
		for i in range(n):
			(x, y) = trie.insert(arr[i], i)
			if y > ch2:
				ans = arr[i]
				ch2 = y
				ch1 = x
			elif y == ch2 and x > ch1:
				ans = arr[i]
				ch1 = x
		return ans


class Solution:

	def mostFrequentWord(self, arr, n):
		hash_map = {}
		count = 0
		first_occur = 0
		word = ''
		for i in range(n):
			if arr[i] not in hash_map:
				hash_map[arr[i]] = [0, i]
			hash_map[arr[i]][0] = hash_map[arr[i]][0] + 1
			if count < hash_map[arr[i]][0]:
				count = hash_map[arr[i]][0]
				first_occur = hash_map[arr[i]][1]
				word = arr[i]
			if count == hash_map[arr[i]][0]:
				if first_occur < hash_map[arr[i]][1]:
					first_occur = hash_map[arr[i]][1]
					word = arr[i]
		return word


class Solution:

	def mostFrequentWord(self, arr, n):
		times = {}
		indexes = {}
		for i in range(n):
			if arr[i] not in indexes:
				indexes[arr[i]] = i
		for word in arr:
			if word not in times:
				times[word] = 1
			else:
				times[word] += 1
		stack = []
		maxi = 0
		for word in times:
			maxi = max(maxi, times[word])
		for word in times:
			if times[word] == maxi:
				stack.append(word)
		mini = 10 ** 10
		res = None
		tar = 0
		for word in stack:
			tar = max(tar, indexes[word])
		for word in stack:
			if indexes[word] == tar:
				res = word
		return res


import collections

class Solution:

	def mostFrequentWord(self, arr, n):
		d = collections.OrderedDict()
		for i in arr:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		f = 0
		for (k, v) in d.items():
			if v >= f:
				s = k
				f = v
		return s


from collections import OrderedDict

class Solution:

	def mostFrequentWord(self, arr, n):
		d = {x: 0 for x in arr}
		s = set()
		c = -100
		for i in arr:
			d[i] += 1
		for i in d:
			if d[i] > c:
				c = d[i]
		m = 0
		for i in d:
			if d[i] == c:
				s.add(i)
				m += 1
		for i in arr:
			if i in s:
				m -= 1
				s.remove(i)
			if m == 0:
				return i


class Solution:

	def mostFrequentWord(self, arr, n):
		dic = {}
		maxi = 1
		maxii = 0
		st = arr[0]
		for i in range(n):
			if arr[i] in dic:
				dic[arr[i]][1] += 1
			else:
				dic[arr[i]] = [i, 1]
			if dic[arr[i]][1] > maxi:
				maxi = dic[arr[i]][1]
				maxii = dic[arr[i]][0]
				st = arr[i]
			if dic[arr[i]][1] == maxi:
				if maxii < dic[arr[i]][0]:
					maxii = dic[arr[i]][0]
					st = arr[i]
		return st


class Solution:

	def mostFrequentWord(self, arr, n):
		d = {}
		for i in range(n):
			if arr[i] in d:
				d[arr[i]] += 1
			else:
				d[arr[i]] = 1
		mx = 0
		ans = ''
		for i in range(n):
			if d[arr[i]] >= mx:
				mx = d[arr[i]]
				ans = arr[i]
				d[arr[i]] = 0
		return ans


import heapq

class Solution:

	def mostFrequentWord(self, arr, n):
		mp = dict()
		for (pos, item) in enumerate(arr):
			if item not in mp:
				mp[item] = [pos, 1]
			else:
				mp[item][1] += 1
		q = []
		for (key, val) in mp.items():
			freq = val[1]
			pos = val[0]
			heapq.heappush(q, (-freq, (key, pos)))
		if q:
			temp = []
			(freq, item) = heapq.heappop(q)
			temp.append([item[0], item[1]])
			while q:
				(freq1, item1) = heapq.heappop(q)
				if freq1 == freq:
					temp.append([item1[0], item1[1]])
				else:
					heapq.heappush(q, (freq1, (item1[0], item1[1])))
					break
			temp.sort(key=lambda x: x[1], reverse=True)
			return temp[0][0]


class Solution:

	def mostFrequentWord(self, arr, n):
		if n == 1:
			return arr[0]
		(res, rescount, max1, min1) = ({}, {}, float('-inf'), float('inf'))
		count = 0
		for i in arr:
			res[i] = res.get(i, 0) + 1
			if i not in rescount:
				rescount[i] = count
			count += 1
			(max1, min1) = (max(max1, res[i]), min(min1, res[i]))
		if max1 == 1:
			return arr[-1]
		else:
			temp = []
			for i in res:
				if res[i] == max1:
					temp.append(i)
			(arr, pos) = ('', float('-inf'))
			for i in temp:
				if pos < rescount[i]:
					(arr, pos) = (i, rescount[i])
		return arr


from collections import defaultdict

class Solution:

	def mostFrequentWord(self, arr, n):
		ans = ''
		count = defaultdict(int)
		highestCount = 0
		for wrd in arr[::-1]:
			count[wrd] += 1
			if count[wrd] > highestCount:
				ans = wrd
				highestCount = count[wrd]
		return ans


class Solution:

	def mostFrequentWord(self, arr, n):
		m = 0
		d = {}
		e = {}
		for (v, i) in enumerate(arr):
			if i not in d:
				d[i] = 0
				e[i] = v
			d[i] += 1
			m = max(m, d[i])
		ke = list(d.keys())
		n = -1
		ans = None
		for k in ke:
			if d[k] == m and e[k] > n:
				n = e[k]
				ans = k
		return ans


class Solution:

	def mostFrequentWord(self, arr, n):
		dic = {}
		l = []
		for i in arr:
			if i in dic:
				dic[i] += 1
			else:
				dic[i] = 1
		s = list(dic.values())
		x = max(s)
		for (k, v) in dic.items():
			if v == x:
				l.append(k)
		k = {}
		k = k.fromkeys(l, 0)
		for i in l:
			k[i] += 1
		last = []
		for i in arr:
			if i in k:
				if i not in last:
					last.append(i)
		return last.pop()


from collections import OrderedDict

class Solution:

	def mostFrequentWord(self, arr, n):
		hm = OrderedDict()
		for i in range(n):
			if arr[i] in hm:
				hm[arr[i]] += 1
			else:
				hm[arr[i]] = 1
		m = max(hm.values())
		ans = [x for (x, y) in hm.items() if y == m][-1]
		return ans


class Solution:

	def mostFrequentWord(self, arr, n):
		d = {}
		for (i, v) in enumerate(arr):
			p = d.get(v, (0, i))
			d[v] = (p[0] + 1, p[1])
		l = list(d.values())
		from operator import itemgetter as i
		l.sort(reverse=True)
		m = l[0][0]
		ind = 0
		for i in l:
			if i[0] < m:
				break
			if i[1] > ind:
				ind = i[1]
		return arr[ind]


class Solution:

	def mostFrequentWord(self, arr, n):
		ans = arr[-1]
		mx = 1
		d = {}
		for ele in arr[::-1]:
			if ele in d:
				d[ele] += 1
				if d[ele] > mx:
					mx = d[ele]
					ans = ele
			else:
				d[ele] = 1
		return ans


class Solution:

	def mostFrequentWord(self, arr, n):
		max_res = 0
		my_dict = {}
		for i in range(len(arr)):
			if arr[i] in my_dict:
				my_dict[arr[i]][0] += 1
			else:
				my_dict[arr[i]] = [1, i]
			max_res = max(max_res, my_dict[arr[i]][0])
		zero = -1
		res = None
		for (k, v) in my_dict.items():
			if v[0] == max_res and v[1] > zero:
				res = k
				zero = v[1]
		return res


class Solution:

	def mostFrequentWord(self, arr, n):
		max_res = 0
		my_dict = {}
		for i in range(len(arr)):
			t = []
			for j in arr[i]:
				t.append(j)
			t = tuple(t)
			if t in my_dict:
				my_dict[t][0] += 1
			else:
				my_dict[t] = [1, i]
			max_res = max(max_res, my_dict[t][0])
		zero = -1
		res_t = None
		for (k, v) in my_dict.items():
			if v[0] == max_res and v[1] > zero:
				res_t = k
				zero = v[1]
		res = ''
		for i in res_t:
			res += i
		return res


class Solution:

	def mostFrequentWord(self, arr, n):
		hashMap = {}
		indexMap = {}
		longest = 0
		prevIndex = float('-inf')
		output = None
		for (i, s) in enumerate(arr):
			hashMap[s] = hashMap.get(s, 0) + 1
			if hashMap[s] == 1:
				indexMap[s] = i
			if hashMap[s] > longest:
				longest = hashMap[s]
				prevIndex = indexMap[s]
				output = s
			elif hashMap[s] == longest:
				if indexMap[s] > prevIndex:
					prevIndex = indexMap[s]
					output = s
		return output


class TrieNode:

	def __init__(self):
		self.children = [None] * 26
		self.isEndOfWord = 0

class Trie:

	def __init__(self):
		self.root = self.getNode()

	def getNode(self):
		return TrieNode()

	def _charToIndex(self, ch):
		return ord(ch) - ord('a')

	def insert(self, key):
		pCrawl = self.root
		length = len(key)
		for level in range(length):
			index = self._charToIndex(key[level])
			if not pCrawl.children[index]:
				pCrawl.children[index] = self.getNode()
			pCrawl = pCrawl.children[index]
		pCrawl.isEndOfWord += 1

	def search(self, key):
		pCrawl = self.root
		length = len(key)
		for level in range(length):
			index = self._charToIndex(key[level])
			if not pCrawl.children[index]:
				return False
			pCrawl = pCrawl.children[index]
		return pCrawl.isEndOfWord

class Solution:

	def mostFrequentWord(self, arr, n):
		t = Trie()
		mx = 1
		ans = arr[-1]
		for ele in arr[::-1]:
			t.insert(ele)
			temp = t.search(ele)
			if temp > mx:
				mx = temp
				ans = ele
		return ans


class Solution:

	def mostFrequentWord(self, arr, n):
		d = {}
		for x in arr:
			if x in d:
				d[x] += 1
			else:
				d[x] = 1
		p = 0
		for x in d:
			p = max(d[x], p)
		ans = ''
		r = {}
		for x in arr:
			if d[x] == p and x not in r:
				ans = x
				r[x] = 1
		return ans


class Node:

	def __init__(self):
		self.children = [None] * 26
		self.cnt = 0
		self.flag = False

class Trie:

	def __init__(self):
		self.root = self.getNode()

	def getNode(self):
		return Node()

	def insert(self, key):
		size = len(key)
		node = self.root
		for i in range(size):
			index = ord(key[i]) - ord('a')
			if node.children[index] == None:
				node.children[index] = self.getNode()
			node = node.children[index]
		node.flag = True
		node.cnt += 1
		return node.cnt

class Solution:

	def mostFrequentWord(self, arr, n):
		t = Trie()
		result = ''
		maxi = 0
		s = arr[::-1]
		for i in range(n):
			res = t.insert(s[i])
			if res > maxi:
				result = s[i]
				maxi = res
		return result


class Solution:

	def mostFrequentWord(self, arr, n):
		map = {}
		for x in range(len(arr)):
			if arr[x] in map:
				map[arr[x]][0] = map[arr[x]][0] + 1
			else:
				map[arr[x]] = [1, x]
		max_num = [float('-inf'), -1]
		max_word = ''
		for x in map:
			if map[x][0] > max_num[0]:
				max_word = x
				max_num = map[x]
			if map[x][0] == max_num[0] and map[x][1] > max_num[1]:
				max_word = x
				max_num = map[x]
		return max_word


class Solution:

	def mostFrequentWord(self, arr, n):
		from collections import OrderedDict
		word_wise_count = OrderedDict()
		for word in arr:
			try:
				word_wise_count[word] += 1
			except KeyError:
				word_wise_count[word] = 1
		max_freq = None
		max_freq_word = None
		for (word, count) in word_wise_count.items():
			if max_freq_word is None:
				max_freq_word = word
				max_freq = count
			elif max_freq <= count:
				max_freq = count
				max_freq_word = word
		return max_freq_word


class Solution:

	def mostFrequentWord(self, arr, n):
		mp = {}
		resMax = 0
		res = ''
		for i in arr:
			if i not in mp:
				mp[i] = 1
				resMax = max(resMax, mp[i])
			else:
				mp[i] += 1
				resMax = max(resMax, mp[i])
		for var in arr:
			if mp[var] == resMax:
				res = var
				mp[var] -= 1
		return res


class Solution:

	def mostFrequentWord(self, arr, n):
		hashmapu = {}
		for i in range(n):
			hashmapu[arr[i]] = 0
		res = ''
		max_freq = 0
		for i in range(n):
			hashmapu[arr[i]] += 1
			max_freq = max(max_freq, hashmapu[arr[i]])
		for i in range(n):
			if hashmapu[arr[i]] == max_freq:
				res = arr[i]
				hashmapu[arr[i]] -= 1
		return res


from collections import Counter

class Solution:

	def mostFrequentWord(self, arr, n):
		dic = Counter(arr)
		ans = ''
		freq = 0
		for i in arr:
			if dic[i] >= freq:
				freq = dic[i]
				ans = i
				dic[i] -= 1
		return ans


class Solution:

	def mostFrequentWord(self, arr, n):
		d = {}
		for i in arr:
			if i not in d:
				d[i] = 0
			d[i] += 1
		ma = 0
		word = ''
		p = {}
		for i in arr:
			if d[i] > ma:
				(ma, word) = (d[i], i)
				p[word] = True
			if d[i] == ma:
				if i not in p:
					word = i
					p[i] = True
		return word


class Solution:

	def mostFrequentWord(self, arr, n):
		d = {}
		for i in arr:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		newd = sorted(d.items(), key=lambda item: item[1])
		report = []
		for i in newd:
			if i[1] == newd[-1][1]:
				report.append(i[0])
		max = arr.index(report[0])
		for j in report:
			if max < arr.index(j):
				max = arr.index(j)
		return arr[max]


from collections import OrderedDict

class Solution:

	def mostFrequentWord(self, arr, n):
		d = OrderedDict()
		for i in arr:
			d[i] = d.get(i, 0) + 1
		count = 0
		ans = None
		for i in d.keys():
			if d[i] >= count:
				count = d[i]
				ans = i
		return ans


class Solution:

	def mostFrequentWord(self, arr, n):
		count = 1
		dic = dict()
		for i in range(n):
			if dic.get(arr[i]):
				dic[arr[i]] += 1
				count = max(count, dic[arr[i]])
			else:
				dic[arr[i]] = 1
		ans = []
		for i in range(n):
			if dic[arr[i]] == count:
				dic[arr[i]] = 0
				ans.append(arr[i])
		return ans[-1]


class TrieNode:

	def __init__(self):
		self.chars = [None] * 26
		self.c = 0
		self.isword = False
		self.occ = -1

class Trie:

	def __init__(self):
		self.root = TrieNode()
		self.ans = [0, 0, '']
		self.time = 0

	def insert(self, s):
		curr = self.root
		for ch in s:
			o = ord(ch) - ord('a')
			if curr.chars[o] is None:
				curr.chars[o] = TrieNode()
			curr = curr.chars[o]
		curr.isword = True
		curr.c += 1
		if curr.occ == -1:
			self.time += 1
			curr.occ = self.time
		if self.ans[0] < curr.c:
			self.ans = [curr.c, curr.occ, s]
		elif self.ans[0] == curr.c:
			if self.ans[1] < curr.occ:
				self.ans[1] = curr.occ
				self.ans[2] = s

class Solution:

	def mostFrequentWord(self, A, N):
		trie = Trie()
		for s in A:
			trie.insert(s)
		return trie.ans[2]


class Solution:

	def mostFrequentWord(self, arr, n):
		l = []
		d = {}
		for i in arr:
			if i in d.keys():
				d[i] += 1
			else:
				d[i] = 1
				l.append(i)
		l.reverse()
		t = 0
		r = ''
		for i in l:
			if d[i] > t:
				t = d[i]
				r = i
		return r


from collections import OrderedDict

class Solution:

	def mostFrequentWord(self, arr, n):
		d = OrderedDict()
		for i in arr:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		maxvalue = max(d, key=d.get)
		p = d[maxvalue]
		lst = []
		for i in d:
			if d[i] == p:
				lst.append(i)
		return lst[-1]


class Solution:

	def fi(self, arr, n, x):
		first = -1
		last = -1
		for i in range(0, n):
			if x != arr[i]:
				continue
			if first == -1:
				first = i
		last = i
		return first

	def mostFrequentWord(self, arr, n):
		dic = {}
		for i in arr:
			if i not in dic:
				dic[i] = 1
			else:
				dic[i] += 1
		maxx = max(dic.values())
		minn = min(dic.values())
		c = []
		if maxx == minn:
			for i in dic:
				if dic[i] == maxx:
					c.append(i)
				else:
					continue
		elif maxx != minn:
			for i in dic:
				if dic[i] == maxx:
					c.append(i)
		d = {}
		for i in c:
			d[i] = obj.fi(arr, n, i)
		y = max(d.values())
		for i in d:
			if d[i] == y:
				return i


class Trie:

	def __init__(self, char):
		self.char = char
		self.end = False
		self.count = 0
		self.children = {}

class Solution:

	def insert(root, txt):
		node = root
		for j in txt:
			if j in node.children:
				node = node.children[j]
			else:
				new_node = Trie(j)
				node.children[j] = new_node
				node = new_node
		node.end = True
		node.count += 1

	def dfs(node, prefix, out):
		if node.end:
			out.append((prefix + node.char, node.count))
		for c in node.children.values():
			Solution.dfs(c, prefix + node.char, out)

	def query(root, key):
		node = root
		for c in key:
			if c in node.children:
				node = node.children[c]
			else:
				return []
		out = []
		Solution.dfs(node, key[:-1], out)
		return sorted(out, key=lambda x: x[1], reverse=True)

	def mostFrequentWord(self, arr, n):
		root = Trie('')
		(max_, txt) = (0, '')
		for st in arr:
			Solution.insert(root, st)
		for st in set(arr):
			match = Solution.query(root, st)
			for j in range(len(match)):
				if match[j][1] >= max_:
					if txt == '':
						txt = match[j][0]
					elif match[j][1] == max_:
						if arr.index(txt) < arr.index(match[j][0]):
							txt = match[j][0]
					else:
						txt = match[j][0]
					max_ = match[j][1]
		return txt


from collections import OrderedDict

class Solution:

	def mostFrequentWord(self, arr, n):
		mp = {}
		resMax = 0
		res = ' '
		for i in range(n):
			if arr[i] not in mp:
				mp[arr[i]] = 1
				resMax = max(resMax, mp[arr[i]])
			else:
				mp[arr[i]] += 1
				resMax = max(resMax, mp[arr[i]])
		for i in range(n):
			if mp[arr[i]] == resMax:
				res = arr[i]
				mp[arr[i]] -= 1
		return res


class TrieNode:

	def __init__(self):
		self.child = [None] * 26
		self.endOf = False
		self.count = 0
		self.index = -1
		self.first = -1

class Solution:

	def insert(self, root, key, j):
		global maxCount
		global maxInd
		global maxFir
		for i in range(len(key)):
			ind = ord(key[i]) - ord('a')
			if root.child[ind] == None:
				root.child[ind] = TrieNode()
			root = root.child[ind]
		if root.count == 0:
			root.first = j
		root.count += 1
		if root.count > maxCount:
			maxCount = root.count
			maxInd = j
			maxFir = root.first
		elif root.count == maxCount:
			maxCount = root.count
			maxFir = max(maxFir, root.first)

	def mostFrequentWord(self, arr, n):
		root = TrieNode()
		global maxCount
		global maxInd
		global maxFir
		maxCount = 0
		maxInd = 0
		maxFir = 0
		for i in range(n):
			res = self.insert(root, arr[i], i)
		return arr[maxFir]


class Solution:

	def mostFrequentWord(self, arr, n):
		ref_dict = {}
		for i in range(n):
			if arr[i] not in ref_dict:
				ref_dict[arr[i]] = [1, i]
			else:
				ref_dict[arr[i]][0] += 1
		max_val = 0
		out = ''
		for x in ref_dict:
			if ref_dict[x][0] > max_val:
				max_val = ref_dict[x][0]
				out = x
			elif ref_dict[x][0] == max_val:
				if ref_dict[x][1] > ref_dict[out][1]:
					out = x
		return out


class Solution:

	def mostFrequentWord(self, arr, n):
		maxi = 0
		di = {}
		ans = ''
		for i in range(n):
			if arr[i] not in di.keys():
				di[arr[i]] = 1
				if di[arr[i]] > maxi:
					maxi = di[arr[i]]
			else:
				di[arr[i]] += 1
				if di[arr[i]] > maxi:
					maxi = di[arr[i]]
		for i in range(n):
			if di[arr[i]] == maxi:
				ans = arr[i]
				di[arr[i]] = di[arr[i]] - 1
		return ans


class Solution:

	def mostFrequentWord(self, arr, n):
		m = {}
		iq = {}
		ma = 0
		word = ''
		for i in range(n):
			if m.get(arr[i]):
				f = m[arr[i]]
				m[arr[i]] = f + 1
			else:
				m[arr[i]] = 1
			try:
				if iq[arr[i]]:
					pass
			except:
				iq[arr[i]] = i
		for i in m:
			if m[i] > ma:
				ma = m[i]
				word = i
			elif m[i] == ma:
				t1 = iq[i]
				t2 = iq[word]
				if t1 > t2:
					word = i
		return word


class Solution:

	def mostFrequentWord(self, arr, n):
		m = {}
		ma = 0
		maxi = []
		mindex = {}
		res = ''
		for i in range(len(arr)):
			if m.get(arr[i]):
				m[arr[i]] = m[arr[i]] + 1
			else:
				m[arr[i]] = 1
				mindex[arr[i]] = i
			if m[arr[i]] > ma:
				ma = m[arr[i]]
				maxi = []
				maxi.append(arr[i])
			elif m[arr[i]] == ma:
				maxi.append(arr[i])
		maimumIndex = -1
		for i in maxi:
			if mindex[i] > maimumIndex:
				maimumIndex = mindex[i]
				res = i
		return res


class Solution:

	def mostFrequentWord(self, arr, n):
		d = {}
		e = {}
		maxVal = arr[0]
		for i in range(len(arr)):
			if arr[i] not in d:
				d[arr[i]] = 1
				e[arr[i]] = i
			else:
				d[arr[i]] += 1
			if d[arr[i]] > d[maxVal]:
				maxVal = arr[i]
			elif d[arr[i]] == d[maxVal] and e[arr[i]] > e[maxVal]:
				maxVal = arr[i]
		return maxVal


class Solution:

	def mostFrequentWord(self, arr, n):
		mcx = 0
		res = ''
		c = {}
		for i in arr:
			c.setdefault(i, 0)
			c[i] += 1
			mcx = max(mcx, c[i])
		for i in range(n):
			if mcx == c[arr[i]]:
				c[arr[i]] -= 1
				res = arr[i]
		return res


class Solution:

	def mostFrequentWord(self, arr, n):
		s = {}
		for i in range(n):
			if arr[i] in s:
				s[arr[i]][0] += 1
			else:
				s[arr[i]] = [1, i]
		d = -1
		for i in arr:
			if s[i][0] == d and s[i][1] > s[g][1]:
				g = i
			if s[i][0] > d:
				d = s[i][0]
				g = i
		return g


from collections import OrderedDict

class Solution:

	def mostFrequentWord(self, arr, n):
		dict = OrderedDict()
		for i in arr:
			if i in dict.keys():
				dict[i] += 1
			else:
				dict[i] = 1
		mx = 0
		st = ''
		for i in dict.keys():
			if dict[i] >= mx:
				mx = dict[i]
				st = i
		return st


from collections import defaultdict

class Solution:

	def mostFrequentWord(self, A, n):
		D = defaultdict(lambda : [-1, 0])
		ans = [0, 0]
		for (i, s) in enumerate(A):
			pr = D[s]
			pr[1] += 1
			if pr[0] == -1:
				pr[0] = i
			if pr[1] > ans[1] or (pr[1] == ans[1] and pr[0] > ans[0]):
				ans = pr
		return A[ans[0]]


class Solution:

	def mostFrequentWord(self, arr, n):
		m = dict()
		m1 = dict()
		max = 0
		result = ''
		k = 1
		for i in range(0, n):
			if arr[i] in m1.keys():
				continue
			m1[arr[i]] = k
			k += 1
		for i in range(0, n):
			if arr[i] in m.keys():
				m[arr[i]] += 1
			else:
				m[arr[i]] = 1
			if max <= m[arr[i]]:
				if max < m[arr[i]]:
					max = m[arr[i]]
					result = arr[i]
				elif m1[result] < m1[arr[i]]:
					max = m[arr[i]]
					result = arr[i]
		return result
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		arr = [x for x in input().strip().split()]
		obj = Solution()
		print(obj.mostFrequentWord(arr, n))


class Solution:

	def mostFrequentWord(self, arr, n):
		d = {}
		for i in arr:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		count = 0
		for i in d:
			if d[i] > count:
				count = d[i]
		e = []
		for i in arr:
			if d[i] == count:
				e.append(i)
		if len(e) == 1:
			return e[0]
		f = {}
		for i in range(len(arr)):
			a = arr[i]
			if a not in f:
				f[a] = [i]
			else:
				f[a].append(i)
		new = []
		for i in e:
			b = f[i]
			new.append(b[0])
		g = max(new)
		for i in e:
			c = f[i]
			if c[0] == g:
				return i
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		arr = [x for x in input().strip().split()]
		obj = Solution()
		print(obj.mostFrequentWord(arr, n))


class Solution:

	def mostFrequentWord(self, arr, n):
		d1 = {}
		for i in range(len(arr)):
			if arr[i] not in d1:
				d1[arr[i]] = [1, i]
			else:
				d1[arr[i]][0] += 1
		(key, value, ind) = (-1, 0, -1)
		for i in range(len(arr)):
			if d1[arr[i]][0] >= value and d1[arr[i]][1] > ind:
				key = arr[i]
				value = d1[arr[i]][0]
				ind = d1[arr[i]][1]
		return key
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		arr = [x for x in input().strip().split()]
		obj = Solution()
		print(obj.mostFrequentWord(arr, n))


from collections import Counter

class Solution:

	def mostFrequentWord(self, arr, n):
		keys = []
		for i in range(n):
			if arr[i] not in keys:
				keys.append(arr[i])
		a = Counter(arr)
		keys.reverse()
		keys.sort(key=lambda x: a[x], reverse=True)
		return keys[0]
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		arr = [x for x in input().strip().split()]
		obj = Solution()
		print(obj.mostFrequentWord(arr, n))


from collections import defaultdict

class Solution:

	def mostFrequentWord(self, arr, n):
		first = {}
		res = [None, 0]
		freq = defaultdict(int)
		for (i, word) in enumerate(arr):
			first[word] = min(i, first.get(word, n))
			hv = hash(word)
			freq[hv] += 1
			if freq[hv] > res[1]:
				res = [word, freq[hv]]
			elif freq[hv] == res[1] and first[word] > first[res[0]]:
				res[0] = word
		return res[0]
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		arr = [x for x in input().strip().split()]
		obj = Solution()
		print(obj.mostFrequentWord(arr, n))


class Solution:

	def mostFrequentWord(self, arr, n):
		d = {}
		for i in range(n):
			if arr[i] in d:
				d[arr[i]][1] += 1
			else:
				d[arr[i]] = [i, 1]
		ans = ''
		ind = 0
		cnt = 0
		for i in d:
			if d[i][1] > cnt:
				ans = i
				cnt = d[i][1]
				ind = d[i][0]
			elif d[i][1] == cnt:
				if d[i][0] > ind:
					ans = i
					cnt = d[i][1]
					ind = d[i][0]
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		arr = [x for x in input().strip().split()]
		obj = Solution()
		print(obj.mostFrequentWord(arr, n))