Given an array arr[] of size n>3, the task is to check whether the given array can be arranged in the form of a Left or Right positioned array?
Left or Right Positioned Array means each element in the array is equal to the number of elements to its left or number of elements to its right.
Note: 1 represents true and 0 represents false.
 
Example 1:
Input  : 
arr[] = {1, 3, 3, 2}
Output : 
1
Explanation :
This array has one such arrangement {3, 1, 2, 3}.
In this arrangement, first element '3' indicates
that three numbers are after it, the 2nd element
'1' indicates that one number is before it, the
3rd element '2' indicates that two elements are
before it.
 
Example 2:
Input : 
arr[] = {1, 6, 5, 4, 3, 2, 1}
Output :
0
Explanation :
No such arrangement is possible
 
Example 3:
Input : 
arr[] = {2, 0, 1, 3}
Output: 
1
Explanation :
Possible arrangement is {0, 1, 2, 3}
 
Example 4:
Input : 
arr[] = {2, 1, 5, 2, 1, 5}
Output : 
"1"
Explanation :
Possible arrangement is {5, 1, 2, 2, 1, 5}
Your Task:
You don't need to print anything, printing is done by the driver code. You have to complete the function leftRight() which takes the array arr[] and its size N as inputs and returns True if the array can be arranged to form left or right positioned array, else False as the answer.
 
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
4 ≤ N ≤ 100000
0 ≤ arr[i] ≤ 1000

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Starter code: #User function Template for python3

class Solution:
    def leftRight(self, arr, n):
        # Your code goes here

Solutions:
class Solution:

	def leftRight(self, arr, n):
		visit = [0] * (n + 1)
		for i in range(n):
			if arr[i] < n:
				if visit[arr[i]] == 0:
					visit[arr[i]] = 1
				else:
					visit[n - arr[i] - 1] = 1
		for i in range(n):
			if visit[i] == 0:
				return False
		return True


class Solution:

	def leftRight(self, arr, n):
		arr.sort()
		brr = list(range(n))
		crr = list(range(n - 1, -1, -1))
		for _ in range(n):
			if arr[-1] == brr[-1] or arr[-1] == crr[-1]:
				(arr.pop(), brr.pop(), crr.pop())
			elif arr[-1] == brr[0] or arr[-1] == crr[0]:
				(arr.pop(), brr.pop(0), crr.pop(0))
			elif arr[0] == brr[0] or arr[0] == crr[0]:
				(arr.pop(0), brr.pop(0), crr.pop(0))
		return not arr


class Solution:

	def leftRight(self, arr, n):
		vis = [0] * n
		for i in range(n):
			if arr[i] < n:
				if vis[arr[i]] == 0:
					vis[arr[i]] = 1
				else:
					vis[n - arr[i] - 1] = 1
		for i in range(n):
			if vis[i] == 0:
				return 0
		return 1


class Solution:

	def leftRight(self, arr, n):
		for j in range(n):
			a = [-1] * n
			for i in range(n):
				if arr[i] >= n:
					return 0
				if a[arr[i]] == -1:
					a[arr[i]] = arr[i]
				elif a[n - arr[i] - 1] == -1:
					a[n - arr[i] - 1] = arr[i]
				else:
					return False
		return True


class Solution:

	def leftRight(self, arr, n):
		if max(arr) >= n:
			return 0
		rt = 1
		x = [-1] * n
		for i in arr:
			if x[i] == -1:
				x[i] = i
			elif x[n - i - 1] == -1:
				x[n - i - 1] = i
			else:
				rt = 0
		return rt


class Solution:

	def leftRight(self, arr, n):
		vis = [0] * n
		for i in arr:
			try:
				if vis[i] == 1:
					vis[n - i - 1] = 1
				else:
					vis[i] = 1
			except:
				return False
		if 0 in vis:
			return False
		return True