Given a sorted array arr[ ] of N positive integers. Your task is to find an index i in the array from where the number of elements smaller than arr[i] in the left side of the index is equal to the number of elements greater than arr[i] in the right side of the index.
If no such index exists, print "-1".
Example 1:
Input:
N = 6
arr[] = {1, 2, 3, 3, 3, 3}
Output:
1
Explanation:
2 is the element before which we have one
element that is smaller than 2 and we have
one element to its right which is greater
than 2. Hence, print the index of 2.
Example 2:
Input:
N = 8
arr[] = {1, 2, 3, 3, 3, 3, 4, 4}
Output:
-1
Explanation:
There is no index as such, so print -1
Your Task:  
You don't need to read input or print anything. Your task is to complete the function findEqualPoint() which takes the array arr[] and its size N as input parameters and returns the required index. If there are multiple indices, return the smallest one. If such index doesn't exist then return "-1" (without quotes).
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 10^{5}
1 ≤ A_{i} ≤ 10^{12}

Source: geeksforgeeks | Difficulty: EASY

Starter code: #User function Template for python3

def findEqualPoint(arr, n):
    # Your code goes here

Solutions:
def findEqualPoint(arr, n):
	if n == 1:
		return 0
	mini = [0] * n
	maxi = [0] * n
	for j in range(n - 2, -1, -1):
		if arr[j] == arr[j + 1]:
			maxi[j] = maxi[j + 1]
		else:
			maxi[j] = maxi[j + 1] + 1
	for i in range(1, n):
		if arr[i] == arr[i - 1]:
			mini[i] = mini[i - 1]
		else:
			mini[i] = mini[i - 1] + 1
		if mini[i] == maxi[i]:
			return i
	return -1


import math

def findEqualPoint(arr, n):
	x = sorted(set(arr))
	if len(x) % 2 != 0:
		x1 = x[math.floor(len(x) / 2)]
		return arr.index(x1)
	else:
		return -1


def findEqualPoint(arr, n):
	stack = [arr[0]]
	for num in arr:
		if num != stack[-1]:
			stack.append(num)
	if len(stack) % 2 == 0:
		return -1
	elif len(stack) == 1:
		return 0
	middle = stack[int(len(stack) / 2)]
	return arr.index(middle)