Given an array arr[ ] of size n such that elements of arr[ ] in range [0, 1, ..n-1]. Our task is to divide the array into the maximum number of partitions that can be sorted individually, then concatenated to make the whole array sorted. 
Example 1:
Ã¢â¬â¹Input : arr[ ] = {2, 1, 0, 3}
Output : 2
Explanation:
If divide arr[] into two partitions 
{2, 1, 0} and {3}, sort then and concatenate 
then, we get the whole array sorted.
Ã¢â¬â¹Example 2:
Input : arr[ ] = {2, 1, 0, 3, 4, 5} 
Output :  4 
 
Your Task:
This is a function problem. The input is already taken care of by the driver code. You only need to complete the function maxPartitions() that takes an array (arr), sizeOfArray (n), and return the maximum number of partitions. The driver code takes care of the printing.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
Constraints:
1 ≤ T ≤ 100
1 ≤ N ≤ 10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: Sorting

Data structures

Starter code: #User function Template for python3





def maxPartitions (arr, n) : 

    #Complete the function



Solutions:
def maxPartitions(arr, n):
	a = arr[0]
	c = 0
	for i in range(n):
		if a < arr[i]:
			a = arr[i]
		if a == i:
			c += 1
	return c


def maxPartitions(arr, n):
	maxi = 0
	count = 0
	for (i, item) in enumerate(arr):
		maxi = max(maxi, item)
		count += maxi == i
	return count


def maxPartitions(arr, n):
	index = [0]
	cnt = 0
	while True:
		if arr[index[0]] == index[0]:
			cnt += 1
			index[0] += 1
		else:
			max_index = arr[index[0]]
			while index[0] <= max_index:
				if arr[index[0]] > max_index:
					max_index = arr[index[0]]
				index[0] += 1
				if index[0] == len(arr):
					break
			cnt += 1
		if index[0] == len(arr):
			break
	return cnt


def maxPartitions(arr, n):
	ans = 0
	max_so_far = 0
	for i in range(0, n):
		max_so_far = max(max_so_far, arr[i])
		if max_so_far == i:
			ans += 1
	return ans


def maxPartitions(arr, n):
	count = 0
	maxi = arr[0]
	for i in range(n):
		if arr[i] > maxi:
			maxi = arr[i]
		if maxi == i:
			count += 1
	return count


def maxPartitions(arr, n):
	temp = [i for i in range(n)]
	i = 0
	cnt = 0
	cursum = 0
	orgsum = 0
	while i < n:
		orgsum += i
		cursum += arr[i]
		if orgsum == cursum:
			cnt += 1
		i += 1
	return cnt


def maxPartitions(arr, n):
	(cur, maxs) = (0, 0)
	for i in range(n):
		maxs = max(maxs, arr[i])
		if maxs == i:
			cur += 1
	return cur


def maxPartitions(arr, n):
	ans = 0
	maxm = float('-inf')
	for i in range(n):
		maxm = max(maxm, arr[i])
		if maxm == i:
			ans += 1
	return ans


def maxPartitions(arr, n):
	c = 0
	Min = [arr[0]]
	Max = [arr[-1]]
	for i in range(1, n):
		Min.append(max(Min[i - 1], arr[i]))
		Max.append(min(Max[i - 1], arr[n - i - 1]))
	Max.reverse()
	for i in range(n - 1):
		if Min[i] <= Max[i + 1]:
			c = c + 1
	return c + 1


def maxPartitions(arr, n):
	N = len(arr)
	leftMax = []
	rightMin = []
	leftMax.append(arr[0])
	rightMin.append(arr[N - 1])
	for i in range(1, N):
		leftMax.append(max(leftMax[i - 1], arr[i]))
		rightMin.append(min(rightMin[i - 1], arr[N - i - 1]))
	rightMin.reverse()
	count = 0
	for i in range(0, N - 1):
		if leftMax[i] <= rightMin[i + 1]:
			count = count + 1
	return count + 1


def maxPartitions(arr, n):
	count = 0
	max_ele = 0
	for i in range(n):
		max_ele = max(max_ele, arr[i])
		if max_ele == i:
			count += 1
	return count


def maxPartitions(arr, n):
	l = []
	for i in range(n):
		l += [[arr[i], i]]
	l.sort()
	l1 = []
	for i in range(n):
		l1 += [[min(l[i][1], i), max(l[i][1], i)]]
	c = 0
	s = -1
	l1.sort()
	for i in range(n):
		if l1[i][0] > s:
			c += 1
		s = max(l1[i][1], s)
	return c


def maxPartitions(arr, n):
	n = len(arr)
	leftarr = []
	rightarr = []
	leftarr.append(arr[0])
	for i in range(1, n):
		leftarr.append(max(leftarr[i - 1], arr[i]))
	rightarr.append(arr[n - 1])
	for i in range(1, n):
		rightarr.append(min(rightarr[i - 1], arr[n - i - 1]))
	rightarr.reverse()
	count = 0
	for i in range(len(arr) - 1):
		if leftarr[i] <= rightarr[i + 1]:
			count += 1
	return count + 1
for _ in range(0, int(input())):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	ans = maxPartitions(arr, n)
	print(ans)


def maxPartitions(arr, n):
	c = 0
	a = arr[0]
	for i in range(n):
		if a < arr[i]:
			a = arr[i]
		if a == i:
			c += 1
	return c
for _ in range(0, int(input())):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	ans = maxPartitions(arr, n)
	print(ans)


def maxPartitions(arr, n):
	x = 0
	cur = None
	for i in range(n):
		if cur == None:
			x += 1
			cur = arr[i]
		elif cur < arr[i]:
			cur = arr[i]
		if i == cur:
			cur = None
	return x
	return x


def maxPartitions(arr, n):
	ind = arr[0]
	cnt = 0
	for i in range(n):
		if ind < arr[i]:
			ind = arr[i]
		if ind == i:
			cnt += 1
	return cnt


def maxPartitions(arr, n):
	max_in_partition = -1
	end_partition = 0
	ans = 0
	while end_partition < n:
		max_in_partition = max(max_in_partition, arr[end_partition])
		if max_in_partition == end_partition:
			ans += 1
			max_in_partition = -1
		end_partition += 1
	return ans


def maxPartitions(arr, n):
	maxi = 0
	chunks = 0
	for i in range(n):
		maxi = max(maxi, arr[i])
		if i == maxi or i == n - 1:
			chunks += 1
	return chunks