Given two positive integers x and y, and an array arr[] of positive integers. We need to find the longest prefix index which contains an equal number of x and y. Print the maximum index of largest prefix if exist otherwise print -1.
 
Example 1:
Input:
N=11
X=7  Y=42
arr[] = [ 7, 42, 5, 6, 42, 8, 7, 5, 3, 6, 7 ]
Output: 9
Explanation: The longest prefix with same 
number of occurrences of 7 and 42 is:
7, 42, 5, 6, 42, 8, 7, 5, 3, 6 
Example 2:
Input:
N=3
X=1 Y=2 
arr[] = [ 1,2,2 ]
Output: 1
Your Task:
Since this is a function problem. You don't need to take any input, as it is already accomplished by the driver code. You just need to complete the function findIndex() that takes array arr, integer X, integer Y, and integer N as parameters and return the desired result.
 
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
 
Constraints:
2 ≤ N ≤ 105
X != Y

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Range queries

Starter code: #User function Template for python3


def findIndex(arr,X,Y,N):
    # Your code goes here

Solutions:
def findIndex(arr, X, Y, N):
	countx = 0
	county = 0
	index = 0
	for i in range(N):
		if X == arr[i]:
			countx += 1
		elif Y == arr[i]:
			county += 1
		if countx == county and countx != 0 and (county != 0):
			index = i
	return index if index > 0 else -1


def findIndex(arr, X, Y, N):
	countX = 0
	countY = 0
	j = -1
	for i in range(N):
		if arr[i] == X:
			countX += 1
		if arr[i] == Y:
			countY += 1
		if countX == countY and countX != 0:
			j = max(i, j)
	return j


def findIndex(arr, X, Y, N):
	n = len(arr)
	count_x = 0
	count_y = 0
	ans = -1
	for i in range(n):
		if arr[i] == X:
			count_x += 1
		elif arr[i] == Y:
			count_y += 1
		if count_x == count_y:
			ans = i
	if ans == -1:
		return ans
	for i in range(ans + 1):
		if arr[i] == X or arr[i] == Y:
			return ans
	if i == ans:
		return -1


def findIndex(arr, X, Y, N):
	c_x = 0
	c_y = 0
	index = 0
	for i in range(N):
		if X == arr[i]:
			c_x += 1
		elif Y == arr[i]:
			c_y += 1
		if c_x == c_y and c_x != 0 and (c_y != 0):
			index = i
	if index != 0:
		return index
	else:
		return -1


def findIndex(arr, X, Y, N):
	result = -1
	nX = 0
	nY = 0
	for i in range(N):
		if arr[i] == X:
			nX += 1
		if arr[i] == Y:
			nY += 1
		if nX == nY and nX > 0 and (nY > 0):
			result = i
	return result


def findIndex(arr, X, Y, N):
	count_x = 0
	count_y = 0
	index = 0
	for i in range(N):
		if X == arr[i]:
			count_x += 1
		elif Y == arr[i]:
			count_y += 1
		if count_x == count_y and count_x != 0 and (count_y != 0):
			index = i
	return index if index != 0 else -1


import math

def findIndex(arr, X, Y, N):
	maxi = -1
	(a, b) = (0, 0)
	for i in range(N):
		if arr[i] == X:
			a += 1
		if arr[i] == Y:
			b += 1
		if a == b and a != 0:
			maxi = max(maxi, i)
	return maxi


def findIndex(arr, X, Y, N):
	x_count = 0
	y_count = 0
	x_index = -1
	y_index = -1
	max_ind = -1
	for index in range(n):
		if arr[index] == X:
			x_count += 1
			x_index = index if x_index == -1 else x_index
		elif arr[index] == Y:
			y_count += 1
			y_index = index if y_index == -1 else y_index
		if x_count == y_count and x_count > 0 and (y_count > 0):
			max_ind = index
	return max_ind


def findIndex(arr, X, Y, N):
	count = 0
	output = -1
	flag = False
	for (i, item) in enumerate(arr):
		if item == X or item == Y:
			flag = True
		count += item == X
		count -= item == Y
		if flag and count == 0:
			output = i
	return output


def findIndex(arr, X, Y, N):
	(x, y) = (0, 0)
	res = -1
	for i in range(N):
		if arr[i] == X:
			x += 1
		if arr[i] == Y:
			y += 1
		if x != 0 and x == y:
			res = i
	return res


def findIndex(arr, X, Y, N):
	k = -1
	(cx, cy) = (0, 0)
	for i in range(n):
		if arr[i] == X:
			cx += 1
		if arr[i] == Y:
			cy += 1
		if cx == cy and cx > 0:
			k = i
	return k


def findIndex(arr, X, Y, N):
	cx = 0
	cy = 0
	ind = 0
	for i in range(N):
		if X == arr[i]:
			cx += 1
		elif Y == arr[i]:
			cy += 1
		if cx == cy and cx != 0 and (cy != 0):
			ind = i
	if ind != 0:
		return ind
	else:
		return -1


def findIndex(arr, X, Y, N):
	c1 = 0
	c2 = 0
	ind = 0
	for i in range(N):
		if X == arr[i]:
			c1 += 1
		elif Y == arr[i]:
			c2 += 1
		if c1 == c2 and c1 != 0 and (c2 != 0):
			ind = i
	if ind != 0:
		return ind
	else:
		return -1


def findIndex(arr, X, Y, N):
	b = []
	for i in range(N):
		if arr[i] == X:
			arr[i] = 1
		elif arr[i] == Y:
			arr[i] = -1
		else:
			arr[i] = 0
		if i == 0:
			b.append(arr[i])
		else:
			b.append(arr[i] + b[i - 1])
	k = 0
	max = -999
	for i in range(N):
		if k == 0:
			if arr[i] != 0:
				k = 1
		elif b[i] == 0:
			if i > max:
				max = i
	if max == -999:
		return -1
	else:
		return max


def findIndex(arr, x, y, n):
	c1 = 0
	c2 = 0
	ma = 0
	for i in range(n):
		if arr[i] == x:
			c1 += 1
		elif arr[i] == y:
			c2 += 1
		if c1 == c2 and c1 != 0 and (c2 != 0):
			ma = i
	return ma if ma != 0 else -1


def findIndex(arr, X, Y, N):
	z = 0
	c1 = 0
	c2 = 0
	for i in range(len(arr)):
		if arr[i] == X:
			c1 += 1
		elif arr[i] == Y:
			c2 += 1
		if c1 == c2 and c1 != 0 and (c2 != 0):
			z = i
	if z == 0 or z == N:
		return -1
	else:
		return z


def findIndex(arr, X, Y, N):
	cx = 0
	cy = 0
	h = -1
	next = -1
	for j in range(N):
		if arr[j] == X:
			cx += 1
		if arr[j] == Y:
			cy += 1
		if cx == cy and cx > 0 and (cy > 0):
			h = j
			next = j
	if next == -1:
		return -1
	else:
		return next


def findIndex(arr, X, Y, N):
	x = 0
	y = 0
	index = 0
	for i in range(N):
		if X == arr[i]:
			x += 1
		elif Y == arr[i]:
			y += 1
		if x == y and x != 0 and (y != 0):
			index = i
	if index != 0:
		return index
	else:
		return -1


from collections import Counter

def findIndex(arr, X, Y, N):
	rec = Counter()
	ans = -1
	for (i, x) in enumerate(arr):
		rec[x] += 1
		if X in rec and rec[X] == rec[Y]:
			ans = i
	return ans


def findIndex(arr, X, Y, N):
	ans = -1
	count_x = 0
	count_y = 0
	for i in range(N):
		if arr[i] == X:
			count_x += 1
		if arr[i] == Y:
			count_y += 1
		if count_x == count_y and count_x > 0 and (count_y > 0):
			ans = i
	return ans


def findIndex(arr, X, Y, N):
	res = -1
	(c1, c2) = (0, 0)
	flag = False
	for i in range(N):
		if arr[i] == X or arr[i] == Y:
			if arr[i] == X:
				c1 += 1
			else:
				c2 += 1
			if not flag:
				flag = True
		if flag and c1 == c2:
			res = i
	return res


def findIndex(arr, X, Y, N):
	cx = 0
	cy = 0
	mi = -1
	for i in range(N):
		if arr[i] == X:
			cx += 1
		elif arr[i] == Y:
			cy += 1
		if cx != 0 and cy != 0 and (cx == cy):
			mi = max(mi, i)
	return mi


def findIndex(arr, X, Y, N):
	cnt_x = 0
	cnt_y = 0
	idx = 0
	for i in range(N):
		if X == arr[i]:
			cnt_x += 1
		elif Y == arr[i]:
			cnt_y += 1
		if cnt_x == cnt_y and cnt_x != 0 and (cnt_y != 0):
			idx = i
	return idx if idx != 0 else -1


def findIndex(arr, X, Y, N):
	xc = 0
	yc = 0
	ind = -1
	for i in range(N):
		if arr[i] == X:
			xc += 1
		if arr[i] == Y:
			yc += 1
		if xc == yc and xc != 0 and (yc != 0):
			ind = i
	if ind == -1:
		return -1
	else:
		return ind


def findIndex(arr, X, Y, N):
	k = 0
	l = 0
	ki = 0
	for i in range(N):
		if arr[i] == X:
			k += 1
		if arr[i] == Y:
			l += 1
		if k == l and k != 0 and (l != 0):
			ki = i
	if ki != 0:
		return ki
	else:
		return -1


def findIndex(arr, x, y, n):
	l = []
	c1 = 0
	c2 = 0
	k = 0
	for i in range(n):
		if arr[i] == x:
			c1 = c1 + 1
		elif arr[i] == y:
			c2 = c2 + 1
		if c1 == c2 and c1 != 0 and (c2 != 0):
			k = i
	if k != 0:
		return k
	return -1


def findIndex(arr, X, Y, N):
	prefix = -1
	xcount = 0
	ycount = 0
	for i in range(N):
		if arr[i] == X:
			xcount += 1
		if arr[i] == Y:
			ycount += 1
		if xcount != 0 and xcount == ycount:
			prefix = i
	return prefix


def findIndex(arr, X, Y, N):
	ax = 0
	ay = 0
	res = -1
	for i in range(N):
		if arr[i] == X:
			ax += 1
		if arr[i] == Y:
			ay += 1
		if ax == ay and (ax != 0 and ay != 0):
			res = i
	return res


def findIndex(arr, X, Y, N):
	count = {}
	index = -1
	for i in range(len(arr)):
		if arr[i] == X or arr[i] == Y:
			if arr[i] not in count:
				count[arr[i]] = 1
			else:
				count[arr[i]] += 1
		if X in count and Y in count:
			if count[X] == count[Y]:
				index = i
	return index


def findIndex(arr, X, Y, N):
	cx = 0
	cy = 0
	ans = -1
	for i in range(len(arr)):
		if arr[i] == X:
			cx = cx + 1
		if arr[i] == Y:
			cy = cy + 1
		if cx != 0 and cy != 0 and (cx == cy):
			ans = i
	return ans


def findIndex(arr, X, Y, N):
	cnt_x = 0
	cnt_y = 0
	j = -1
	for i in range(N):
		if arr[i] == X:
			cnt_x += 1
		if arr[i] == Y:
			cnt_y += 1
		if cnt_x == cnt_y and cnt_x != 0 and (cnt_y != 0):
			j = max(j, i)
	return j


def findIndex(arr, X, Y, N):
	countx = 0
	county = 0
	last_index = -1
	for i in range(n):
		if arr[i] == X:
			countx += 1
		if arr[i] == Y:
			county += 1
		if countx != 0 and countx == county:
			last_index = i
	return last_index


def findIndex(arr, X, Y, N):
	count_X = 0
	count_Y = 0
	j = -1
	for i in range(N):
		if arr[i] == X:
			count_X += 1
		if arr[i] == Y:
			count_Y += 1
		if count_X != 0 and count_Y != 0 and (count_X == count_Y):
			j = i
	return j
t = int(input())
for _ in range(0, t):
	l = list(map(int, input().split()))
	n = l[0]
	x = l[1]
	y = l[2]
	a = list(map(int, input().split()))
	ans = findIndex(a, x, y, n)
	print(ans)


def findIndex(arr, X, Y, N):
	d = -1
	xc = 0
	yc = 0
	for i in range(N):
		if arr[i] == X:
			xc += 1
		if arr[i] == Y:
			yc += 1
		if xc == yc and xc != 0:
			d = i
	return d
t = int(input())
for _ in range(0, t):
	l = list(map(int, input().split()))
	n = l[0]
	x = l[1]
	y = l[2]
	a = list(map(int, input().split()))
	ans = findIndex(a, x, y, n)
	print(ans)


def findIndex(arr, X, Y, N):
	cntx = 0
	cnty = 0
	inx = -1
	for i in range(N):
		if arr[i] == X:
			cntx += 1
		if arr[i] == Y:
			cnty += 1
		if cntx == cnty and cntx != 0:
			inx = i
	return inx
t = int(input())
for _ in range(0, t):
	l = list(map(int, input().split()))
	n = l[0]
	x = l[1]
	y = l[2]
	a = list(map(int, input().split()))
	ans = findIndex(a, x, y, n)
	print(ans)


def findIndex(arr, X, Y, N):
	xcount = arr.count(X)
	ycount = arr.count(Y)
	yitr = 0
	xitr = 0
	if xcount == ycount:
		return N - 1
	maxReached = -1
	for itr in range(N):
		if arr[itr] == x:
			xitr += 1
		elif arr[itr] == y:
			yitr += 1
		if xitr == yitr and xitr != 0:
			maxReached = itr
	return maxReached
t = int(input())
for _ in range(0, t):
	l = list(map(int, input().split()))
	n = l[0]
	x = l[1]
	y = l[2]
	a = list(map(int, input().split()))
	ans = findIndex(a, x, y, n)
	print(ans)


def findIndex(arr, X, Y, N):
	xc = yc = -1
	idx = -1
	for (i, v) in enumerate(arr):
		xc += v == X
		yc += v == Y
		if xc == yc and -1 not in (xc, yc):
			idx = i
	return idx


def findIndex(arr, X, Y, N):
	count_X = 0
	count_Y = 0
	ind = -1
	maxi = -1
	for i in range(N):
		if arr[i] == X:
			count_X += 1
		if arr[i] == Y:
			count_Y += 1
		if count_X != 0 and count_Y != 0 and (count_X == count_Y):
			ind = i
	return ind


def findIndex(arr, X, Y, N):
	res = -1
	sx = 0
	sy = 0
	for (i, j) in enumerate(arr):
		if j == X:
			sx += 1
		elif j == Y:
			sy += 1
		if sx == sy and sx:
			res = i
	return res


def findIndex(arr, X, Y, N):
	a = 0
	b = 0
	res = -1
	for i in range(N):
		if arr[i] == X:
			a += 1
		elif arr[i] == Y:
			b += 1
		if a == b and (a != 0 and b != 0):
			res = i
	return res


def findIndex(arr, X, Y, N):
	a = 0
	b = 0
	for i in range(N):
		if arr[i] == X:
			a += 1
		elif arr[i] == Y:
			b += 1
	dif = 0
	el = 0
	if a > b:
		dif = a - b
		el = X
		ex = Y
	elif b > a:
		dif = b - a
		el = Y
		ex = X
	minx = min(a, b)
	r = N - 1
	if dif == 0:
		return N - 1
	k = 0
	for i in range(N - 1, 0, -1):
		if arr[i] == el:
			dif -= 1
		elif arr[i] == ex:
			dif += 1
			k += 1
		if k == minx:
			return -1
		if dif == 0:
			return i - 1
	return -1


from collections import defaultdict

def findIndex(arr, X, Y, N):
	d = defaultdict(int)
	index = 0
	for i in range(N):
		if arr[i] == X:
			d[X] += 1
		if arr[i] == Y:
			d[Y] += 1
		if d[X] == d[Y] and d[X] != 0:
			index = max(i, index)
	if index == 0:
		return -1
	return index


from collections import defaultdict

def findIndex(arr, X, Y, N):
	counter_x = 0
	counter_y = 0
	index = 0
	for i in range(N):
		if arr[i] == X:
			counter_x += 1
		if arr[i] == Y:
			counter_y += 1
		if counter_x != 0 and counter_y != 0 and (counter_x == counter_y):
			index = max(i, index)
	if index == 0:
		return -1
	return index


def findIndex(arr, X, Y, N):
	x = 0
	y = 0
	maxi = -1
	for i in range(0, N):
		if arr[i] == X:
			x += 1
		elif arr[i] == Y:
			y += 1
		if x == y and x > 0 and (y > 0):
			maxi = max(maxi, i)
	return maxi


def findIndex(arr, X, Y, N):
	p1 = 0
	p2 = 0
	ans = -1
	for i in range(N):
		value = arr[i]
		if value == X:
			p1 += 1
		if value == Y:
			p2 += 1
		if p1 == p2 and p1 != 0:
			ans = i
	return ans


def findIndex(a, x, y, n):
	xx = 0
	yy = 0
	ans = -1
	for i in range(n):
		if a[i] == x:
			xx += 1
		elif a[i] == y:
			yy += 1
		if xx == yy and xx != 0 and (yy != 0):
			ans = i
	return ans if ans else -1


def findIndex(arr, X, Y, N):
	end_index = -1
	X_count = 0
	Y_count = 0
	for i in range(N):
		if arr[i] == X:
			X_count += 1
		if arr[i] == Y:
			Y_count += 1
		if X_count == Y_count and X_count > 0:
			end_index = i
	return end_index


def findIndex(arr, X, Y, N):
	x = 0
	y = 0
	index = -1
	i = 0
	for item in arr:
		if X == item:
			x = x + 1
		elif Y == item:
			y = y + 1
		if x == y and x > 0 and (y > 0):
			index = max(index, i)
		i = i + 1
	return index


def findIndex(arr, X, Y, N):
	stk = []
	for i in range(N):
		if arr[i] == X:
			arr[i] = 1
		elif arr[i] == Y:
			arr[i] = -1
		else:
			arr[i] = 0
	summ = 0
	index = -1
	flag = False
	for i in range(N):
		if arr[i] == 1 or arr[i] == -1:
			summ += arr[i]
			flag = True
		if flag and summ == 0:
			index = i
	return index


def findIndex(arr, X, Y, N):
	count_x = 0
	count_y = 0
	longest = 0
	count = 0
	bfr = 0
	for i in range(N):
		if arr[i] == X:
			count_x += 1
		elif arr[i] == Y:
			count_y += 1
		if count_x > 0 and count_y > 0 and (count_x == count_y):
			count += 1 + bfr
			bfr = 0
		else:
			bfr += 1
	return count - 1 if count > 0 else -1


def findIndex(arr, x, y, n):
	xc = yc = 0
	m = -1
	for i in range(len(arr)):
		if arr[i] == x:
			xc += 1
		elif arr[i] == y:
			yc += 1
		if i == 0:
			if xc == yc and xc != 0 and (yc != 0):
				m = i
			continue
		elif xc == yc and xc != 0 and (yc != 0):
			m = i
	if xc == 0 or yc == 0:
		return -1
	return m


def findIndex(arr, X, Y, N):
	c = 0
	d = 0
	ind = 0
	for i in range(n):
		if arr[i] == X:
			c += 1
		if arr[i] == Y:
			d += 1
		if c == d and c != 0 and (d != 0):
			ind = i
	if ind == 0:
		return -1
	return ind


def findIndex(arr, X, Y, N):
	a = 0
	b = 0
	ind = -1
	for i in range(len(arr)):
		if arr[i] == X:
			a += 1
		if arr[i] == Y:
			b += 1
		if a == b and a != 0:
			ind = i
	return ind


def findIndex(arr, X, Y, N):
	c = d = e = 0
	for i in range(len(arr)):
		if arr[i] == X:
			c += 1
		elif arr[i] == Y:
			d += 1
		if c == d and c != 0 and (d != 0):
			e = i
	if e == 0:
		return -1
	return e


def findIndex(arr, x, y, n):
	cx = 0
	cy = 0
	res = -1
	for i in range(n):
		if arr[i] == x:
			cx += 1
		if arr[i] == y:
			cy += 1
		if cx == cy and cx != 0:
			res = i
	return res