Given an array arr of N integers that might contain duplicates, find the element whose last appearance is earliest.
 
Example 1:
Input : arr[] = {10, 30, 20, 10, 20}
Output : 30
Explanation:
Below are indexes of last
appearances of all elements (0 based
indexes). 10 last occurs at index 3
30 last occurs at index 1. 20 last
occurs at index 4 The element whose
last appearance earliest is 30.
 
Example 2:
Input : arr[] = {10, 20, 30, 40, 10}
Output : 20
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 lastSeenElement() that takes an array (arr), sizeOfArray (n), and returns the element whose last appearance is earliest. The driver code takes care of the printing.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(N).
Constraints:
1<=N<=10^{5}
1<=arr[i]<=10^{6}

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Data structures

Starter code: #User function Template for python3



class Solution:

      

    def firstNonRepeating(self, arr, n): 

          

        # Complete the function



Solutions:
class Solution:

	def firstNonRepeating(self, arr, n):
		dic = {}
		for i in range(n):
			if arr[i] not in dic:
				dic[arr[i]] = i
			else:
				dic[arr[i]] = i
		lis = []
		for i in dic:
			lis.append(dic[i])
		k = min(lis)
		return arr[k]


class Solution:

	def firstNonRepeating(self, arr, n):
		dic = {}
		for i in range(n):
			if arr[i] not in dic:
				dic[arr[i]] = i
			else:
				dic[arr[i]] = i
		mi = n
		mii = 0
		for i in dic:
			if mi > dic[i]:
				mi = dic[i]
				mii = i
		return mii


class Solution:

	def firstNonRepeating(self, arr, n):
		a = {}
		for i in range(n):
			a[arr[i]] = i
		mn = min(a.values())
		for i in arr:
			if a[i] == mn:
				return i


class Solution:

	def firstNonRepeating(self, arr, n):
		d = {}
		for i in range(n):
			if arr[i] in d:
				d[arr[i]].append(i)
			else:
				d[arr[i]] = [i]
		j = n
		for i in d:
			if d[i][-1] < j:
				j = d[i][-1]
		return arr[j]


class Solution:

	def firstNonRepeating(self, arr, n):
		dict = {}
		small = 1000000
		for i in range(n):
			dict[arr[i]] = i
		for i in range(n):
			if dict.get(arr[i]) < small:
				small = dict.get(arr[i])
		return arr[small]


class Solution:

	def firstNonRepeating(self, arr, n):
		d = {}
		for i in range(n):
			d[arr[i]] = i
		lastseen = min(d.values())
		for i in arr:
			if d[i] == lastseen:
				return i


class Solution:

	def firstNonRepeating(self, arr, n):
		d = dict()
		for i in range(n):
			d[arr[i]] = i
		minv = min(d.values())
		for i in arr:
			if d[i] == minv:
				return i


class Solution:

	def firstNonRepeating(self, arr, n):
		d = {}
		for i in range(n):
			if arr[i] not in d:
				d[arr[i]] = [i]
			else:
				d[arr[i]].append(i)
		l = []
		for i in d:
			l.append(d[i][-1])
		l.sort()
		a = l[0]
		return arr[a]


class Solution:

	def firstNonRepeating(self, arr, n):
		d = {}
		for i in range(n):
			d[arr[i]] = i
		return sorted(d.items(), key=lambda x: x[1])[0][0]


import sys

class Solution:

	def firstNonRepeating(self, arr, n):
		hash = {}
		for i in range(n):
			hash[arr[i]] = i
		res_ind = sys.maxsize
		res = 0
		for (x, y) in hash.items():
			if y < res_ind:
				res_ind = y
				res = x
		return res


class Solution:

	def firstNonRepeating(self, arr, n):
		hm = {}
		for i in range(n):
			hm[arr[i]] = i
		min1 = min(hm.values())
		for i in arr:
			if hm[i] == min1:
				return i


class Solution:

	def firstNonRepeating(self, arr: list, n: int) -> int:
		_dict = {}
		for i in range(n):
			_dict[arr[i]] = i
		index = float('inf')
		target = None
		for (key, value) in _dict.items():
			if value < index:
				target = key
				index = value
		return target


class Solution:

	def firstNonRepeating(self, arr, n):
		s = set(arr)
		m = len(s)
		l = set()
		c = 0
		for i in range(n - 1, -1, -1):
			if arr[i] in l:
				continue
			else:
				l.add(arr[i])
				c += 1
				if c == m:
					return arr[i]


class Solution:

	def firstNonRepeating(self, arr, n):
		d = {}
		for i in range(n):
			d[arr[i]] = i
		last = 9999999999999999
		ans = arr[0]
		for i in d:
			if d[i] < last:
				ans = i
				last = d[i]
		return ans


class Solution:

	def firstNonRepeating(self, arr, n):
		d = {}
		for i in range(n - 1, -1, -1):
			if arr[i] not in d:
				d[arr[i]] = i
		mi = min(d.values())
		for i in d:
			if d[i] == mi:
				return i


class Solution:

	def firstNonRepeating(self, arr, n):
		d = {}
		for i in range(n):
			d[arr[i]] = i
		m = []
		for (x, y) in d.items():
			m.append(y)
		e = min(m)
		for (x, y) in d.items():
			if y == e:
				return x


class Solution:

	def firstNonRepeating(self, arr, n):
		m = {}
		for i in range(n):
			m[arr[i]] = i
		d = 99999999999
		for i in m:
			if m[i] < d:
				d = m[i]
				h = i
		return h


class Solution:

	def firstNonRepeating(self, arr, n):
		d = dict()
		for i in range(n):
			d[arr[i]] = i
		res = 10000000
		for i in d.values():
			res = min(res, i)
		return arr[res]


class Solution:

	def firstNonRepeating(self, arr, n):
		d = dict()
		for i in range(n):
			d[arr[i]] = i
		res = 10000000
		for i in d.values():
			res = min(res, i)
		return arr[res]
from collections import defaultdict
for _ in range(0, int(input())):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	ob = Solution()
	print(ob.firstNonRepeating(arr, n))


class Solution:

	def firstNonRepeating(self, arr, n):
		d = dict()
		for i in range(n):
			d[arr[i]] = i
		mini = 1000
		for (k, v) in d.items():
			if v < mini:
				mini = v
				ans = k
		return ans
from collections import defaultdict
for _ in range(0, int(input())):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	ob = Solution()
	print(ob.firstNonRepeating(arr, n))


class Solution:

	def firstNonRepeating(self, arr, n):
		d = {}
		for i in range(n):
			d[arr[i]] = i
		k = min(d.values())
		for (i, j) in d.items():
			if j == k:
				return i
from collections import defaultdict
for _ in range(0, int(input())):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	ob = Solution()
	print(ob.firstNonRepeating(arr, n))


class Solution:

	def firstNonRepeating(self, arr, n):
		d = {}
		for i in range(n):
			d[arr[i]] = i
		a = []
		for (x, y) in d.items():
			a.append(y)
		min_val = min(a)
		for (x, y) in d.items():
			if y == min_val:
				return x
from collections import defaultdict
for _ in range(0, int(input())):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	ob = Solution()
	print(ob.firstNonRepeating(arr, n))


class Solution:

	def firstNonRepeating(self, arr, n):
		lst = [0] * max(len(arr) + 1, max(arr) + 1)
		c = max(arr) + 1
		d = 0
		for i in range(len(arr)):
			lst[arr[i]] = i + 1
		for j in range(len(arr)):
			if lst[arr[j]] >= 1:
				c = min(lst[arr[j]], c)
		return lst.index(c)
from collections import defaultdict
for _ in range(0, int(input())):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	ob = Solution()
	print(ob.firstNonRepeating(arr, n))


class Solution:

	def firstNonRepeating(self, arr, n):
		d = {}
		for i in range(n):
			a = arr[i]
			if a in d:
				d[a] = i
			else:
				d[a] = i
		ans = 0
		index = n
		for i in d:
			if d[i] < index:
				ans = i
				index = d[i]
		return ans


class Solution:

	def firstNonRepeating(self, a, n):
		d = {}
		for i in range(n):
			d[a[i]] = i
		return a[min(d.values())]


from collections import defaultdict

class Solution:

	def firstNonRepeating(self, arr, n):
		d = defaultdict(int)
		for i in range(n):
			d[arr[i]] = i
		ele = 0
		index = n
		for (i, j) in d.items():
			if j < index:
				index = j
				ele = i
		return ele


class Solution:

	def firstNonRepeating(self, arr, n):
		hash = {}
		for i in range(0, n):
			hash[arr[i]] = i
		min_idx_value = 1097666
		for (key, value) in hash.items():
			if value < min_idx_value:
				min_idx_value = value
		return arr[min_idx_value]


class Solution:

	def firstNonRepeating(self, arr, n):
		k = {}
		for i in range(n):
			k[arr[i]] = i
		ind = []
		for x in k.values():
			ind.append(x)
		m = min(ind)
		for x in k.keys():
			if k[x] == m:
				return x


class Solution:

	def firstNonRepeating(self, arr, n):
		hash_map = {}
		for i in range(n):
			hash_map[arr[i]] = i
		index = n
		element = -1
		for i in hash_map:
			if hash_map[i] < index:
				element = i
				index = hash_map[i]
		return element


class Solution:

	def firstNonRepeating(self, arr, n):
		gg = {}
		for i in range(n):
			gg[arr[i]] = i
		ans = float('inf')
		for i in gg:
			if gg[i] < ans:
				ans = gg[i]
		return arr[ans]


class Solution:

	def firstNonRepeating(self, arr, n):
		_dict = {}
		for i in range(n):
			_dict[arr[i]] = i
		_dict = sorted(_dict.items(), key=lambda kv: kv[1])
		return _dict[0][0]


class Solution:

	def firstNonRepeating(self, arr, n):
		mp = {}
		c = 0
		for i in range(n):
			c += 1
			if arr[i] not in mp:
				mp[arr[i]] = c
			mp[arr[i]] = c
		x1 = 1000000000
		res = -1
		for x in mp:
			if mp[x] < x1:
				x1 = mp[x]
				res = x
		return res


class Solution:

	def firstNonRepeating(self, arr, n):
		hashmap = {}
		for i in arr:
			if i in hashmap:
				hashmap[i] = hashmap[i] + 1
			else:
				hashmap[i] = 1
		for i in arr:
			if i in hashmap:
				if hashmap[i] == 1:
					return i
				else:
					hashmap[i] = hashmap[i] - 1


class Solution:

	def firstNonRepeating(self, arr, n):
		d = {}
		for i in range(n):
			d[arr[i]] = i
		mini = min(d.values())
		for key in list(d.keys()):
			if d[key] == mini:
				return key
			else:
				pass


class Solution:

	def firstNonRepeating(self, arr, n):
		d = defaultdict(lambda : -1)
		for i in range(n):
			d[arr[i]] = i
		m = 10 ** 9
		x = -1
		for i in d:
			if d[i] < m:
				m = d[i]
				x = i
		return x


class Solution:

	def firstNonRepeating(self, arr, n):
		d = {}
		d[arr[-1]] = 1
		last = arr[-1]
		for i in range(n - 2, -1, -1):
			if arr[i] not in d:
				last = arr[i]
				d[arr[i]] = 1
		return last


class Solution:

	def firstNonRepeating(self, arr, n):
		counter = {}
		for i in range(0, n):
			counter.setdefault(arr[i], i)
			counter[arr[i]] = i
		minval = 1000000
		minkey = 0
		for key in counter:
			if counter[key] < minval:
				minkey = key
				minval = counter[key]
		return minkey


class Solution:

	def firstNonRepeating(self, arr, n):
		d = dict()
		for i in range(n):
			d[arr[i]] = i
		mini = 1000
		for (k, v) in d.items():
			if v < mini:
				mini = v
				ans = k
		return ans


class Solution:

	def firstNonRepeating(self, arr, n):
		m = {}
		for i in range(n):
			m[arr[i]] = i
		r = [(k, v) for (k, v) in m.items()]
		(kk, vv) = (100000, 100000)
		for v in r:
			if vv > v[1]:
				kk = v[0]
				vv = v[1]
		return kk


class Solution:

	def firstNonRepeating(self, arr, n):
		d = {}
		for i in arr:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		for i in range(n):
			if d[arr[i]] == 1:
				return arr[i]
			elif d[arr[i]] > 1:
				d[arr[i]] -= 1
		return -1


class Solution:

	def firstNonRepeating(self, arr, n):
		d = {}
		for i in range(n):
			d[arr[i]] = i
		m = n
		ans = 0
		for i in d:
			if d[i] < m:
				ans = i
				m = d[i]
		return ans


class Solution:

	def firstNonRepeating(self, arr, n):
		model = dict()
		for i in range(n):
			model[arr[i]] = i
		v = min(model.values())
		for i in arr:
			if model[i] == v:
				return i


class Solution:

	def firstNonRepeating(self, arr, n):
		m = {}
		for i in range(n):
			if arr[i] not in m:
				m[arr[i]] = 1
				if m[arr[i]] == arr.count(arr[i]):
					return arr[i]
			else:
				m[arr[i]] = m[arr[i]] + 1
				if m[arr[i]] == arr.count(arr[i]):
					return arr[i]


class Solution:

	def firstNonRepeating(self, arr, n):
		map = {}
		for i in range(len(arr)):
			map[arr[i]] = i
		k = min(map.values())
		for (i, v) in map.items():
			if v == k:
				return i


class Solution:

	def firstNonRepeating(self, arr, n):
		s = set()
		l = n
		for i in range(n - 1, -1, -1):
			if arr[i] not in s:
				s.add(arr[i])
				l = min(l, i)
		return arr[l]


class Solution:

	def firstNonRepeating(self, arr, n):
		d = dict()
		for (i, j) in enumerate(arr):
			d[j] = i
		p = min(d.values())
		return arr[p]


import sys

class Solution:

	def firstNonRepeating(self, arr, n):
		hash = {}
		for i in range(n):
			hash[arr[i]] = i
		res_index = sys.maxsize
		res = 0
		for (i, j) in hash.items():
			if j < res_index:
				res_index = j
				res = i
		return res


class Solution:

	def firstNonRepeating(self, arr, n):
		dic = {}
		for index in range(n):
			element = arr[index]
			if element in dic:
				dic[element].append(index)
			else:
				dic[element] = [index]
		mini_index = int(n) - 1
		item = 0
		for i in dic:
			if dic[i][-1] <= mini_index:
				mini_index = dic[i][-1]
				item = i
		return item


class Solution:

	def firstNonRepeating(self, arr, n):
		d = {}
		for (ind, ele) in enumerate(arr):
			d[ele] = ind
		mval = 99999
		for (key, val) in d.items():
			if val < mval:
				mval = val
				k = key
		return k


class Solution:

	def firstNonRepeating(self, arr, n):
		d = {}
		for e in arr:
			if e not in d:
				d[e] = 1
			else:
				d[e] += 1
		for e in arr:
			d[e] -= 1
			if d[e] == 0:
				return e