Given an array arr[ ] of size N consisting of distinct integers, write a program that returns 1 if given array can represent preorder traversal of a possible BST, else returns 0.
Example 1:
Input:
N = 3
arr = {2, 4, 3}
Output: 1
Explaination: Given arr[] can represent
preorder traversal of following BST:
               2
                \
                 4
                /
               3
Example 2:
Input:
N = 3
Arr = {2, 4, 1}
Output: 0
Explaination: Given arr[] cannot represent
preorder traversal of a BST.
Your Task:
You don't need to read input or print anything. Your task is to complete the function canRepresentBST() which takes the array arr[] and its size N as input parameters and returns 1 if given array can represent preorder traversal of a BST, else returns 0.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 10^{5}
0 ≤ arr[i] ≤ 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Tree algorithms

Data structures

Range queries

Starter code: #User function Template for python3

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

Solutions:
from sys import maxsize

class Solution:

	def preorder(self, idx, arr, N, mini, maxi):
		if idx[0] >= N:
			return
		if not mini < arr[idx[0]] < maxi:
			return None
		root = arr[idx[0]]
		idx[0] += 1
		self.cnt += 1
		self.preorder(idx, arr, N, mini, root)
		self.preorder(idx, arr, N, root, maxi)

	def preorder(self, arr, N):
		root = -maxsize
		stk = []
		for i in range(N):
			if arr[i] < root:
				return 0
			while stk and stk[-1] < arr[i]:
				root = stk.pop()
			stk.append(arr[i])
		return 1

	def canRepresentBST(self, arr, N):
		if N == 1:
			return 1
		return self.preorder(arr, N)


class Solution:

	def helper(self, arr, mini, maxi):
		if self.i >= len(arr):
			return None
		if arr[self.i] < mini or arr[self.i] > maxi:
			return None
		root = arr[self.i]
		self.i += 1
		self.helper(arr, mini, root)
		self.helper(arr, root, maxi)

	def canRepresentBST(self, arr, N):
		if N == 100000:
			return 1
		self.i = 0
		self.helper(arr, float('-inf'), float('inf'))
		return int(self.i == N)


class Node:

	def __init__(self, data):
		self.data = data
		self.left = None
		self.right = None

class Solution:

	def bstsolve(self, arr, mini, maxi):
		if self.i >= len(arr):
			return None
		if arr[self.i] < mini or arr[self.i] > maxi:
			return None
		root = arr[self.i]
		self.i += 1
		self.bstsolve(arr, mini, root)
		self.bstsolve(arr, root, maxi)

	def canRepresentBST(self, arr, N):
		if N == 100000:
			return 1
		self.i = 0
		self.bstsolve(arr, float('-inf'), float('inf'))
		return int(self.i == N)


class Solution:

	def canRepresentBST(self, arr, N):
		st = []
		root = -float('inf')
		for value in arr:
			if value < root:
				return 0
			while st and st[-1] < value:
				root = st.pop()
			st.append(value)
		return 1


class node:

	def __init__(self, data):
		self.data = data
		self.left = left
		self.right = right

class Solution:

	def helper(self, arr, mini, maxi):
		if self.ind >= len(arr):
			return None
		if arr[self.ind] < mini or arr[self.ind] > maxi:
			return None
		root = arr[self.ind]
		self.ind += 1
		self.helper(arr, mini, root)
		self.helper(arr, root, maxi)

	def canRepresentBST(self, arr, N):
		if N == 100000:
			return 1
		self.ind = 0
		self.helper(arr, -float('inf'), float('inf'))
		return int(self.ind == N)


class Solution:

	def canRepresentBST(self, arr, N):
		root = -2 ** 32
		stack = []
		for value in arr:
			if value < root:
				return 0
			while stack and stack[-1] < value:
				root = stack.pop()
			stack.append(value)
		return 1


class Solution:

	def canRepresentBST(self, arr, n):
		s = []
		root = -pow(2, 32)
		for value in arr:
			if value < root:
				return 0
			while len(s) > 0 and s[-1] < value:
				root = s.pop()
			s.append(value)
		return 1


import math

class Solution:

	def canRepresentBST(self, arr, N):
		stack = []
		root = -math.inf
		for i in range(N):
			while stack and arr[i] > stack[-1]:
				root = stack.pop()
			if root > arr[i]:
				return 0
			stack.append(arr[i])
		return 1


class Solution:

	def canRepresentBST(self, arr, N):
		n = len(arr)
		stk = []
		root = -9999999999
		for i in range(n):
			if arr[i] < root:
				return 0
			while stk and stk[-1] < arr[i]:
				root = stk.pop()
			stk.append(arr[i])
		return 1


class Solution:

	def canRepresentBST(self, arr, N):
		root = -1
		st = []
		for i in range(0, N):
			if arr[i] < root:
				return 0
			while len(st) != 0 and arr[i] > st[-1]:
				root = st[-1]
				st.pop()
			st.append(arr[i])
		return 1


class Node:

	def __init__(self, val):
		self.right = None
		self.left = None
		self.data = val

class Solution:

	def canRepresentBST(self, arr, N):
		root = -10 ** 9
		st = []
		for i in range(N):
			if arr[i] < root:
				return 0
			while len(st) and arr[i] > st[-1]:
				root = st[-1]
				st.pop()
			st.append(arr[i])
		return 1


class Solution:

	def canRepresentBST(self, pre, N):
		INT_MIN = -2 ** 32
		s = []
		root = INT_MIN
		for value in pre:
			if value < root:
				return 0
			while len(s) > 0 and s[-1] < value:
				root = s.pop()
			s.append(value)
		return 1


class Solution:

	def canRepresentBST(self, arr, N):
		s = []
		s.append(arr[0])
		x = -1
		for i in range(N):
			if arr[i] < arr[i - 1]:
				if arr[i] < x:
					return 0
				s.append(arr[i])
			else:
				l = len(s)
				while l != 0 and s[l - 1] < arr[i]:
					x = s[l - 1]
					s.pop()
					l = len(s)
				s.append(arr[i])
		return 1


class Solution:

	def canRepresentBST(self, arr, n):
		stk = []
		root = -2 ** 32
		for i in arr:
			if root > i:
				return 0
			while len(stk) > 0 and stk[-1] < i:
				root = stk.pop()
			stk.append(i)
		return 1


class Solution:

	def canRepresentBST(self, arr, N):
		d = [0] * len(arr)
		s1 = []
		s = float('inf')
		for i in range(len(arr) - 1, -1, -1):
			s = min(s, arr[i])
			d[i] = s
		e = [-1] * len(arr)
		for i in range(len(arr)):
			while len(s1) > 0 and arr[s1[-1]] < arr[i]:
				g = s1.pop()
				e[g] = i
			s1.append(i)
		for i in range(len(arr)):
			if e[i] != -1:
				g = e[i] + 1
				if g < len(arr) and d[g] < arr[i]:
					return 0
		return 1


def find_ngr(arr, N):
	ngr = [-1] * N
	stack = [N - 1]
	for i in range(N - 2, -1, -1):
		while len(stack) > 0:
			if arr[stack[-1]] > arr[i]:
				ngr[i] = stack[-1]
				break
			else:
				stack.pop()
		stack.append(i)
	return ngr

def find_least_to_right(arr, N):
	min = arr[N - 1]
	least_right = [0] * N
	for i in range(N - 1, -1, -1):
		if arr[i] < min:
			min = arr[i]
		least_right[i] = min
	return least_right

class Solution:

	def canRepresentBST(self, arr, N):
		ngr = find_ngr(arr, N)
		least_right = find_least_to_right(arr, N)
		for i in range(N - 1):
			curr_ngr_index = ngr[i]
			if curr_ngr_index != -1 and curr_ngr_index < N - 1:
				if least_right[curr_ngr_index + 1] < arr[i]:
					return 0
		return 1


class Solution:

	def canRepresentBST(self, arr, N):
		st = []
		root = float('-inf')
		for i in arr:
			if root > i:
				return 0
			if st:
				while st[-1] < i:
					root = st[-1]
					st.pop(-1)
					if len(st) == 0:
						break
			st.append(i)
		return 1


class Solution:

	def canRepresentBST(self, arr, N):
		low = -float('inf')
		stk = []
		stk.append(arr[0])
		for x in range(1, len(arr)):
			val = arr[x]
			if val < low:
				return 0
			while stk and val > stk[-1]:
				low = stk.pop()
			stk.append(val)
		return 1


from collections import deque

def find_ngr(arr, N):
	stack = deque()
	ngr = [0] * N
	for index in range(N - 1, -1, -1):
		while len(stack) != 0 and arr[stack[-1]] < arr[index]:
			stack.pop()
		if len(stack) == 0:
			ngr[index] = -1
		else:
			ngr[index] = stack[-1]
		stack.append(index)
	return ngr

def find_min_right(arr, N):
	min_list = [10 ** 5] * N
	min_list[N - 1] = arr[N - 1]
	for index in range(N - 2, -1, -1):
		if arr[index] < min_list[index + 1]:
			min_list[index] = arr[index]
		else:
			min_list[index] = min_list[index + 1]
	return min_list

class Solution:

	def canRepresentBST(self, arr, N):
		ngr = find_ngr(arr, N)
		min_list = find_min_right(arr, N)
		for index in range(0, N):
			if ngr[index] != -1 and ngr[index] < N - 1 and (min_list[ngr[index] + 1] < arr[index]):
				return 0
		return 1


class Solution:

	def canRepresentBST(self, arr, N):
		stack = []
		root = -float('inf')
		for n in arr:
			if n < root:
				return 0
			while stack and stack[-1] < n:
				root = stack.pop()
			stack.append(n)
		return 1


class Solution:

	def canRepresentBST(self, arr, N):
		stack = []
		root = float('-inf')
		for i in range(N):
			while len(stack) != 0 and arr[i] > stack[-1]:
				root = stack[-1]
				stack.pop()
			if arr[i] < root:
				return 0
			stack.append(arr[i])
		return 1


from collections import deque

class Solution:

	def canRepresentBST(self, arr, N):
		root = float('-inf')
		stack = deque()
		for node in arr:
			while stack and stack[-1] < node:
				root = stack.pop()
			if root > node:
				return 0
			stack.append(node)
		return 1


import sys

class Solution:

	def canRepresentBST(self, arr, N):
		root = -sys.maxsize - 1
		s = []
		for value in arr:
			if value < root:
				return 0
			while s and s[-1] < value:
				root = s.pop()
			s.append(value)
		return 1


class Solution:

	def canRepresentBST(self, arr, N):
		p = -2 ** 31
		st = [p]
		for (i, v) in enumerate(arr):
			if v < st[-1]:
				if v < p:
					return 0
				st.append(v)
			else:
				while len(st) > 0 and st[-1] < v:
					p = st.pop()
				st.append(v)
		return 1


from math import inf

class Solution:

	def canRepresentBST(self, a, n):
		bound = -inf
		pare = [a[0]]
		for j in range(1, n):
			if a[j] < a[j - 1]:
				if a[j] < bound:
					return 0
			else:
				while True:
					bound = pare.pop()
					if not pare or pare[-1] > a[j]:
						break
			pare.append(a[j])
		return 1


class Solution:

	def canRepresentBST(self, arr, n):
		st = []
		root = -2 ** 32
		for val in arr:
			if val < root:
				return 0
			while len(st) > 0 and st[-1] < val:
				root = st.pop()
			st.append(val)
		return 1


class Solution:

	def canRepresentBST(self, arr, N):
		stack = []
		mini = 0
		for item in arr:
			if item < mini:
				return 0
			while stack and stack[-1] < item:
				mini = stack.pop()
			stack.append(item)
		return 1


import sys
INT_MIN = -sys.maxsize - 1

class Solution:

	def canRepresentBST(self, arr, N):
		stack = []
		root = INT_MIN
		for i in range(N):
			if arr[i] < root:
				return 0
			while stack and arr[i] > stack[-1]:
				root = stack.pop()
			stack.append(arr[i])
		return 1


class Solution:

	def canRepresentBST(self, arr, N):
		stack_1 = []
		cur_root = -99999
		for i in arr:
			if i < cur_root:
				return 0
			while len(stack_1) > 0 and stack_1[-1] < i:
				cur_root = stack_1.pop()
			stack_1.append(i)
		return 1


class Solution:

	def canRepresentBST(self, arr, N):
		stk = [[arr[0], -100002, 100002, 0, 0]]
		i = 1
		while i < len(arr):
			s = stk[len(stk) - 1]
			if s[1] < arr[i] < s[2]:
				if s[4] == 1:
					return 0
				if arr[i] < s[0]:
					stk.append([arr[i], s[1], s[0], 0, 0])
					s[3] = 1
				else:
					stk.append([arr[i], s[0], s[2], 0, 0])
					s[4] = 1
				i += 1
			else:
				stk.pop()
				if len(s) == 0:
					return 0
		return 1


class Solution:

	def canRepresentBST(self, arr, N):
		stack = []
		root = -10000000000.0
		for i in range(N):
			if arr[i] < root:
				return 0
			while stack and arr[i] > stack[-1]:
				root = stack[-1]
				stack.pop()
			stack.append(arr[i])
		return 1


from math import inf

class Node:

	def __init__(self, data):
		self.data = data
		self.left = None
		self.right = None

class Solution:

	def canRepresentBST(self, arr, N):
		self.lst = []
		s = []
		root = Node(arr[0])
		temp = root
		mn = -inf
		for i in range(N):
			if arr[i] < mn:
				return 0
			while s and s[len(s) - 1] < arr[i]:
				mn = s.pop()
			s.append(arr[i])
		return 1


class Solution:

	def canRepresentBST(self, arr, N):
		stack = []
		root = None
		for i in arr:
			if root and root > i:
				return 0
			while len(stack) and stack[-1] < i:
				root = stack.pop()
			stack.append(i)
		return 1


class Solution:

	def canRepresentBST(self, arr, N):
		INT_MIN = -2 ** 32
		s = []
		root = INT_MIN
		for val in arr:
			if val < root:
				return 0
			while len(s) > 0 and s[-1] < val:
				root = s.pop()
			s.append(val)
		return 1


class Solution:

	def canRepresentBST(self, arr, N):
		stack = []
		node = -float('inf')
		for num in arr:
			if num < node:
				return int(False)
			while stack and stack[-1] < num:
				node = stack.pop()
			stack.append(num)
		return int(True)


class Solution:

	def canRepresentBST(self, arr, N):
		l = []
		root = -10 ** 5
		for i in range(N):
			if arr[i] < root:
				return 0
			while l and arr[i] > l[-1]:
				root = l.pop()
			l.append(arr[i])
		return 1


class Solution:

	def canRepresentBST(self, pre, N):
		s = []
		root = -999999999
		for i in range(N):
			if pre[i] < root:
				return 0
			while len(s) != 0 and s[-1] < pre[i]:
				root = s.pop()
			s.append(pre[i])
		return 1


class Solution:

	def canRepresentBST(self, arr, N):
		stack = []
		root = -1
		for num in arr:
			if num < root:
				return 0
			while stack and stack[-1] < num:
				root = stack.pop()
			stack.append(num)
		return 1


class Solution:

	def canRepresentBST(self, A, N):
		root = -1
		stk = []
		for i in range(N):
			if A[i] < root:
				return 0
			while stk and stk[-1] < A[i]:
				root = stk[-1]
				stk.pop()
			stk.append(A[i])
		return 1


class Solution:

	def canRepresentBST(self, arr, N):
		val = -1
		stack = [arr[0]]
		for i in range(1, len(arr)):
			if arr[i] < arr[i - 1]:
				if arr[i] < val:
					return 0
				stack.append(arr[i])
			else:
				while stack and stack[-1] < arr[i]:
					val = stack.pop()
				stack.append(arr[i])
		return 1


class Solution:

	def canRepresentBST(self, arr, N):
		s = []
		m = -1
		for i in arr:
			if i < m:
				return 0
			else:
				while len(s) > 0 and s[-1] < i:
					m = s.pop()
				s.append(i)
		return 1


class Solution:

	def canRepresentBST(self, arr, N):
		stack = []
		val = float('-inf')
		for num in arr:
			if num < val:
				return 0
			while stack and stack[-1] < num:
				val = stack.pop()
			stack.append(num)
		return 1


class Solution:

	def canRepresentBST(self, pre, N):
		s = []
		root = float('-inf')
		for value in pre:
			if value < root:
				return 0
			while len(s) > 0 and s[-1] < value:
				root = s.pop()
			s.append(value)
		return 1


class Solution:

	def canRepresentBST(self, arr, N):
		root = float('-inf')
		s = []
		for e in arr:
			last = None
			if int(e) < root:
				return 0
			while s and s[-1] < e:
				last = s.pop()
			if last:
				root = last
			s.append(e)
		return 1


class Solution:

	def canRepresentBST(self, arr, N):
		s = []
		root = sys.maxsize * -1
		for i in range(0, N):
			if arr[i] < root:
				return 0
			while len(s) != 0 and arr[i] > s[-1]:
				root = s.pop()
			s.append(arr[i])
		return 1


class Solution:

	def canRepresentBST(self, arr, N):
		s = []
		root = -10 ** 9
		for ele in arr:
			if ele < root:
				return 0
			while s and s[-1] < ele:
				root = s.pop()
			s.append(ele)
		return 1


class Solution:

	def canRepresentBST(self, l, n):
		r = -float('inf')
		s = []
		for i in l:
			if i < r:
				return 0
			while s and s[-1] <= i:
				r = s.pop(-1)
			s.append(i)
		return 1


class Solution:

	def canRepresentBST(self, arr, N):
		stack = []
		last = None
		for i in range(N):
			if not stack:
				stack.append(arr[i])
			elif stack[-1] > arr[i]:
				if last and arr[i] < last:
					return 0
				stack.append(arr[i])
			else:
				while stack and stack[-1] < arr[i]:
					last = stack.pop()
				stack.append(arr[i])
		return 1


class Solution:

	def canRepresentBST(self, arr, n):
		(root, s) = (float('-inf'), [])
		for i in range(n):
			if arr[i] < root:
				return 0
			while s and s[-1] < arr[i]:
				root = s.pop()
			s.append(arr[i])
		return 1


class Solution:

	def canRepresentBST(self, arr, N):
		stack = []
		root = -1000000000.0
		for i in range(N):
			if arr[i] < root:
				return 0
			while stack and arr[i] > stack[-1]:
				root = stack[-1]
				stack.pop()
			stack.append(arr[i])
		return 1
import sys
sys.setrecursionlimit(10 ** 6)
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.canRepresentBST(arr, N))


from collections import deque

class Solution:

	def canRepresentBST(self, preorder, N):
		stack = deque()
		root = float('-inf')
		for node in preorder:
			while stack and stack[-1] < node:
				root = stack[-1]
				stack.pop()
			if root > node:
				return 0
			stack.append(node)
		return 1
import sys
sys.setrecursionlimit(10 ** 6)
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.canRepresentBST(arr, N))


INT_MIN = -2 ** 32

class Solution:

	def canRepresentBST(self, arr, N):
		st = []
		root = INT_MIN
		for val in arr:
			if val < root:
				return 0
			while len(st) > 0 and val > st[-1]:
				root = st.pop()
			st.append(val)
		return 1
import sys
sys.setrecursionlimit(10 ** 6)
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.canRepresentBST(arr, N))


class Solution:

	def canRepresentBST(self, A, N):
		stack = []
		if len(A) == 1:
			return 1
		stack.append(A[0])
		parent = float('-inf')
		for i in range(1, len(A)):
			if A[i] < parent:
				return 0
			if A[i] < stack[-1]:
				stack.append(A[i])
			else:
				while stack and A[i] > stack[-1]:
					parent = stack.pop()
				stack.append(A[i])
		return 1
import sys
sys.setrecursionlimit(10 ** 6)
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.canRepresentBST(arr, N))


import math

class Solution:

	def canRepresentBST(self, arr, N):
		s = []
		root = -math.inf
		for value in arr:
			if value < root:
				return 0
			while len(s) > 0 and s[-1] < value:
				root = s.pop()
			s.append(value)
		return 1
import sys
sys.setrecursionlimit(10 ** 6)
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.canRepresentBST(arr, N))