You are given an array of size N having no duplicate elements. The array can be categorized into the following:
1.  Ascending
2.  Descending
3.  Descending Rotated
4.  Ascending Rotated
Your task is to return which type of array it is and the maximum element of that array.
 
Example 1:
Input :
N = 5 
A[] = { 2, 1, 5, 4, 3}
Output :
5 3
Explanation:
Descending rotated with maximum
element 5 
Example 2:
Input :
N = 5
A[] = { 3, 4, 5, 1, 2}
Output : 
5 4
Explanation:
Ascending rotated with maximum element 5 
 
Your Task:  
You don't need to read input or print anything. Your task is to complete the function maxNtype() which takes the array A[] and its size N as inputs and returns the largest element in the array and and integer x denoting the type of the array.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Constraints:
3 <= N <= 10^{5}
1 <= A[] <= 10^{12}

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Starter code: #User function Template for python3

class Solution:
    def maxNtype(self , arr, n):
        #code here.
    
    


Solutions:
class Solution:

	def maxNtype(self, arr, n):
		f = arr[0]
		l = arr[-1]
		type = 1
		if arr == sorted(arr):
			type = 1
		elif arr == sorted(arr, reverse=True):
			type = 2
		elif l > f:
			type = 3
		elif l < f:
			type = 4
		return [type, max(arr)]


class Solution:

	def maxNtype(self, arr, n):
		maxs = max(arr)
		if sorted(arr) == arr:
			return (1, maxs)
		elif sorted(arr)[::-1] == arr:
			return (2, maxs)
		neg = 0
		pos = 0
		for i in range(1, n):
			if arr[i] - arr[i - 1] < 0:
				neg += 1
			else:
				pos += 1
		return (3, maxs) if neg > pos else (4, maxs)


class Solution:

	def maxNtype(self, arr, n):
		result = []
		maximum = arr[0]
		minimum = arr[0]
		for i in range(n):
			if arr[i] > maximum:
				maximum = arr[i]
			if arr[i] < minimum:
				minimum = arr[i]
		if arr[0] == minimum and arr[n - 1] == maximum:
			type = 1
		elif arr[0] == maximum and arr[n - 1] == minimum:
			type = 2
		elif arr[0] < arr[n - 1]:
			type = 3
		else:
			type = 4
		result.append(type)
		result.append(maximum)
		return result


class Solution:

	def maxNtype(self, arr, n):
		a = arr[0]
		b = arr[-1]
		if arr == sorted(arr):
			type = 1
		elif arr == sorted(arr, reverse=True):
			type = 2
		elif a < b:
			type = 3
		else:
			type = 4
		return (type, max(arr))


class Solution:

	def maxNtype(self, arr, n):
		a = arr.copy()
		b = arr.copy()
		b.sort(reverse=True)
		arr.sort()
		if a == arr:
			return (1, max(a))
		elif a == b:
			return (2, max(a))
		elif a[0] > a[n - 1]:
			return (4, max(a))
		else:
			return (3, max(a))


class Solution:

	def maxNtype(self, arr, n):
		m = max(arr)
		if arr == sorted(arr):
			return [1, m]
		elif arr == sorted(arr, reverse=True):
			return [2, m]
		elif arr[0] > arr[-1]:
			return [4, m]
		elif arr[0] < arr[-1]:
			return [3, m]


class Solution:

	def maxNtype(self, arr, n):
		j = []
		r = []
		j[:] = arr[:]
		r[:] = arr[:]
		r.sort()
		r.reverse()
		j.sort()
		m = max(arr)
		mn = min(arr)
		h = j[-2]
		c = 0
		if arr == r and c == 0:
			return (2, m)
		elif arr == j and c == 0:
			return (1, m)
		for i in range(n):
			if arr[i] == m and arr[(i + 2) % n - 1] == h:
				c = 'DR'
				break
			elif arr[i] == m and arr[(i + 2) % n - 1] == mn:
				c = 'AR'
				break
		if arr == j and c == 0:
			return (1, m)
		elif c == 'DR':
			return (3, m)
		elif c == 'AR':
			return (4, m)


class Solution:

	def maxNtype(self, arr, n):
		min1 = arr[0]
		mini = 0
		max1 = arr[0]
		max1 = 0
		for i in range(0, n):
			if arr[i] < min1:
				min1 = arr[i]
				mini = i
			elif arr[i] > max1:
				max1 = arr[i]
				maxi = i
		if min1 == arr[0] and max1 == arr[n - 1]:
			return (1, max1)
		elif min1 == arr[n - 1] and max1 == arr[0]:
			return (2, max1)
		elif mini > maxi:
			return (4, max1)
		elif maxi > mini:
			return (3, max1)


class Solution:

	def maxNtype(self, arr, n):
		arr2 = arr.copy()
		arr2.sort()
		maximum = max(arr)
		minimum = min(arr)
		if arr == arr2:
			return (1, maximum)
		elif arr == arr2[::-1]:
			return (2, maximum)
		elif arr.index(maximum) > arr.index(minimum):
			return (3, maximum)
		else:
			return (4, maximum)
		arr2 = arr.copy()
		arr2.sort()
		maximum = max(arr)
		minimum = min(arr)
		if arr == arr2:
			return (1, maximum)
		elif arr == arr2[::-1]:
			return (2, maximum)
		elif arr.index(maximum) > arr.index(minimum):
			return (3, maximum)
		else:
			return (4, maximum)


class Solution:

	def maxNtype(self, arr, n):
		arr_max = max(arr)
		if arr == sorted(arr):
			return (1, arr_max)
		if arr == sorted(arr)[::-1]:
			return (2, arr_max)
		diff = [arr[i + 1] - arr[i] for i in range(n - 1)]
		ng = sum((1 for x in diff if x < 0))
		po = len(diff) - ng
		if ng > po:
			return (3, arr_max)
		else:
			return (4, arr_max)


class Solution:

	def maxNtype(self, arr, n):
		max_num = max(arr)
		ind = arr.index(max_num)
		if 0 < ind < n - 1:
			return [3, max_num] if arr[ind - 1] < arr[ind + 1] else [4, max_num]
		elif ind == 0:
			return [2, max_num] if arr[1] > arr[-1] else [4, max_num]
		else:
			return [1, max_num] if arr[1] > arr[0] else [3, max_num]


class Solution:

	def maxNtype(self, arr, n):
		list_return = [max(arr)]
		arr_str = ''.join((str(i) for i in arr))
		list1 = arr[0:n - 3]
		list1 += arr[n - 3:]
		list1.sort()
		list1_str = ''.join((str(i) for i in list1))
		list2_str = list1_str + list1_str
		list1.reverse()
		list3_str = ''.join((str(i) for i in list1))
		list4_str = list3_str + list3_str
		if arr_str == list1_str:
			list_return.append(1)
		elif arr_str in list2_str:
			list_return.append(4)
		elif arr_str == list3_str:
			list_return.append(2)
		elif arr_str in list4_str:
			list_return.append(3)
		list_return.reverse()
		return list_return


class Solution:

	def maxNtype(self, arr, n):
		s = max(arr)
		l = 0
		a = sorted(arr)
		if a == arr:
			l = 1
		elif a[::-1] == arr:
			l = 2
		elif arr[-1] > arr[0]:
			l = 3
		else:
			l = 4
		return [l, s]


class Solution:

	def maxNtype(self, arr, n):
		res = []
		mx = max(arr)
		mi = min(arr)
		type = 1
		if arr[0] == mi and arr[n - 1] == mx:
			type = 1
		elif arr[0] == mx and arr[n - 1] == mi:
			type = 2
		elif arr[0] < arr[n - 1]:
			type = 3
		elif arr[0] > arr[n - 1]:
			type = 4
		return [type, max(arr)]


class Solution:

	def maxNtype(self, arr, n):
		first = arr[0]
		last = arr[-1]
		type_ = 1
		if arr == sorted(arr):
			type_ = 1
		elif arr == sorted(arr, reverse=True):
			type_ = 2
		elif last > first:
			type_ = 3
		elif last < first:
			type_ = 4
		return [type_, max(arr)]


class Solution:

	def maxNtype(self, arr, n):
		high = max(arr)
		if arr == sorted(arr):
			return (1, high)
		if arr == sorted(arr)[::-1]:
			return (2, high)
		temp = [arr[ind + 1] - arr[ind] for ind in range(n - 1)]
		neg = sum((1 for num in temp if num < 0))
		pos = len(temp) - neg
		if neg > pos:
			return (3, high)
		else:
			return (4, high)


class Solution:

	def maxNtype(self, arr, n):
		maxarr = max(arr)
		if arr == sorted(arr):
			return (1, maxarr)
		if arr == sorted(arr)[::-1]:
			return (2, maxarr)
		diff = [arr[i + 1] - arr[i] for i in range(n - 1)]
		a = sum((1 for i in diff if i < 0))
		b = len(diff) - a
		if a > b:
			return (3, maxarr)
		else:
			return (4, maxarr)


class Solution:

	def maxNtype(self, arr, n):
		maximum = -1
		minimum = 10 ** 12 + 1
		index_max = -1
		index_min = -1
		ans = -1
		for i in range(n):
			if arr[i] > maximum:
				maximum = arr[i]
				index_max = i
			if arr[i] < minimum:
				minimum = arr[i]
				index_min = i
		if index_max == n - 1 and index_min == 0:
			ans = 1
		elif index_max == 0 and index_min == n - 1:
			ans = 2
		elif index_max > index_min:
			ans = 3
		elif index_max < index_min:
			ans = 4
		return (ans, maximum)


class Solution:

	def maxNtype(self, arr, n):
		mx = max(arr)
		x1 = 1
		x2 = 1
		for i in range(n - 1):
			if arr[i] < arr[i + 1]:
				x1 += 1
		if x1 == n:
			return (1, mx)
		elif x1 > 2:
			return (4, mx)
		for i in range(n - 1):
			if arr[i] > arr[i + 1]:
				x2 += 1
		if x2 == n:
			return (2, mx)
		elif x2 > 2:
			return (3, mx)


class Solution:

	def maxNtype(self, arr, n):
		if arr[-1] == max(arr) and arr[0] == min(arr):
			return (1, max(arr))
		elif arr[0] == max(arr) and arr[-1] == min(arr):
			return (2, max(arr))
		elif arr.index(min(arr)) < arr.index(max(arr)):
			return (3, max(arr))
		else:
			return (4, max(arr))


class Solution:

	def maxNtype(self, arr, n):
		maximum = -1
		i = 0
		while i < n - 1 and arr[i] <= arr[i + 1]:
			i += 1
		if i == n - 1:
			maximum = arr[n - 1]
			return (1, maximum)
		if i == 0:
			while i < n - 1 and arr[i] >= arr[i + 1]:
				i += 1
			if i == n - 1:
				maximum = arr[0]
				return (2, maximum)
			if arr[0] < arr[i + 1]:
				maximum = max(arr[0], arr[i + 1])
				return (3, maximum)
		if arr[0] > arr[i + 1]:
			maximum = max(arr[0], arr[i])
			return (4, maximum)
		maximum = max(arr[0], arr[i])
		return (3, maximum)


class Solution:

	def maxNtype(self, arr, n):
		max_e = max(arr)
		min_e = min(arr)
		if arr[0] == min_e and arr[n - 1] == max_e:
			return [1, max_e]
		elif arr[0] == max_e and arr[n - 1] == min_e:
			return [2, max_e]
		elif arr[0] < arr[n - 1]:
			return [3, max_e]
		elif arr[0] > arr[n - 1]:
			return [4, max_e]


class Solution:

	def maxNtype(self, arr, n):
		asc_rot = arr[0]
		des_rot = arr[-1]
		type = 1
		if arr == sorted(arr):
			type = 1
		elif arr == sorted(arr, reverse=True):
			type = 2
		elif asc_rot < des_rot:
			type = 3
		elif asc_rot > des_rot:
			type = 4
		return [type, max(arr)]


class Solution:

	def maxNtype(self, arr, n):
		asc_cnt = 0
		desc_cnt = 0
		max_val = 0
		for i in range(n - 1):
			if arr[i + 1] > arr[i]:
				asc_cnt += 1
			else:
				desc_cnt += 1
			max_val = max(max_val, arr[i])
		order = 0
		if asc_cnt == n - 1:
			order = 1
		elif desc_cnt == n - 1:
			order = 2
		elif asc_cnt > desc_cnt:
			order = 4
		else:
			order = 3
		return (order, max(max_val, arr[n - 1]))


class Solution:

	def maxNtype(self, arr, n):
		asc_count = 0
		desc_count = 0
		largest = 0
		for i in range(n - 1):
			if arr[i + 1] > arr[i]:
				asc_count += 1
			else:
				desc_count += 1
			largest = max(largest, arr[i])
		order = 2
		if asc_count == n - 1:
			order = 1
		elif asc_count >= desc_count:
			order = 4
		elif desc_count > asc_count and desc_count < n - 1:
			order = 3
		return [order, max(largest, arr[n - 1])]


class Solution:

	def maxNtype(self, arr, n):
		ascending = 'Ascending'
		descending = 'Descending'
		max_element = max(arr)
		total = []
		ascending_count = 0
		descending_count = 0
		for i in range(n - 1):
			if arr[i] - arr[i + 1] > 0:
				total.append(descending)
				descending_count += 1
			else:
				total.append(ascending)
				ascending_count += 1
		if ascending in total and descending in total:
			if ascending_count > descending_count:
				return (4, max_element)
			else:
				return (3, max_element)
		elif ascending in total and descending not in total:
			return (1, max_element)
		else:
			return (2, max_element)


class Solution:

	def maxNtype(self, arr, n):
		min1 = min(arr)
		max1 = max(arr)
		firMin = None
		lastMin = None
		firMax = None
		lastMax = None
		i = 0
		while i < n:
			if arr[i] == min1:
				firMin = i
				break
			i += 1
		j = 0
		while j < n:
			if arr[j] == max1:
				firMax = j
				break
			j += 1
		k = n - 1
		while k >= 0:
			if arr[k] == min1:
				lastMin = k
				break
			k -= 1
		l = n - 1
		while l >= 0:
			if arr[l] == max1:
				lastMax = l
				break
			l -= 1
		if firMin == 0 and lastMax == n - 1:
			return [1, max1]
		elif lastMin == n - 1 and firMax == 0:
			return [2, max1]
		elif firMin == lastMax + 1:
			return [4, max1]
		else:
			return [3, max1]


class Solution:

	def maxNtype(self, arr, n):
		l = arr[0]
		r = arr[-1]
		x = 1
		if arr == sorted(arr):
			x = 1
		elif arr == sorted(arr, reverse=True):
			x = 2
		elif r > l:
			x = 3
		else:
			x = 4
		return [x, max(arr)]


class Solution:

	def maxNtype(self, arr, n):
		mini = min(arr)
		maxi = max(arr)
		if mini == arr[0] and maxi == arr[n - 1]:
			return [1, maxi]
		elif maxi == arr[0] and mini == arr[n - 1]:
			return [2, maxi]
		elif arr[0] > arr[n - 1]:
			return [4, maxi]
		elif arr[0] < arr[n - 1]:
			return [3, maxi]


class Solution:

	def maxNtype(self, arr, n):
		max = arr[0]
		min = arr[0]
		for i in range(n):
			if max < arr[i]:
				max = arr[i]
			if min > arr[i]:
				min = arr[i]
		if min == arr[0] and max == arr[n - 1]:
			return (1, max)
		if max == arr[0] and min == arr[n - 1]:
			return (2, max)
		if arr[0] < arr[n - 1]:
			return (3, max)
		if arr[0] > arr[n - 1]:
			return (4, max)


class Solution:

	def maxNtype(self, arr, n):
		f = arr[0]
		l = arr[-1]
		maxi = max(arr)
		ans = []
		l1 = []
		l1[:] = arr[:]
		if sorted(l1) == arr:
			ans = [1, maxi]
		elif sorted(l1, reverse=True) == arr:
			ans = [2, maxi]
		elif l > f:
			ans = [3, maxi]
		elif l < f:
			ans = [4, maxi]
		return ans


class Solution:

	def maxNtype(self, arr, n):
		min_item = float('inf')
		max_item = 0
		for item in arr:
			if item < min_item:
				min_item = item
			if item > max_item:
				max_item = item
		if arr[0] == min_item and arr[-1] == max_item:
			return [1, max_item]
		if arr[0] == max_item and arr[-1] == min_item:
			return [2, max_item]
		if arr[0] == min_item and arr[1] == max_item:
			return [3, max_item]
		if arr[0] == max_item and arr[1] == min_item:
			return [4, max_item]
		if arr[0] > arr[1]:
			return [3, max_item]
		if arr[0] < arr[1]:
			return [4, max_item]


class Solution:

	def maxNtype(self, arr, n):
		k = arr[:]
		k.sort()
		(x, z) = (k[0], max(arr))
		if k == arr:
			return (1, z)
		elif k[::-1] == arr:
			return (2, z)
		elif arr.index(x) < arr.index(z):
			return (3, z)
		else:
			return (4, z)


class Solution:

	def maxNtype(self, arr, n):
		count1 = 0
		count2 = 0
		arr1 = sorted(arr)
		if arr == arr1:
			return (1, max(arr))
		elif arr == sorted(arr, reverse=True):
			return (2, max(arr))
		else:
			for i in range(n - 1):
				if arr[i] > arr[i + 1]:
					count1 += 1
				else:
					count2 += 1
			if count1 > count2:
				return (3, max(arr))
			else:
				return (4, max(arr))


class Solution:

	def maxNtype(self, arr, n):
		(min_index, max_index) = (0, 0)
		for i in range(n):
			if arr[i] > arr[max_index]:
				max_index = i
			if arr[i] < arr[min_index]:
				min_index = i
		if min_index == 0 and max_index == n - 1:
			return (1, arr[max_index])
		elif min_index == n - 1 and max_index == 0:
			return (2, arr[max_index])
		elif min_index < max_index:
			return (3, arr[max_index])
		else:
			return (4, arr[max_index])


class Solution:

	def maxNtype(self, arr, n):
		max1 = arr[0]
		min1 = arr[0]
		for i in range(n):
			max1 = max(max1, arr[i])
			min1 = min(min1, arr[i])
		if max1 == arr[0] and min1 == arr[n - 1]:
			return (2, max1)
		elif min1 == arr[0] and max1 == arr[n - 1]:
			return (1, max1)
		elif arr[0] < arr[n - 1]:
			return (3, max1)
		else:
			return (4, max1)