Given an array A[]of size N. Let us call difference between indices of an element's first and last appearance in the array A[] a gap. Find the maximum possible gap.  Note that if any element appears only once, then the gap for that element is 0.
 
Example 1:
Input:
N = 9
A[] = {2, 1, 3, 4, 2, 1, 5, 1, 7}
Output:
6
Explanation:
For the above test case (Assuming 0-based indexing): 
Number 1's first appearance is at index 1 and last appearance is at index 7. This implies gap is 7-1=6
This is the maximum possible in the given test case.
 
Your Task:  
You don't need to read input or print anything. Your task is to complete the function leftIndex() which takes the array A[] and its size N as inputs and returns the Maximum Difference.
 
Expected Time Complexity: O(N. Log(N))
Expected Auxiliary Space: O(N)
 
Constraints:
1<=N<=10^{5}
-10^{5}<=A_{i}<=10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Starter code: #User function Template for python3


class Solution:
    def maxDiffIndex(self, A, N):
        # code here
    


Solutions:
import math

class Solution:

	def maxDiffIndex(self, A, N):
		maxi = -math.inf
		dicti = {}
		for i in range(N):
			if A[i] not in dicti:
				dicti[A[i]] = i
			else:
				maxi = max(maxi, i - dicti[A[i]])
		if maxi == -math.inf:
			return 0
		return maxi


class Solution:

	def maxDiffIndex(self, A, N):
		diff = 0
		dict_ = {}
		for index in range(N):
			elem = A[index]
			ind = dict_.get(elem, -1)
			if ind == -1:
				dict_.update({elem: index})
			else:
				current_diff = index - dict_[elem]
				diff = index - dict_[elem] if diff < current_diff else diff
		return diff


class Solution:

	def maxDiffIndex(self, A, N):
		d = {}
		id = 0
		for i in range(N):
			if A[i] not in d:
				d[A[i]] = i
			elif i - d[A[i]] > id:
				id = i - d[A[i]]
		return id


class Solution:

	def maxDiffIndex(self, A, N):
		B = list(reversed(A))
		maxi = 0
		visited = set()
		i = -1
		while i + maxi < N - 1:
			i += 1
			if A[i] in visited:
				continue
			visited.add(A[i])
			diff = N - 1 - i - B.index(A[i])
			if diff > maxi:
				maxi = diff
		return maxi


class Solution:

	def maxDiffIndex(self, A, N):
		maxi = 0
		rev = A[::-1]
		for i in list(set(A)):
			fir = A.index(i)
			las = rev.index(i)
			las = len(A) - las - 1
			maxi = max(maxi, las - fir)
		return maxi


class Solution:

	def maxDiffIndex(self, A, N):
		d1 = {}
		d2 = {}
		for i in range(len(A)):
			if A[i] not in d1:
				d1[A[i]] = i
		for i in reversed(range(len(A))):
			if A[i] not in d2:
				d2[A[i]] = i
		maximum = -987654321
		for (k, v) in d1.items():
			maximum = max(maximum, d2[k] - v)
		return maximum


class Solution:

	def maxDiffIndex(self, A, N):
		result = []
		dict = {}
		for i in range(N):
			dict[A[i]] = i
		for j in range(N):
			value = abs(dict[A[j]] - j)
			result.append(value)
		return max(result)


class Solution:

	def maxDiffIndex(self, A, N):
		maxi = 0
		temp = {}
		for i in range(N):
			if A[i] not in temp:
				temp[A[i]] = i
			else:
				maxi = max(maxi, i - temp[A[i]])
		return maxi


from collections import defaultdict

class Solution:

	def maxDiffIndex(self, A, N):
		di = defaultdict(list)
		ans = []
		for i in range(N):
			di[A[i]].append(i)
		values = di.values()
		for i in values:
			if len(i) == 1:
				continue
			else:
				ans.append(i[-1] - i[0])
		if len(ans) != 0:
			return max(ans)
		else:
			return 0


class Solution:

	def maxDiffIndex(self, A, N):
		m = {}
		for i in range(len(A)):
			m[A[i]] = i
		A = A[::-1]
		d = {}
		for j in range(len(A)):
			d[A[j]] = N - j - 1
		r = sorted(m.items())
		r = dict(r)
		e = sorted(d.items())
		e = dict(e)
		u = []
		v = []
		for (x, y) in r.items():
			u.append(y)
		for (x, y) in e.items():
			v.append(y)
		h = []
		for k in range(len(u)):
			h.append(abs(u[k] - v[k]))
		return max(h)


class Solution:

	def maxDiffIndex(self, A, N):
		first = {}
		last = {}
		max_diff = -123456789
		for i in range(N):
			if A[i] not in first:
				first[A[i]] = i
			if A[i] not in last:
				last[A[i]] = i
			else:
				last[A[i]] = i
		for key in first:
			diff = last[key] - first[key]
			max_diff = max(max_diff, diff)
		return max_diff


class Solution:

	def maxDiffIndex(self, A, N):
		d = {}
		for i in range(N):
			a = A[i]
			if a not in d:
				d[a] = [i]
			else:
				d[a].append(i)
		x = []
		for i in d:
			b = d[i]
			x.append(b[-1] - b[0])
		return max(x)


class Solution:

	def maxDiffIndex(self, A, N):
		h = {}
		for i in range(N):
			if A[i] not in h:
				h[A[i]] = [i]
			else:
				h[A[i]] += [i]
		ans = []
		for i in h:
			if len(h[i]) == 1:
				ans.append(0)
			else:
				ans.append(h[i][-1] - h[i][0])
		return max(ans)


class Solution:

	def maxDiffIndex(self, A, N):
		rslt = 0
		dc = {}
		for i in range(N):
			a = A[i]
			if a in dc.keys():
				if i - dc[a] > rslt:
					rslt = i - dc[a]
			else:
				dc[a] = i
		return rslt

def main():
	T = int(input())
	while T > 0:
		n = int(input())
		a = [int(x) for x in input().strip().split()]
		ob = Solution()
		print(ob.maxDiffIndex(a, n))
		T -= 1
if __name__ == '__main__':
	main()


class Solution:

	def maxDiffIndex(self, A, N):
		d = {}
		for i in range(N):
			if A[i] not in d:
				d[A[i]] = i
		ans = 0
		for i in range(N - 1, -1, -1):
			if A[i] in d:
				ans = max(ans, i - d[A[i]])
		return ans


class Solution:

	def maxDiffIndex(self, A, N):
		d = {}
		mx = 0
		for i in range(N):
			if A[i] in d:
				mx = max(abs(d[A[i]] - i), mx)
			else:
				d[A[i]] = i
		return mx


class Solution:

	def maxDiffIndex(self, arr, n):
		d = dict()
		res = 0
		for i in range(n):
			if arr[i] in d:
				res = max(res, i - d[arr[i]])
			else:
				d[arr[i]] = i
		return res


class Solution:

	def maxDiffIndex(self, A, N):
		max_diff = 0
		d = {}
		for i in range(N):
			if A[i] not in d:
				d[A[i]] = i
			else:
				max_diff = max(max_diff, i - d[A[i]])
		return max_diff


class Solution:

	def maxDiffIndex(self, A, N):
		d = {}
		f = {}
		for i in range(len(A)):
			if A[i] not in d:
				d[A[i]] = i
			else:
				continue
		for i in range(len(A) - 1, -1, -1):
			if A[i] not in f:
				f[A[i]] = i
			else:
				continue
		max_val = -9999
		for key in d.keys():
			if abs(d[key] - f[key]) > max_val:
				max_val = abs(d[key] - f[key])
		return max_val