Given an array arr of size N, write a program that returns 1 if array represents Inorder traversal of a BST, else returns 0.
Note: All keys in BST must be unique.
Example 1:
Input:
N = 3
arr = {2, 4, 5}
Output: 1
Explaination: Given arr representing
inorder traversal of a BST.
Example 2:
Input:
N = 3
arr = {2, 4, 1}
Output: 0
Explaination: Given arr is not representing
inorder traversal of a BST.
Your Task:
You don't need to read input or print anything. Your task is to complete the function isRepresentingBST() which takes the array arr[] and its size N as input parameters and returns 1 if array represents Inorder traversal of a BST, else returns 0. 
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N ≤ 10^{3}
1 ≤ arr[i] ≤ 10^{3}

Source: geeksforgeeks | Difficulty: EASY
Tags: Tree algorithms

Data structures

Range queries

Starter code: #User function Template for python3

class Solution:
    def isRepresentingBST(self, arr, N):
        # code here

Solutions:
class Solution:

	def isRepresentingBST(self, arr, N):
		i = 1
		while i < len(arr):
			if arr[i - 1] >= arr[i]:
				return 0
			i += 1
		return 1


class Solution:

	def isRepresentingBST(self, arr, N):
		x = list(set(arr))
		x.sort()
		if x == arr:
			return 1
		else:
			return 0


class Solution:

	def isRepresentingBST(self, arr, N):
		for i in range(N - 1):
			if arr[i] >= arr[i + 1]:
				return 0
		return 1


class Solution:

	def isRepresentingBST(self, arr, N):
		if N != len(set(arr)):
			return 0
		s = arr.copy()
		s.sort()
		if s == arr:
			return 1
		return 0


class Solution:

	def isRepresentingBST(self, arr, N):
		i = 0
		prev = -1
		while i < N:
			if prev != -1 and arr[i] <= prev:
				return 0
			prev = arr[i]
			i += 1
		return 1


class Solution:

	def isRepresentingBST(self, arr, N):
		x = []
		x.extend(arr)
		x.sort()
		if x == arr and len(set(arr)) == len(arr):
			return 1
		return 0


class Solution:

	def isRepresentingBST(self, arr, N):
		return 1 if arr == sorted(list(set(arr))) else 0


class Solution:

	def isRepresentingBST(self, arr, N):
		a = arr.copy()
		a.sort()
		b = set(arr)
		if a == arr and len(b) == N:
			return 1
		return 0


class Solution:

	def isRepresentingBST(self, arr, N):
		num = [i for i in arr]
		num = list(set(num))
		if len(num) < N:
			return 0
		num.sort()
		if num == arr:
			return 1
		else:
			return 0


class Solution:

	def isRepresentingBST(self, arr, N):
		lis = arr.copy()
		mis = arr.copy()
		mis = set(mis)
		lis.sort()
		if N != len(mis):
			return 0
		if arr != lis:
			return 0
		return 1


class Solution:

	def isRepresentingBST(self, arr, N):
		d = {}
		for i in arr:
			if i not in d:
				d[i] = 1
			else:
				return 0
		return 1


class Solution:

	def isRepresentingBST(self, arr, N):
		_represents = 1
		for _ in range(1, len(arr)):
			if arr[_] <= arr[_ - 1]:
				_represents = 0
				break
		return _represents


class Solution:

	def isRepresentingBST(self, arr, N):
		s = set()
		for i in arr:
			if i in s:
				return 0
			else:
				s.add(i)
		return int(sorted(arr) == arr)


class Solution:

	def isRepresentingBST(self, arr, N):
		if arr == sorted(arr) and len(arr) == len(set(arr)):
			return 1
		return 0


class Solution:

	def isRepresentingBST(self, arr, N):
		se = []
		for val in arr:
			if val not in se:
				se.append(val)
		if se == arr:
			return 1
		else:
			return 0


class Solution:

	def isRepresentingBST(self, arr, N):
		dic = {}
		for i in range(N - 1):
			if arr[i] not in dic:
				dic[arr[i]] = 1
			else:
				return 0
			if arr[i] > arr[i + 1]:
				return 0
		return 1


class Solution:

	def isRepresentingBST(self, arr, n):
		for i in range(1, n):
			if arr[i] > arr[i - 1]:
				continue
			else:
				return 0
		return 1


class Solution:

	def isRepresentingBST(self, arr, N):
		rslt = 1
		el = arr[0]
		for i in range(1, N):
			if arr[i] <= el:
				rslt = 0
				break
			el = arr[i]
		return rslt


class Solution:

	def isRepresentingBST(self, arr, N):
		l = list(set(arr))
		l.sort()
		if arr == l:
			return 1
		else:
			return 0
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		arr = input().split()
		for itr in range(N):
			arr[itr] = int(arr[itr])
		ob = Solution()
		print(ob.isRepresentingBST(arr, N))


class Solution:

	def isRepresentingBST(self, arr, N):
		for i in range(1, N):
			if arr[i - 1] >= arr[i]:
				return 0
		return 1
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		arr = input().split()
		for itr in range(N):
			arr[itr] = int(arr[itr])
		ob = Solution()
		print(ob.isRepresentingBST(arr, N))


class Solution:

	def isRepresentingBST(self, arr, N):
		pre = 0
		for num in arr[1:]:
			if arr[pre] > num or arr[pre] == num:
				return 0
			pre += 1
		return 1


from queue import Queue

class Solution:

	def isRepresentingBST(self, arr, N):
		min1 = None
		for i in arr:
			if min1 is None or min1 < i:
				min1 = i
			else:
				return 0
		return 1


class Solution:

	def isRepresentingBST(self, arr, N):
		l = []
		for x in range(len(arr)):
			l.append(arr[x])
		l = list(set(l))
		l.sort()
		arr.sort()
		if l == arr and len(arr) == len(l) == N:
			return 1
		else:
			return 0


class Solution:

	def isRepresentingBST(self, arr, N):
		l = set(arr)
		if len(l) != N:
			return 0
		for i in range(1, N):
			if arr[i - 1] > arr[i]:
				return 0
		return 1


class Solution:

	def isRepresentingBST(self, arr, N):
		arr1 = []
		for i in arr:
			arr1.append(i)
		n_arr1 = sorted(list(set(arr1)))
		if arr1 == n_arr1 and len(arr1) == len(n_arr1) == N:
			return 1
		else:
			return 0


class Solution:

	def isRepresentingBST(self, arr, N):
		j = []
		for i in range(len(arr)):
			j.append(arr[i])
		arr = sorted(arr)
		j = sorted(list(set(j)))
		if arr == j and len(arr) == len(j) == N:
			return 1
		else:
			return 0


class Solution:

	def isRepresentingBST(self, arr, N):
		Set = list(set(arr))
		if len(Set) != len(arr):
			return 0
		else:
			for i in range(N - 1):
				if arr[i] >= arr[i + 1]:
					return 0
			return 1