Given an array A. Let X be an element in the array which has the maximum frequency. The task is to find the smallest sub segment of the array which also has X as the maximum frequency element.
Note: if two or more elements have the same frequency (i.e., maximum frequency) and the same sub segment size then print the sub segment which occurs first in the array.
 
Example 1:
 
Input : A[] = {1, 2, 2, 3, 1}
Output : 2 2
Explanation:
Note that there are two elements that appear two times,
1 and 2.The smallest window for 1 is whole array and
smallest window for 2 is {2, 2}.
Since window for 2 is smaller, this is our output.
Example 2:
Input : A[] = {1, 4, 3, 3, 5, 5} 
Output : 3 3 
 
Your Task:
This is a function problem. The input is already taken care of by the driver code. You only need to complete the function smallestSubsegment() that takes an array (arr), sizeOfArray (n), and return the required sub-segment of the array. The driver code takes care of the printing.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(N).
 
 
Constraints:
1 ≤ N ≤ 10^{5}
1 ≤ A[i] ≤ 10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Data structures

Starter code: #User function Template for python3

class Solution:
    def smallestSubsegment (self, arr,  n) : 
        #Complete the function


Solutions:
class Solution:

	def smallestSubsegment(self, arr, n):
		left = dict()
		count = dict()
		mx = 0
		mn = 0
		startindex = 0
		for i in range(n):
			ele = arr[i]
			if ele not in count.keys():
				left[ele] = i
				count[ele] = 1
			else:
				count[ele] += 1
			if count[ele] > mx:
				mx = count[ele]
				mn = i - left[ele] + 1
				startindex = left[ele]
			elif count[ele] == mx and i - left[ele] + 1 < mn:
				mn = i - left[ele] + 1
				startindex = left[ele]
		return arr[startindex:startindex + mn]


class Solution:

	def smallestSubsegment(self, a, n):
		left = dict()
		count = dict()
		mx = 0
		(mn, strindex) = (0, 0)
		for i in range(n):
			x = a[i]
			if x not in count.keys():
				left[x] = i
				count[x] = 1
			else:
				count[x] += 1
			if count[x] > mx:
				mx = count[x]
				mn = i - left[x] + 1
				strindex = left[x]
			elif count[x] == mx and i - left[x] + 1 < mn:
				mn = i - left[x] + 1
				strindex = left[x]
		return a[strindex:strindex + mn]


class Solution:

	def smallestSubsegment(self, arr, n):
		d = {}
		for i in range(n):
			if arr[i] in d:
				d[arr[i]].append(i)
			else:
				d[arr[i]] = [i]
		l = [len(d[i]) for i in d]
		a = max(l)
		t = []
		for i in d:
			if len(d[i]) == a:
				t.append(d[i])
		w = []
		for i in t:
			q = i[-1] - i[0]
			w.append([q, i])
		w.sort()
		p = w[0][1][0]
		r = w[0][1][-1]
		return arr[p:r + 1]


class Solution:

	def smallestSubsegment(self, arr, n):
		freq = {}
		startmap = {}
		highfreq = 0
		startindex = 0
		endindex = 0
		length = endindex - startindex + 1
		for i in range(n):
			if arr[i] in freq:
				freq[arr[i]] += 1
			else:
				freq[arr[i]] = 1
				startmap[arr[i]] = i
			if freq[arr[i]] > highfreq:
				highfreq = freq[arr[i]]
				startindex = startmap[arr[i]]
				endindex = i
				length = endindex - startindex + 1
			elif freq[arr[i]] == highfreq:
				clen = i - startmap[arr[i]] + 1
				if clen < length:
					highfreq = freq[arr[i]]
					startindex = startmap[arr[i]]
					endindex = i
					length = endindex - startindex + 1
		res = []
		for i in range(startindex, endindex + 1):
			res.append(arr[i])
		return res


class Solution:

	def smallestSubsegment(self, arr, n):
		dc = {}
		d = {}
		for i in range(n):
			if arr[i] in d:
				dc[arr[i]] += 1
				d[arr[i]][1] = i
			else:
				dc[arr[i]] = 1
				d[arr[i]] = [i, i]
		d1 = {}
		for x in d:
			d1[x] = d[x][1] - d[x][0] + 1
		m = max(dc.values())
		ls = []
		for x in dc:
			if dc[x] == m:
				ls.append(x)
		if len(ls) == 1:
			return arr[d[ls[0]][0]:d[ls[0]][1] + 1]
		else:
			mx = len(arr)
			ls1 = []
			for x in ls:
				mx = min(d1[x], mx)
			for x in d1:
				if d1[x] == mx and x in ls:
					ls1.append(x)
			if len(ls1) == 1:
				return arr[d[ls1[0]][0]:d[ls1[0]][1] + 1]
			else:
				mxc = len(arr) - 1
				for x in ls1:
					if mxc >= d[x][0]:
						mxc = d[x][0]
						vv = x
				return arr[d[vv][0]:d[vv][1] + 1]


class Solution:

	def smallestSubsegment(self, arr, n):
		si = -1
		li = -1
		map1 = {}
		map2 = {}
		mfreq = 0
		for i in range(len(arr)):
			map1[arr[i]] = map1.get(arr[i], 0) + 1
			if arr[i] not in map2:
				map2[arr[i]] = i
			if map1[arr[i]] > mfreq:
				mfreq = map1[arr[i]]
				si = map2[arr[i]]
				li = i
			elif map1[arr[i]] == mfreq:
				if i - map2[arr[i]] < li - si:
					si = map2[arr[i]]
					li = i
		res = []
		for i in range(si, li + 1):
			res.append(arr[i])
		return res


class Solution:

	def smallestSubsegment(self, arr, n):
		mydict = {}
		count = {}
		maximum_freq = 0
		(start, end) = (0, 0)
		for i in range(n):
			x = arr[i]
			if x not in mydict:
				mydict[x] = i
				count[x] = 1
			else:
				count[x] += 1
			if count[x] > maximum_freq:
				maximum_freq = count[x]
				end = i - mydict[x] + 1
				start = mydict[x]
			elif count[x] == maximum_freq and end > i - mydict[x] + 1:
				end = i - mydict[x] + 1
				start = mydict[x]
		return arr[start:start + end]


class Solution:

	def smallestSubsegment(self, arr, n):
		d = {}
		for i in range(n):
			a = arr[i]
			if a not in d:
				d[a] = [i]
			else:
				d[a].append(i)
		count = 0
		d1 = {}
		for i in arr:
			if i not in d1:
				d1[i] = 1
			else:
				d1[i] += 1
		for i in d1:
			count = max(d1[i], count)
		x = []
		for i in d1:
			if d1[i] == count:
				x.append(i)
		ans = []
		for i in arr:
			if i in x:
				b = d[i]
				c = arr[b[0]:b[-1] + 1]
				ans.append(c)
		l = 99999
		for i in ans:
			l = min(len(i), l)
		z = []
		for i in ans:
			if len(i) == l:
				z.append(i)
		for i in arr:
			for j in z:
				if j[0] == i:
					return j


class Solution:

	def smallestSubsegment(self, arr, n):
		count = {}
		start_index = {}
		max_freq = 0
		min_dist = 0
		start = 0
		end = 0
		for i in range(n):
			if arr[i] not in start_index:
				start_index[arr[i]] = i
			if arr[i] not in count:
				count[arr[i]] = 1
			else:
				count[arr[i]] += 1
			if count[arr[i]] > max_freq:
				max_freq = count[arr[i]]
				min_dist = i - start_index[arr[i]] + 1
				start = start_index[arr[i]]
				end = i
			elif count[arr[i]] == max_freq:
				if i - start_index[arr[i]] + 1 < min_dist:
					min_dist = i - start_index[arr[i]] + 1
					start = start_index[arr[i]]
					end = i
		return arr[start:end + 1]


class Solution:

	def smallestSubsegment(self, arr, n):
		(fmap, smap) = ({}, {})
		(hf, si, ei) = (0, 0, 0)
		ln = 0
		for i in range(n):
			if arr[i] in fmap.keys():
				fmap[arr[i]] += 1
			else:
				fmap[arr[i]] = 1
				smap[arr[i]] = i
			if fmap[arr[i]] > hf:
				hf = fmap[arr[i]]
				si = smap[arr[i]]
				ei = i
				ln = ei - si + 1
			elif fmap[arr[i]] == hf:
				templn = i - smap[arr[i]] + 1
				if templn < ln:
					ln = templn
					hf = fmap[arr[i]]
					si = smap[arr[i]]
					ei = i
					ln = ei - si + 1
		return arr[si:ei + 1]


class Solution:

	def smallestSubsegment(self, arr, n):
		counter = {}
		minlen = float('inf')
		mincouple = (0, 0)
		maxfreq = 1
		for (i, a) in enumerate(arr):
			if a in counter:
				dist = i - counter[a][0]
				if maxfreq < len(counter[a]) + 1 or (dist < minlen and maxfreq == len(counter[a]) + 1):
					minlen = dist
					mincouple = (counter[a][0], i)
					maxfreq = len(counter[a]) + 1
			else:
				counter[a] = []
			counter[a].append(i)
		if mincouple:
			return arr[mincouple[0]:mincouple[1] + 1]
		return -1
for _ in range(0, int(input())):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	ob = Solution()
	res = ob.smallestSubsegment(arr, n)
	print(*res)


class Solution:

	def smallestSubsegment(self, arr, n):
		dct = {}
		idx = 0
		ed = 0
		mx = 1
		mn = n
		prv_mn = n - 1
		lc = n
		for i in arr:
			if i in dct.keys():
				dct[i][2] = dct[i][2] + 1
				dct[i][1] = idx
				dct[i][3] = idx - dct[i][0] + 1
			else:
				dct[i] = [idx, idx, 1, 0]
			if dct[i][2] >= mx:
				pre_mx = mx
				mx = dct[i][2]
			idx = idx + 1
		for i in dct.keys():
			if (dct[i][2] == mx) & (dct[i][3] < mn):
				mn = dct[i][3]
		for i in dct.keys():
			if (dct[i][2] == mx) & (dct[i][3] == mn):
				if dct[i][1] < lc:
					lc = dct[i][1]
					rel = i
		rslt = arr[dct[rel][0]:dct[rel][1] + 1]
		return rslt


class Solution:

	def smallestSubsegment(self, arr, n):
		fr = {}
		si = {}
		hf = 0
		s = 0
		e = 0
		ln = 0
		for i in range(n):
			if arr[i] not in fr:
				si[arr[i]] = i
				fr[arr[i]] = 1
			else:
				fr[arr[i]] += 1
			if fr[arr[i]] > hf:
				s = si[arr[i]]
				e = i
				hf = fr[arr[i]]
				ln = e - s + 1
			elif fr[arr[i]] == hf:
				chln = i - si[arr[i]] + 1
				if chln < ln:
					s = si[arr[i]]
					e = i
					ln = chln
		return arr[s:e + 1]


from collections import Counter

class Solution:

	def smallestSubsegment(self, arr, n):
		C = Counter(arr)
		maxOccurrence = max(C.values())
		d = {}
		for (num, count) in C.items():
			if count == maxOccurrence:
				d[num] = -1
		for i in range(len(arr)):
			if arr[i] in d:
				if d[arr[i]] == -1:
					d[arr[i]] = [i, 0]
				else:
					d[arr[i]][1] = i
		minDist = float('inf')
		ans = 0
		for (num, dist) in d.items():
			if dist[1] - dist[0] < minDist:
				minDist = dist[1] - dist[0]
				ans = dist
		if minDist <= 0:
			return [arr[0]]
		a = ans[0]
		b = ans[1]
		return arr[a:b + 1]


class Solution:

	def smallestSubsegment(self, arr, n):
		left = {}
		count = {}
		mx = 0
		(mn, startindex) = (0, 0)
		for i in range(n):
			x = arr[i]
			if x not in count:
				left[x] = i
				count[x] = 1
			else:
				count[x] += 1
			if count[x] > mx:
				mx = count[x]
				mn = i - left[x] + 1
				startindex = left[x]
			elif count[x] == mx and i - left[x] + 1 < mn:
				mn = i - left[x] + 1
				startindex = left[x]
		ans = []
		for i in range(startindex, startindex + mn):
			ans.append(arr[i])
		return ans


from collections import defaultdict

class Solution:

	def smallestSubsegment(self, arr, n):
		fmap = {}
		i_map = {}
		hfreq = 0
		reslen = 1
		for i in range(n):
			if arr[i] not in fmap:
				fmap[arr[i]] = 1
				i_map[arr[i]] = i
			else:
				fmap[arr[i]] += 1
			if fmap[arr[i]] > hfreq:
				hfreq = fmap[arr[i]]
				si = i_map[arr[i]]
				ei = i
				reslen = ei - si + 1
			elif fmap[arr[i]] == hfreq:
				clen = i - i_map[arr[i]] + 1
				if clen < reslen:
					hfreq = fmap[arr[i]]
					si = i_map[arr[i]]
					ei = i
					reslen = ei - si + 1
		res = arr[si:ei + 1]
		return res


class Solution:

	def smallestSubsegment(self, arr, n):
		freqs = {}
		idxes = {}
		minDist = 0
		maxFreq = 0
		start = 0
		end = 0
		for i in range(n):
			if arr[i] not in idxes:
				idxes[arr[i]] = i
			if arr[i] not in freqs:
				freqs[arr[i]] = 1
			else:
				freqs[arr[i]] += 1
			if freqs[arr[i]] >= maxFreq:
				if freqs[arr[i]] > maxFreq:
					maxFreq = freqs[arr[i]]
					minDist = i - idxes[arr[i]] + 1
					start = idxes[arr[i]]
					end = i
				elif freqs[arr[i]] == maxFreq:
					if i - idxes[arr[i]] + 1 < minDist:
						minDist = i - idxes[arr[i]] + 1
						start = idxes[arr[i]]
						end = i
		res = []
		for i in range(start, end + 1):
			res.append(arr[i])
		return res


class Solution:

	def smallestSubsegment(self, arr, n):
		left = {}
		count = {}
		ln = 0
		strt = 0
		mx = 0
		for i in range(n):
			x = arr[i]
			if x not in left:
				left[x] = i
				count[x] = 1
			else:
				count[x] += 1
			if count[x] > mx:
				mx = count[x]
				ln = i - left[x] + 1
				strt = left[x]
			elif count[x] == mx and i - left[x] + 1 < ln:
				ln = i - left[x] + 1
				strt = left[x]
		li = []
		for i in range(strt, strt + ln):
			li.append(arr[i])
		return li


from collections import defaultdict

class Solution:

	def smallestSubsegment(self, arr, n):
		d = defaultdict(lambda : 0)
		for i in arr:
			d[i] += 1
		l = []
		m = 10 ** 9
		for i in range(n + 1):
			l.append([])
		for i in d:
			l[d[i]].append(i)
		x = []
		for i in range(n - 1, -1, -1):
			if len(l[i]) != 0:
				x = l[i]
				break
		t1 = 0
		t2 = 0
		t3 = 0
		for i in x:
			for j in range(n - 1, -1, -1):
				if i == arr[j]:
					break
			t = arr.index(i)
			if m > j - t:
				m = j - t
				t1 = j
				t2 = t
			elif m == j - t:
				if t < t2:
					t1 = j
					t2 = t
		ll = arr[t2:t1 + 1]
		return ll


import collections

class Solution:

	def smallestSubsegment(self, arr, n):
		hashMap = {}
		for (i, el) in enumerate(arr):
			if el not in hashMap:
				hashMap[el] = [0] * 3
				hashMap[el][0] = i
				hashMap[el][1] = i
				hashMap[el][2] = 1
			else:
				hashMap[el][1] = i
				hashMap[el][2] += 1
		hashMap = sorted(hashMap.values(), key=lambda y: (-y[2], y[1] - y[0], y[0]))
		(start, end, freq) = hashMap[0]
		return arr[start:end + 1]


class Solution:

	def smallestSubsegment(self, arr, n):
		dic = {}
		for i in arr:
			dic[i] = dic.get(i, 0) + 1
		li = dic.values()
		mx = max(li)
		target = []
		for i in dic:
			if dic[i] == mx:
				target.append(i)
		arr2 = arr[::-1]
		ans = []
		for i in target:
			ind1 = arr.index(i)
			ind2 = n - arr2.index(i) - 1
			ans.append((ind2 - ind1 + 1, ind1, arr[ind1:ind2 + 1]))
		mn = float('inf')
		for (i, j, k) in ans:
			mn = min(i, mn)
		mn_with_ind = float('inf')
		pot = []
		for (i, j, k) in ans:
			if i == mn:
				if mn_with_ind > j:
					mn_with_ind = j
					pot = k
		return pot


class Solution:

	def smallestSubsegment(self, arr, n):
		count = {}
		for (i, ele) in enumerate(arr):
			if ele not in count:
				count[ele] = [i, i, 1]
			else:
				count[ele][1] = i
				count[ele][2] += 1
		ans = 1
		l = 0
		r = 0
		for (k, v) in count.items():
			(start, end, freq) = v
			if freq >= ans:
				if freq > ans or (freq == ans and end - start < r - l) or (freq == ans and end - start == r - l and (start < l)):
					ans = freq
					l = start
					r = end
		return arr[l:r + 1]


class Solution:

	def smallestSubsegment(self, arr, n):
		left = {}
		freq = {}
		ans = []
		(mx, lenn, val) = (0, 0, 0)
		for (i, ele) in enumerate(arr):
			if ele not in freq:
				left[ele] = i
				freq[ele] = 1
			else:
				freq[ele] += 1
			if freq[ele] > mx:
				mx = freq[ele]
				lenn = i - left[ele] + 1
				val = left[ele]
			elif freq[ele] == mx and i - left[ele] + 1 < lenn:
				val = left[ele]
				lenn = i - left[ele] + 1
		for i in range(val, val + lenn):
			ans.append(arr[i])
		return ans


class Solution:

	def smallestSubsegment(self, arr, n):
		ans = []
		left = dict()
		count = dict()
		(mx, idx) = (0, 0)
		mxlen = 0
		for (i, ele) in enumerate(arr):
			if ele not in count:
				left[ele] = i
				count[ele] = 1
			else:
				count[ele] += 1
			if count[ele] > mx:
				mx = count[ele]
				lenn = i - left[ele] + 1
				idx = left[ele]
			elif count[ele] == mx and i - left[ele] + 1 < lenn:
				lenn = i - left[ele] + 1
				idx = left[ele]
		for i in range(idx, idx + lenn):
			ans.append(arr[i])
		return ans


class Solution:

	def smallestSubsegment(self, arr, n):
		fmap = {}
		i_map = {}
		res_len = 1
		hfreq = 0
		for i in range(n):
			if arr[i] not in fmap:
				fmap[arr[i]] = 1
				i_map[arr[i]] = i
			else:
				fmap[arr[i]] += 1
			if fmap[arr[i]] > hfreq:
				hfreq = fmap[arr[i]]
				si = i_map[arr[i]]
				ei = i
				res_len = ei - si + 1
			elif fmap[arr[i]] == hfreq:
				clen = i - i_map[arr[i]] + 1
				if clen < res_len:
					hfreq = fmap[arr[i]]
					si = i_map[arr[i]]
					ei = i
					res_len = ei - si + 1
		res = []
		for i in range(si, ei + 1):
			res.append(arr[i])
		return res


class Solution:

	def smallestSubsegment(self, arr, n):
		fmap = {}
		stmap = {}
		hf = 0
		s = -1
		e = -1
		l = 10 ** 9
		for i in range(n):
			if arr[i] not in stmap:
				stmap[arr[i]] = i
			fmap[arr[i]] = fmap.get(arr[i], 0) + 1
			if fmap[arr[i]] > hf:
				hf = fmap[arr[i]]
				s = stmap[arr[i]]
				e = i
				l = e - s + 1
			elif fmap[arr[i]] == hf:
				if i - stmap[arr[i]] + 1 < l:
					l = i - stmap[arr[i]] + 1
					s = stmap[arr[i]]
					e = i
		return arr[s:e + 1]


class Solution:

	def smallestSubsegment(self, arr, n):
		d = {}
		for i in range(len(arr)):
			if arr[i] not in d:
				d[arr[i]] = [i, i, 1]
			else:
				d[arr[i]][1] = i
				d[arr[i]][2] += 1
		l = d[arr[0]][0]
		r = d[arr[0]][1]
		m = d[arr[0]][2]
		for i in d.keys():
			if d[i][2] > m:
				l = d[i][0]
				r = d[i][1]
				m = d[i][2]
			if d[i][2] == m:
				if r - l > d[i][1] - d[i][0]:
					r = d[i][1]
					l = d[i][0]
				if r - l == d[i][1] - d[i][0]:
					if l > d[i][0]:
						l = d[i][0]
						r = d[i][1]
		return arr[l:r + 1]


class Solution:

	def smallestSubsegment(self, arr, n):
		map1 = {}
		map2 = {}
		m = 0
		l = 0
		last = -1
		for i in range(n):
			if arr[i] not in map1:
				map1[arr[i]] = 1
				map2[arr[i]] = i
			else:
				map1[arr[i]] += 1
			if map1[arr[i]] > m:
				m = map1[arr[i]]
				v = arr[i]
				last = i
				l = i - map2[arr[i]]
			elif map1[arr[i]] == m and i - map2[arr[i]] < l:
				v = arr[i]
				l = i - map2[arr[i]]
				last = i
		ans = []
		for i in range(map2[v], last + 1):
			ans.append(arr[i])
		return ans


class Solution:

	def smallestSubsegment(self, arr, n):
		fmap = {}
		smap = {}
		hfreq = 0
		si = 0
		ei = 0
		len1 = ei - si + 1
		for i in range(n):
			if arr[i] in fmap:
				fmap[arr[i]] += 1
			else:
				fmap[arr[i]] = 1
				smap[arr[i]] = i
			if fmap[arr[i]] > hfreq:
				hfreq = fmap[arr[i]]
				si = smap[arr[i]]
				ei = i
				len1 = ei - si + 1
			elif fmap[arr[i]] == hfreq:
				clen = i - smap[arr[i]] + 1
				if clen < len1:
					hfreq = fmap[arr[i]]
					si = smap[arr[i]]
					ei = i
					len1 = ei - si + 1
		res = []
		for i in range(si, ei + 1):
			res.append(arr[i])
		return res