Given a matrix mat[][] of size N x M, where every row and column is sorted in increasing order, and a number X is given. The task is to find whether element X is present in the matrix or not.
Example 1:
Input:
N = 3, M = 3
mat[][] = 3 30 38 
         44 52 54 
         57 60 69
X = 62
Output:
0
Explanation:
62 is not present in the
matrix, so output is 0
Example 2:
Input:
N = 1, M = 6
mat[][] = 18 21 27 38 55 67
X = 55
Output:
1
Explanation:
55 is present in the
matrix at 5th cell.
Your Task:
You don't need to read input or print anything. You just have to complete the function matSearch() which takes a 2D matrix mat[][], its dimensions N and M and integer X as inputs and returns 1 if the element X is present in the matrix and 0 otherwise.
Expected Time Complexity: O(N+M).
Expected Auxiliary Space: O(1).
Constraints:
1 <= N, M <= 1005
1 <= mat[][] <= 10000000
1<= X <= 10000000

Difficulty: EASY
Tags: Matrices

Data structures

Complete search
Skill types: Data structures

Complete search
Expected Time Complexity: O(N+M).
Expected Auxiliary Space: O(1).

Starter code:
#User function Template for python3

class Solution:

	def matSearch(self,mat, N, M, X):

		# Complete this function

Solutions:
class Solution:

	def matSearch(self, mat, N, M, X):
		for i in range(N):
			for j in range(M):
				if mat[i][j] == X:
					return 1
		return 0


class Solution:

	def matSearch(self, matrix, N, M, x):
		for i in range(len(matrix)):
			if x >= matrix[i][0] and x <= matrix[i][-1]:

				def binary(arr, element, start, end):
					while start <= end:
						mid = (start + end) // 2
						if arr[mid] == element:
							return mid
						elif arr[mid] > element:
							end = mid - 1
						else:
							start = mid + 1
					return -1
				if binary(matrix[i], x, 0, len(matrix[i]) - 1) != -1:
					return 1
		return 0


class Solution:

	def matSearch(self, mat, N, M, X):
		i = 0
		j = M - 1
		while i < N and j >= 0:
			if mat[i][j] == X:
				return 1
			elif mat[i][j] > X:
				j -= 1
			else:
				i += 1
		return 0


import numpy as np

class Solution:

	def matSearch(self, mat, N, M, X):
		for i in mat:
			if X in i:
				return '1'
		return '0'


class Solution:

	def matSearch(self, mat, N, M, X):
		if not mat or N == 0 or M == 0:
			return 0
		for row in mat:
			left = 0
			right = M - 1
			while left <= right:
				mid = left + (right - left) // 2
				if row[mid] == X:
					return 1
				elif row[mid] < X:
					left = mid + 1
				else:
					right = mid - 1
		return 0


class Solution:

	def matSearch(self, mat, N, M, X):
		a = []
		for i in range(len(mat)):
			for j in range(len(mat[i])):
				a.append(mat[i][j])
		if X in a:
			return 1
		else:
			return 0


class Solution:

	def matSearch(self, mat, N, M, X):
		a = [element for sublist in mat for element in sublist]
		a.sort()
		if X not in a:
			return 0
		else:
			return 1


class Solution:

	def matSearch(self, mat, N, M, X):
		for i in range(n):
			l = 0
			r = m - 1
			while l <= r:
				mid = (l + r) // 2
				if mat[i][mid] == X:
					return 1
				if mat[i][mid] < X:
					l = mid + 1
				else:
					r = mid - 1
		return 0


class Solution:

	def matSearch(self, arr, N, M, X):
		i = 0
		while i < N:
			j = M - 1
			if arr[i][j] == X:
				return 1
			elif arr[i][j] > X:
				j -= 1
				while j >= 0:
					if arr[i][j] == X:
						return 1
					elif arr[i][j] < X:
						break
					j -= 1
				i += 1
			else:
				i += 1
		return 0


class Solution:

	def matSearch(self, mat, N, M, X):
		l = []
		c = 0
		for i in range(len(mat)):
			for j in range(len(mat[0])):
				l.append(mat[i][j])
		for i in range(len(l)):
			if l[i] == x:
				c += 1
		if c > 0:
			return 1
		return 0


class Solution:

	def matSearch(self, mat, N, M, X):
		for arr in mat:
			if X in arr:
				return 1
		return 0


class Solution:

	def matSearch(self, mat, N, M, X):
		b = False
		ind = 0
		for i in range(N):
			for j in range(M):
				if X == mat[i][j]:
					b = True
					ind = i
		if b:
			return 1
		else:
			return 0


class Solution:

	def matSearch(self, mat, N, M, X):
		row = 0
		col = M - 1
		while col >= 0 and row <= N - 1:
			if mat[row][col] == X:
				return 1
			elif mat[row][col] < X:
				row += 1
			else:
				col -= 1
		return 0


class Solution:

	def matSearch(self, mat, N, M, X):
		flag = 0
		for i in mat:
			if X in i:
				return 1
		return 0


class Solution:

	def matSearch(self, mat, N, M, X):
		for i in range(N):
			low = 0
			high = M - 1
			while low <= high:
				mid = low + (high - low) // 2
				if mat[i][mid] == X:
					return 1
				elif mat[i][mid] < X:
					low = mid + 1
				else:
					high = mid - 1
		return 0


class Solution:

	def matSearch(self, mat, N, M, X):
		r = 0
		c = M - 1
		while r < N and c >= 0:
			if X == mat[r][c]:
				return 1
			if X < mat[r][c]:
				c -= 1
			else:
				r += 1
		return 0


class Solution:

	def matSearch(self, mat, n, m, x):
		for i in range(n):
			if x in mat[i]:
				return 1
		return 0


class Solution:

	def matSearch(self, mat, n, m, x):
		i = 0
		j = m - 1
		while i < n and j >= 0:
			if mat[i][j] == x:
				return 1
			if mat[i][j] > x:
				j -= 1
			if mat[i][j] < x:
				i += 1
		return 0


class Solution:

	def matSearch(self, mat, N, M, X):
		start = 0
		end = M - 1
		while start < N and end >= 0:
			if mat[start][end] == X:
				return '1'
			if mat[start][end] < X:
				start += 1
			else:
				end -= 1
		return '0'


class Solution:

	def matSearch(self, mat, N, M, X):
		for c in mat:
			for a in c:
				if a == x:
					return 1
		return 0


class Solution:

	def matSearch(self, matrix, n, m, x):
		for i in range(n):
			for j in range(m):
				if matrix[i][j] == x:
					return 1
		return 0


class Solution:

	def matSearch(self, mat, N, M, X):
		ans = 0
		for i in range(N):
			arr = mat[i]
			ans = self.binary_search(arr, 0, len(arr) - 1, X)
			if ans == 1:
				return 1
		return 0

	def binary_search(self, arr, low, high, k):
		while low <= high:
			mid = int((low + high) / 2)
			if arr[mid] == k:
				return 1
			if arr[mid] > k:
				high = mid - 1
			else:
				low = mid + 1
		return 0


class Solution:

	def matSearch(self, mat, N, M, X):
		i = 0
		while i < N:
			j = 0
			while j < M:
				if mat[i][j] == X:
					return 1
				j += 1
			i += 1
		return 0


class Solution:

	def matSearch(self, mat, N, M, X):

		def binary_search(arr, target):
			start = 0
			end = len(arr) - 1
			while start <= end:
				mid = (start + end) // 2
				if arr[mid] == target:
					return mid
				if arr[mid] > target:
					end = mid - 1
				else:
					start = mid + 1
			return -1
		for i in mat:
			if binary_search(i, X) != -1:
				return 1
		return 0