Given two integers N and M and a matrix of dimensions N*M. Count all the rows in a matrix that are sorted either in strictly increasing order or in strictly decreasing order.
Example 1:
Input:
N=3,M=3
Mat=[[1,2,3],[6,5,4],[7,9,8]]
Output:
2
Explanation:
The first row is sorted in strictly 
increasing order while the second row 
is sorted in strictly decreasing order.
Example 2:
Input:
N=3,M=3
Mat=[[1,2,3],[4,5,6],[7,8,9]]
Output:
3
Explanation:
All the rows are sorted in strictly 
increasing order.
Your Task:
You don't need to read input or print anything.Your task is to complete the function sortedCount() which takes the two integers N,M and the matrix Mat as input parameters and returns the number of rows which are sorted in either strictly increasing order or strictly decreasing order.
Expected Time Complexity:O(N*M)
Expected Auxillary Space:O(1)
 
Constraints:
1<=N,M,Mat[i][j]<=1000

Difficulty: EASY
Tags: Matrices

Data structures
Skill types: Data structures
Expected Time Complexity: O(N*M)
Expected Auxiliary Space: O(1)

Starter code:
#User function Template for python3



class Solution:

    def sortedCount(self,N,M,Mat):

        #code here

        

Solutions:
class Solution:

	def sortedCount(self, N, M, Mat):
		count = 0
		for i in range(N):
			inc = 0
			dec = 0
			for j in range(M - 1):
				if Mat[i][j] < Mat[i][j + 1]:
					inc += 1
				if Mat[i][j] > Mat[i][j + 1]:
					dec += 1
			if inc == M - 1 or dec == M - 1:
				count += 1
		return count


class Solution:

	def sortedCount(self, N, M, Mat):
		cnt = 0
		for x in range(N):
			flag = True
			curr = ''
			for y in range(M - 1):
				if Mat[x][y] > Mat[x][y + 1] and curr != 'inc':
					curr = 'dec'
				elif Mat[x][y] < Mat[x][y + 1] and curr != 'dec':
					curr = 'inc'
				else:
					flag = False
			if flag == True:
				cnt += 1
		return cnt


class Solution:

	def sortedCount(self, N, M, Mat):
		count = 0
		for i in Mat:
			m = sorted(list(set(i)))
			q = m[::-1]
			if i == m or i == q:
				count += 1
		return count


class Solution:

	def sortedCount(self, N, M, Mat):
		c = 0
		for i in Mat:
			a = 1
			b = 1
			for j in range(1, M):
				if i[j] < i[j - 1]:
					b += 1
				elif i[j] > i[j - 1]:
					a += 1
				else:
					continue
			if a == M or b == M:
				c += 1
		return c


class Solution:

	def sortedCount(self, N, M, Mat):
		count = 0
		for i in Mat:
			sd = 1
			se = 1
			for j in range(1, M):
				if i[j] < i[j - 1]:
					se += 1
				elif i[j] > i[j - 1]:
					sd += 1
				else:
					continue
			if sd == M or se == M:
				count += 1
		return count


class Solution:

	def sortedCount(self, N, M, mat):
		c = 0
		for i in range(N):
			for j in range(1, M):
				if mat[i][j] > mat[i][j - 1]:
					continue
				else:
					break
			else:
				c += 1
				continue
			for j in range(1, M):
				if mat[i][j] < mat[i][j - 1]:
					continue
				else:
					break
			else:
				c += 1
				continue
		return c


class Solution:

	def sortedCount(self, N, M, Mat):
		cnt = 0
		for j in range(len(Mat)):
			nt = 1
			temp = Mat[j][0]
			if len(Mat[j]) == 1:
				cnt += 1
				continue
			elif len(Mat[j]) == 2 and Mat[j][0] != Mat[j][1]:
				cnt += 1
				continue
			inc = 0
			if Mat[j][0] > Mat[j][1]:
				inc = 0
			else:
				inc = 1
			for i in range(len(Mat[j])):
				if inc == 0:
					if Mat[j][i] >= temp and i != 0:
						nt = 0
						break
				elif Mat[j][i] <= temp and i != 0:
					nt = 0
					break
				temp = Mat[j][i]
			if nt:
				cnt += 1
		return cnt


class Solution:

	def sortedCount(self, N, M, Mat):
		count = 0
		if M == 1:
			return N
		for i in range(N):
			is_sorted = self.func(Mat[i])
			if is_sorted:
				count += 1
		return count

	def func(self, arr):
		if arr[0] > arr[1]:
			decrease = True
			for i in range(len(arr) - 1):
				if arr[i] <= arr[i + 1]:
					decrease = False
					return decrease
			return decrease
		elif arr[0] < arr[1]:
			increase = True
			for i in range(len(arr) - 1):
				if arr[i] >= arr[i + 1]:
					increase = False
					return increase
			return increase


class Solution:

	def sortedCount(self, N, M, Mat):
		c = 0
		for i in range(N):
			if len(set(Mat[i])) == len(Mat[i]):
				if sorted(Mat[i]) == Mat[i] or sorted(Mat[i])[::-1] == Mat[i]:
					c += 1
		return c


class Solution:

	def sortedCount(self, N, M, Mat):
		c = 0
		for i in Mat:
			t = sorted(list(set(i)))
			if i == t or i == t[::-1]:
				c += 1
		return c


class Solution:

	def sortedCount(self, N, M, Mat):
		if M == 1:
			return N
		count = 0
		for row in Mat:
			count += all([row[i] < row[i + 1] for i in range(M - 1)])
			count += all([row[i] > row[i + 1] for i in range(M - 1)])
		return count


class Solution:

	def arrAsc(self, arr):
		n = len(arr)
		if n == 1 or n == 0:
			return True
		return arr[0] < arr[1] and self.arrAsc(arr[1:])

	def arrDsc(self, arr):
		n = len(arr)
		if n == 1 or n == 0:
			return True
		return arr[0] > arr[1] and self.arrDsc(arr[1:])

	def sortedCount(self, N, M, Mat):
		ans = 0
		for i in range(N):
			if self.arrAsc(Mat[i]) or self.arrDsc(Mat[i]):
				ans += 1
		return ans


class Solution:

	def sortedCount(self, N, M, Mat):
		if M == 1:
			return N
		res = 0
		for i in range(N):
			cnt = 0
			for j in range(1, M):
				if Mat[i][j] < Mat[i][j - 1]:
					cnt += 1
				elif Mat[i][j] > Mat[i][j - 1]:
					cnt -= 1
				if cnt == -1 * (M - 1) or cnt == M - 1:
					res += 1
		return res


class Solution:

	def sortedCount(self, N, M, Mat):
		count = 0
		for i in range(N):
			test_list = Mat[i]
			res1 = all((i < j for (i, j) in zip(test_list, test_list[1:])))
			res2 = all((i > j for (i, j) in zip(test_list, test_list[1:])))
			if res1 or res2:
				count += 1
		return count


class Solution:

	def sortedCount(self, N, M, Mat):
		count = 0
		for i in Mat:
			temp = i
			if len(set(i)) == M and (sorted(temp) == i or temp[::-1] == sorted(i)):
				count += 1
		return count


class Solution:

	def sortedCount(self, N, M, Mat):

		def call(lst):
			i = 0
			a = 0
			b = 0
			while i < len(lst) - 1:
				if a == 0 and b == 0:
					if lst[i] < lst[i + 1]:
						a = 1
						b = 0
					elif lst[i] > lst[i + 1]:
						a = 0
						b = 1
					else:
						return 0
				elif a == 1:
					if lst[i] > lst[i + 1] or lst[i] == lst[i + 1]:
						return 0
					else:
						i += 1
				elif b == 1:
					if lst[i] < lst[i + 1] or lst[i] == lst[i + 1]:
						return 0
					else:
						i += 1
			return 1
		count = 0
		for lst in Mat:
			if call(lst):
				count += 1
		return count


class Solution:

	def sortedCount(self, N, M, Mat):
		ac = dc = 1
		count = 0
		for i in range(N):
			for j in range(1, M):
				if Mat[i][j - 1] < Mat[i][j]:
					ac += 1
				elif Mat[i][j - 1] > Mat[i][j]:
					dc += 1
				else:
					break
			if dc == M or ac == M:
				count += 1
			dc = ac = 1
		return count


class Solution:

	def sortedCount(self, N, M, Mat):
		count = 0
		if M == 1:
			return N
		for i in range(N):
			for j in range(M - 1):
				if Mat[i][j] > Mat[i][j + 1]:
					if j + 2 == M:
						count += 1
				else:
					break
			for j in range(M - 1):
				if Mat[i][j] < Mat[i][j + 1]:
					if j + 2 == M:
						count += 1
				else:
					break
		return count


class Solution:

	def sortedCount(self, N, M, Mat):
		count = 0
		for row in Mat:
			des = int(self.checkDes(row))
			asc = int(self.checkAsc(row))
			if des or asc:
				count += 1
		return count

	def checkDes(self, arr):
		if len(arr) == 1:
			return True
		for i in range(len(arr) - 1):
			if arr[i] <= arr[i + 1]:
				return False
		return True

	def checkAsc(self, arr):
		if len(arr) == 1:
			return True
		for i in range(len(arr) - 1):
			if arr[i] >= arr[i + 1]:
				return False
		return True


from collections import Counter

class Solution:

	def isSorted(self, arr, n):
		if n == 1:
			return True
		if len(set(list(Counter(arr).values()))) == 1:
			if len(list(Counter(arr).keys())) == 1:
				return False
			elif arr == sorted(arr) or arr == sorted(arr, reverse=True):
				return True
		else:
			return False

	def sortedCount(self, N, M, Mat):
		cnt = 0
		for i in range(N):
			if self.isSorted(Mat[i], M):
				cnt += 1
		return cnt


class Solution:

	def sortedCount(self, N, M, arr):

		def dec(arr):
			for i in range(1, len(arr)):
				if arr[i] >= arr[i - 1]:
					return 0
			return 1

		def inc(arr):
			for i in range(1, len(arr)):
				if arr[i] <= arr[i - 1]:
					return 0
			return 1
		ans = 0
		for i in range(N):
			ans = ans + max(inc(arr[i]), dec(arr[i]))
		return ans
import math
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(N, M) = map(int, input().strip().split(' '))
		Mat = []
		for i in range(N):
			Mat.append(list(map(int, input().strip().split(' '))))
		ob = Solution()
		ans = ob.sortedCount(N, M, Mat)
		print(ans)


class Solution:

	def sortedCount(self, N, M, Mat):
		c = 0
		for i in Mat:
			if (i == sorted(i) or i == sorted(i, reverse=True)) and len(i) == len(set(i)):
				c = c + 1
		return c
import math
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(N, M) = map(int, input().strip().split(' '))
		Mat = []
		for i in range(N):
			Mat.append(list(map(int, input().strip().split(' '))))
		ob = Solution()
		ans = ob.sortedCount(N, M, Mat)
		print(ans)


class Solution:

	def sortedCount(self, N, M, Mat):
		count = 0
		for a in Mat:
			i = 1
			inc = 0
			dec = 0
			while i < M:
				if a[i - 1] < a[i]:
					inc += 1
				elif a[i - 1] > a[i]:
					dec += 1
				i += 1
			if inc == M - 1 or dec == M - 1:
				count += 1
		return count
import math
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(N, M) = map(int, input().strip().split(' '))
		Mat = []
		for i in range(N):
			Mat.append(list(map(int, input().strip().split(' '))))
		ob = Solution()
		ans = ob.sortedCount(N, M, Mat)
		print(ans)


class Solution:

	def sortedCount(self, N, M, arr):
		if M <= 1:
			return N
		c = 0
		for i in range(N):
			f = 0
			if arr[i][0] < arr[i][1]:
				for j in range(M - 1):
					if arr[i][j] >= arr[i][j + 1]:
						f = 1
						break
			else:
				for j in range(M - 1):
					if arr[i][j] <= arr[i][j + 1]:
						f = 1
						break
			if f == 0:
				c += 1
		return c
import math
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(N, M) = map(int, input().strip().split(' '))
		Mat = []
		for i in range(N):
			Mat.append(list(map(int, input().strip().split(' '))))
		ob = Solution()
		ans = ob.sortedCount(N, M, Mat)
		print(ans)


class Solution:

	def sortedCount(self, N, M, mat):
		c = 0
		for val in mat:
			count = 0
			i = 0
			if i < len(val) - 1 and val[i] < val[i + 1]:
				count = 0
				while i < len(val) - 1 and val[i] < val[i + 1]:
					count += 1
					i += 1
			elif i < len(val) - 1 and val[i] > val[i + 1]:
				count = 0
				while i < len(val) - 1 and val[i] > val[i + 1]:
					count += 1
					i += 1
			if count == len(val) - 1:
				c += 1
		return c
import math
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(N, M) = map(int, input().strip().split(' '))
		Mat = []
		for i in range(N):
			Mat.append(list(map(int, input().strip().split(' '))))
		ob = Solution()
		ans = ob.sortedCount(N, M, Mat)
		print(ans)


class Solution:

	def sortedCount(self, N, M, Mat):
		count = 0
		for i in range(N):
			a = Mat[i]
			if a == sorted(set(a)) or a == sorted(set(a))[::-1]:
				count += 1
		return count


class Solution:

	def sortedCount(self, N, M, Mat):
		count = 0
		for i in range(N):
			is_increasing = False
			is_decreasing = False
			for j in range(M - 1):
				if Mat[i][j] < Mat[i][j + 1]:
					is_increasing = True
				elif Mat[i][j] > Mat[i][j + 1]:
					is_decreasing = True
				else:
					is_increasing = True
					is_decreasing = True
			if M == 1:
				count += 1
			if is_increasing ^ is_decreasing:
				count += 1
		return count


class Solution:

	def sortedCount(self, N, M, Mat):
		count = 0
		for i in range(N):
			asc = 1
			desc = 1
			for j in range(M - 1):
				if Mat[i][j] >= Mat[i][j + 1]:
					asc = 0
					break
			for j in range(M - 1):
				if Mat[i][j] <= Mat[i][j + 1]:
					desc = 0
					break
			if asc == 1 or desc == 1:
				count += 1
		return count


class Solution:

	def sortedCount(self, N, M, Mat):
		ans = 0
		for i in range(N):
			isSorted = True
			for j in range(1, M):
				if Mat[i][j - 1] >= Mat[i][j]:
					isSorted = False
					break
			if isSorted:
				ans += 1
				continue
			isSorted = True
			for j in range(1, M):
				if Mat[i][j - 1] <= Mat[i][j]:
					isSorted = False
					break
			if isSorted:
				ans += 1
		return ans


class Solution:

	def sortedCount(self, N, M, Mat):
		c = 0
		for i in range(N):
			asc = False
			desc = False
			for j in range(M):
				if j == 0:
					ele = Mat[i][j]
				elif asc and Mat[i][j] <= Mat[i][j - 1]:
					asc = False
					break
				elif desc and Mat[i][j] >= Mat[i][j - 1]:
					desc = False
					break
				elif ele < Mat[i][j]:
					asc = True
				elif ele > Mat[i][j]:
					desc = True
				else:
					break
			if asc or desc or M == 1:
				c += 1
		return c


class Solution:

	def sortedCount(self, N, M, Mat):
		if M == 1:
			return N
		ans = 0
		for i in range(N):
			c = 0
			j = 0
			while j < M - 1 and Mat[i][j] < Mat[i][j + 1]:
				c += 1
				j += 1
			if c == 0:
				while j < M - 1 and Mat[i][j] > Mat[i][j + 1]:
					c += 1
					j += 1
			if c == M - 1:
				ans += 1
		return ans


class Solution:

	def sortedCount(self, N, M, Mat):
		ans = 0
		for i in range(0, N):
			sort = 0
			for j in range(0, M - 1):
				if Mat[i][j] > Mat[i][j + 1]:
					sort -= 1
				if Mat[i][j] < Mat[i][j + 1]:
					sort += 1
			if sort == M - 1 or sort == 1 - M:
				ans += 1
		return ans


class Solution:

	def sortedCount(self, N, M, x):
		ans = 0
		for i in range(N):
			s = 0
			for j in range(M - 1):
				if x[i][j] > x[i][j + 1]:
					s += 1
				if x[i][j] < x[i][j + 1]:
					s -= 1
			if s == M - 1 or s == 1 - M:
				ans += 1
		return ans


class Solution:

	def sortedCount(self, N, M, Mat):
		count = 0
		for i in range(N):
			ll = Mat[i].copy()
			lm = Mat[i].copy()
			ll.sort()
			lm = sorted(lm, reverse=True)
			if (ll == Mat[i] or lm == Mat[i]) and len(set(Mat[i])) == len(Mat[i]):
				count += 1
		return count


class Solution:

	def sortedCount(self, N, M, Mat):
		count = 0
		if M == 1:
			return N
		for i in range(N):
			temp = Mat[i][1] - Mat[i][0]
			is_sorted = True
			for x in range(1, M):
				if temp < 0:
					if Mat[i][x] - Mat[i][x - 1] > 0:
						is_sorted = False
						break
				if temp > 0:
					if Mat[i][x] - Mat[i][x - 1] < 0:
						is_sorted = False
						break
				if temp == 0 or Mat[i][x] - Mat[i][x - 1] == 0:
					is_sorted = False
					break
			if is_sorted:
				count += 1
		return count


class Solution:

	def sortedCount(self, N, M, Mat):
		c = 0
		for i in range(N):
			if Mat[i] == sorted(Mat[i]) or Mat[i] == sorted(Mat[i], reverse=True):
				if count(Mat[i]) == 1:
					c += 1
		return c

def count(m):
	counter = {}
	for i in m:
		counter.setdefault(i, 0)
		counter[i] += 1
	for key in counter:
		if counter[key] > 1:
			return 0
	return 1


class Solution:

	def sortedCount(self, N, M, Mat):
		count = 0
		for v in range(N):
			i = Mat[v]
			l = sorted(i)
			r = l[::-1]
			x = set(l)
			k = list(x)
			k.sort()
			if (i == l or i == r) and k == l:
				count += 1
		return count


class Solution:

	def sortedCount(self, N, M, Mat):
		c = 0
		for i in range(N):
			c1 = 0
			for j in range(M - 1):
				if Mat[i][j] > Mat[i][j + 1]:
					c1 = c1 + 1
				if Mat[i][j] < Mat[i][j + 1]:
					c1 = c1 - 1
			if c1 == M - 1 or c1 == 1 - M:
				c = c + 1
		return c


class Solution:

	def sortedCount(self, N, M, Mat):
		cnt = 0
		i = 0
		while i < len(Mat):
			one = Mat[i]
			two = one[:]
			three = one[:]
			two.sort()
			three.sort()
			three.reverse()
			s = set(one)
			if len(s) != len(one):
				pass
			elif one == two or one == three:
				cnt = cnt + 1
			i = i + 1
		return cnt


class Solution:

	def sortedCount(self, N, M, Mat):
		sum1 = 0
		for i in range(N):
			s = 0
			s1 = 0
			for j in range(M - 1):
				if Mat[i][j] < Mat[i][j + 1]:
					s += 1
				elif Mat[i][j] > Mat[i][j + 1]:
					s1 += 1
			if s == M - 1 or s1 == M - 1:
				sum1 = sum1 + 1
		return sum1


class Solution:

	def sortedCount(self, N, M, Mat):
		cnt = 0
		for i in range(N):
			iflag = True
			dflag = True
			for j in range(M - 1):
				if Mat[i][j] == Mat[i][j + 1]:
					(iflag, dflag) = (False, False)
				if Mat[i][j] > Mat[i][j + 1]:
					iflag = False
				elif Mat[i][j] < Mat[i][j + 1]:
					dflag = False
			if iflag or dflag:
				cnt += 1
		return cnt


class Solution:

	def sortedCount(self, N, M, Mat):
		ascd = desc = count_asc = count_dsc = 0
		for i in range(N):
			for j in range(0, M - 1):
				if Mat[i][j] < Mat[i][j + 1]:
					ascd += 1
				elif Mat[i][j] > Mat[i][j + 1]:
					desc += 1
			if ascd == M - 1:
				count_asc += 1
			elif desc == M - 1:
				count_dsc += 1
			ascd = desc = 0
		return count_asc + count_dsc


class Solution:

	def sortedCount(self, N, M, Mat):
		if M == 1:
			return N
		count = 0
		for i in range(N):
			less = 0
			more = 0
			for j in range(M - 1):
				if Mat[i][j] <= Mat[i][j + 1]:
					less += 1
				if Mat[i][j] >= Mat[i][j + 1]:
					more += 1
			if less == 0 and more != 0 or (less != 0 and more == 0):
				count += 1
		return count