Given two sorted matrices mat1 and mat2 of size N x N of elements. Given a value x. The problem is to count all pairs from both matrices whose sum is equal to x.
Note: The pair has an element from each matrix. Matrices are strictly sorted which means that matrices are sorted in a way such that all elements in a row are sorted in increasing order and for row ‘i’, where 1 <= i <= n-1, the first element of row 'i' is greater than the last element of row 'i-1'.
Example 1:
Input: 
N = 3, x = 21
mat1 = { {1 5 6}
         {8 10 11}
         {15 16 18} }
mat2 = { {2 4 7}
         {9 10 12}
         {13 16 20} }
OUTPUT: 4
Explanation: The pairs are (1, 20),
            (5, 16), (8, 13), (11, 10).
Example 2:
Input:
N = 2, x = 10
mat1 = { {1 2}
         {3 4} }
mat2 = { {4 5}
         {6 7}
Output: 2
Explanation: The pairs are (4, 6), (3, 7)
User Task:
Your task is to complete the function countPairs() which takes 4 arguments mat1, mat2, N, X, and returns the count of pairs. You don't need to take any input or print anything.
Expected Time Complexity: O(N^{2})
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ T ≤ 100
1 ≤ N ≤ 100
1 ≤ X ≤ 10^{5}
1 ≤ mat1[i][j] , mat2[i][j] ≤ 10^{5}

Difficulty: EASY
Tags: Matrices

Sorting

Data structures

String algorithms
Skill types: Sorting

Data structures
Expected Time Complexity: O(N^{2})
Expected Auxiliary Space: O(1)

Starter code:
#User function Template for python3
class Solution:
	def countPairs(self, mat1, mat2, n, x):
		# code here

Solutions:
class Solution:

	def countPairs(self, mat1, mat2, n, x):
		count = 0
		s = set()
		for i in range(n):
			for j in range(n):
				s.add(mat2[i][j])
		for i in range(n):
			for j in range(n):
				if x - mat1[i][j] in s:
					count += 1
		return count


class Solution:

	def countPairs(self, mat1, mat2, n, x):
		dic = {}
		count = 0
		for i in range(n):
			for j in range(n):
				dic[mat2[i][j]] = 1
		for i in range(n):
			for j in range(n):
				d = x - mat1[i][j]
				if d < 0:
					continue
				elif d in dic:
					count += 1
		return count


class Solution:

	def countPairs(self, mat1, mat2, n, x):
		counter = 0
		if n < 1:
			return counter

		def next_largest(row_idx, col_idx):
			if col_idx < n - 1:
				return (row_idx, col_idx + 1)
			else:
				return (row_idx + 1, 0)

		def next_smallest(row_idx, col_idx):
			if col_idx > 0:
				return (row_idx, col_idx - 1)
			else:
				return (row_idx - 1, n - 1)
		(m1_row, m1_col) = (0, 0)
		(m2_row, m2_col) = (n - 1, n - 1)
		index = 0
		while m1_row < n and m2_row >= 0:
			m1_val = mat1[m1_row][m1_col]
			m2_val = mat2[m2_row][m2_col]
			if m1_val + m2_val == x:
				counter += 1
				(m2_row, m2_col) = next_smallest(m2_row, m2_col)
				(m1_row, m1_col) = next_largest(m1_row, m1_col)
			elif m1_val + m2_val < x:
				(m1_row, m1_col) = next_largest(m1_row, m1_col)
			else:
				(m2_row, m2_col) = next_smallest(m2_row, m2_col)
		return counter


class Solution:

	def countPairs(self, mat1, mat2, n, x):
		r1 = 0
		c1 = 0
		r2 = n - 1
		c2 = n - 1
		count = 0
		while r1 < n and r2 >= -1:
			val = mat1[r1][c1] + mat2[r2][c2]
			if val == x:
				count += 1
				c1 += 1
				c2 -= 1
			elif val < x:
				c1 += 1
			else:
				c2 -= 1
			if c1 == n:
				c1 = 0
				r1 += 1
			if c2 == -1:
				c2 = n - 1
				r2 -= 1
		return count


class Solution:

	def countPairs(self, mat1, mat2, n, x):
		count = 0
		dic = {}
		for i in range(n):
			for j in range(n):
				if x - mat1[i][j] not in dic:
					dic[x - mat1[i][j]] = 1
				else:
					dic[x - mat1[i][j]] += 1
		lis = {}
		for i in range(n):
			for j in range(n):
				if mat2[i][j] not in lis:
					lis[mat2[i][j]] = 1
				else:
					lis[mat2[i][j]] += 1
		for i in dic:
			if i in lis:
				if lis[i] == dic[i]:
					count += dic[i]
				else:
					count += min(lis[i], dic[i])
		return count


from collections import Counter

class Solution:

	def countPairs(self, mat1, mat2, n, x):
		u = []
		v = []
		for i in range(len(mat1)):
			for j in range(len(mat1)):
				u.append(x - mat1[i][j])
				v.append(mat2[i][j])
		d = Counter(u)
		e = Counter(v)
		c = 0
		for k in d:
			if k in e:
				c += 1
		return c


class Solution:

	def countPairs(self, mat1, mat2, n, t):
		d = dict()
		ans = 0
		for i in mat1:
			for j in i:
				if j in d:
					d[j] += 1
				else:
					d[j] = 1
		for i in mat2:
			for j in i:
				if t - j in d and d[t - j] > 0:
					ans += 1
					d[t - j] -= 1
		return ans


class Solution:

	def countPairs(self, mat1, mat2, n, x):
		d = {}
		c = 0
		for i in range(n):
			for j in range(n):
				if x - mat2[i][j] in d:
					d[x - mat2[i][j]] += 1
				else:
					d[x - mat2[i][j]] = 1
		for i in range(n):
			for j in range(n):
				if mat1[i][j] in d:
					if d[mat1[i][j]] > 0:
						d[mat1[i][j]] -= 1
						c += 1
		return c


class Solution:

	def countPairs(self, mat1, mat2, n, x):
		setti1 = set()
		for item in mat1:
			setti1.update(item)
		setti2 = set()
		for item in mat2:
			setti2.update(item)
		count = 0
		for item in setti1:
			count += x - item in setti2
		return count


class Solution:

	def countPairs(self, mat1, mat2, n, x):
		lst = []
		k = 0
		for i in range(n):
			for j in range(n):
				lst.append(mat2[i][j])
		lst = set(lst)
		for i in range(n):
			for j in range(n):
				if x - mat1[i][j] in lst:
					k += 1
		return k


class Solution:

	def countPairs(self, mat1, mat2, n, x):
		c = 0
		r1 = 0
		r2 = n - 1
		c1 = 0
		c2 = n - 1
		while r1 < n and r2 >= 0:
			if mat1[r1][c1] + mat2[r2][c2] == x:
				c += 1
				c1 += 1
				c2 -= 1
			elif mat1[r1][c1] + mat2[r2][c2] < x:
				c1 += 1
			elif mat1[r1][c1] + mat2[r2][c2] > x:
				c2 -= 1
			if c1 == n:
				c1 = 0
				r1 += 1
			if c2 == -1:
				c2 = n - 1
				r2 -= 1
		return c


class Solution:

	def countPairs(self, mat1, mat2, n, x):
		res1 = []
		res2 = []
		for i in range(n):
			res1 += mat1[i]
		for i in range(n):
			res2 += mat2[i]
		d = {}
		c = 0
		for i in res1:
			if x - i not in d:
				d[x - i] = 1
			else:
				d[x - i] += 1
		for i in res2:
			if i in d.keys():
				if d[i] > 0:
					c += 1
					d[i] -= 1
		return c


class Solution:

	def countPairs(self, mat1, mat2, n, x):
		d = {}
		c = 0
		for h in mat2:
			for g in h:
				if g not in d:
					d[g] = 1
				else:
					d[g] += 1
		for h in mat1:
			for y in h:
				z = x - y
				if z in d:
					c += 1
		return c


class Solution:

	def countPairs(self, mat1, mat2, n, x):
		c = 0
		a = set()
		for k in mat2:
			for l in k:
				a.add(l)
		for i in mat1:
			b = 0
			for j in i:
				if x - j in a:
					c += 1
		return c


class Solution:

	def countPairs(self, mat1, mat2, n, x):
		l = []
		for i in mat1:
			l.extend(i)
		p = []
		for i in mat2:
			p.extend(i)
		i = 0
		g = n * n
		j = g - 1
		c = 0
		while i < g and j >= 0:
			if l[i] + p[j] == x:
				c += 1
				i += 1
				j -= 1
			elif l[i] + p[j] < x:
				i += 1
			else:
				j -= 1
		return c


class Solution:

	def countPairs(self, mat1, mat2, n, x):
		d1 = {}
		for i in mat1:
			for j in i:
				d1[j] = 1
		ans = 0
		d2 = {}
		for i in mat2:
			for j in i:
				d2[j] = 1
		for i in d1:
			a = x - i
			if a in d2:
				ans += 1
		return ans


class Solution:

	def countPairs(self, mat1, mat2, n, x):
		(i, k) = (0, n - 1)
		(j, l) = (0, n - 1)
		count = 0
		while i < n and k >= 0:
			if j >= n:
				j = 0
			if l < 0:
				l = n - 1
			while j < n and l >= 0:
				if mat1[i][j] + mat2[k][l] == x:
					count += 1
					l -= 1
					j += 1
				elif mat1[i][j] + mat2[k][l] > x:
					l -= 1
				else:
					j += 1
			if j >= n:
				i += 1
			if l < 0:
				k -= 1
		return count


class Solution:

	def countPairs(self, mat1, mat2, n, x):
		count = 0
		li = []
		a = set()
		b = set()
		for i in range(n):
			for j in range(n):
				a.add(mat1[i][j])
				b.add(mat2[i][j])
		for i in a:
			if x - i in b:
				count += 1
		return count
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(n, x) = input().split()
		(n, x) = (int(n), int(x))
		mat1 = []
		for _ in range(n):
			a = [int(x) for x in input().split()]
			mat1.append(a)
		mat2 = []
		for _ in range(n):
			a = [int(x) for x in input().split()]
			mat2.append(a)
		ob = Solution()
		ans = ob.countPairs(mat1, mat2, n, x)
		print(ans)


class Solution:

	def countPairs(self, mat1, mat2, n, x):
		c = 0
		r1 = 0
		c1 = 0
		r2 = n - 1
		c2 = n - 1
		while r1 < n and r2 >= -1:
			val = mat1[r1][c1] + mat2[r2][c2]
			if val == x:
				c += 1
				c1 += 1
				c2 -= 1
			elif val < x:
				c1 += 1
			elif val > x:
				c2 -= 1
			if c1 == n:
				c1 = 0
				r1 += 1
			if c2 == -1:
				c2 = n - 1
				r2 -= 1
		return c
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(n, x) = input().split()
		(n, x) = (int(n), int(x))
		mat1 = []
		for _ in range(n):
			a = [int(x) for x in input().split()]
			mat1.append(a)
		mat2 = []
		for _ in range(n):
			a = [int(x) for x in input().split()]
			mat2.append(a)
		ob = Solution()
		ans = ob.countPairs(mat1, mat2, n, x)
		print(ans)


class Solution:

	def countPairs(self, mat1, mat2, n, x):
		c = 0
		b = []
		for i in range(n):
			for j in range(n):
				b.append(mat2[i][j])
		for m in range(n):
			for o in range(n):
				k = x - mat1[m][o]
				l = 0
				h = n * n - 1
				while l <= h:
					mi = (l + h) // 2
					if b[mi] == k:
						c = c + 1
						break
					elif b[mi] < k:
						l = mi + 1
					else:
						h = mi - 1
		return c
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(n, x) = input().split()
		(n, x) = (int(n), int(x))
		mat1 = []
		for _ in range(n):
			a = [int(x) for x in input().split()]
			mat1.append(a)
		mat2 = []
		for _ in range(n):
			a = [int(x) for x in input().split()]
			mat2.append(a)
		ob = Solution()
		ans = ob.countPairs(mat1, mat2, n, x)
		print(ans)


class Solution:

	def bs(self, ele, l1):
		low = 0
		high = len(l1) - 1
		while low <= high:
			mid = low + (high - low) // 2
			if ele == l1[mid]:
				return True
			elif l1[mid] < ele:
				low = mid + 1
			elif l1[mid] > ele:
				high = mid - 1
		return False

	def countPairs(self, mat1, mat2, n, x):
		count = 0
		l = []
		l1 = []
		for i in range(n):
			for j in range(n):
				l1.append(mat2[i][j])
		for i in range(n):
			for j in range(n):
				if self.bs(x - mat1[i][j], l1):
					count += 1
		return count
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(n, x) = input().split()
		(n, x) = (int(n), int(x))
		mat1 = []
		for _ in range(n):
			a = [int(x) for x in input().split()]
			mat1.append(a)
		mat2 = []
		for _ in range(n):
			a = [int(x) for x in input().split()]
			mat2.append(a)
		ob = Solution()
		ans = ob.countPairs(mat1, mat2, n, x)
		print(ans)


class Solution:

	def countPairs(self, mat1, mat2, n, x):
		i1 = j1 = 0
		i2 = j2 = n - 1
		res = 0
		while i1 < n and i1 >= -1:
			if i2 < 0 or i1 >= n:
				break
			if mat1[i1][j1] + mat2[i2][j2] == x:
				res += 1
				j1 += 1
				j2 -= 1
			elif mat1[i1][j1] + mat2[i2][j2] < x:
				j1 += 1
			else:
				j2 -= 1
			if j1 == n:
				j1 = 0
				i1 += 1
			if j2 < 0:
				j2 = n - 1
				i2 -= 1
		return res
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(n, x) = input().split()
		(n, x) = (int(n), int(x))
		mat1 = []
		for _ in range(n):
			a = [int(x) for x in input().split()]
			mat1.append(a)
		mat2 = []
		for _ in range(n):
			a = [int(x) for x in input().split()]
			mat2.append(a)
		ob = Solution()
		ans = ob.countPairs(mat1, mat2, n, x)
		print(ans)


class Solution:

	def countPairs(self, mat1, mat2, n, x):
		c = 0
		l = set()
		l1 = set()
		uc = dict()
		for i in range(n):
			for j in range(n):
				l.add(x - mat1[i][j])
		for i in range(n):
			for j in range(n):
				l1.add(mat2[i][j])
		for i in l1:
			if i in l:
				c += 1
		return c
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(n, x) = input().split()
		(n, x) = (int(n), int(x))
		mat1 = []
		for _ in range(n):
			a = [int(x) for x in input().split()]
			mat1.append(a)
		mat2 = []
		for _ in range(n):
			a = [int(x) for x in input().split()]
			mat2.append(a)
		ob = Solution()
		ans = ob.countPairs(mat1, mat2, n, x)
		print(ans)


class Solution:

	def countPairs(self, mat1, mat2, n, x):
		d = {}
		ans = 0
		for i in range(n):
			for j in range(n):
				d[x - mat1[i][j]] = 1
		for i in range(n):
			for j in range(n):
				if mat2[i][j] in d:
					del d[mat2[i][j]]
					ans += 1
		return ans


from collections import defaultdict

class Solution:

	def countPairs(self, mat1, mat2, n, x):
		d = defaultdict(int)
		count = 0
		for i in range(n):
			for j in range(n):
				d[mat1[i][j]] += 1
		for i in range(n):
			for j in range(n):
				if d[x - mat2[i][j]] > 0:
					count += 1
					d[x - mat2[i][j]] -= 1
		return count


from collections import Counter

class Solution:

	def countPairs(self, mat1, mat2, n, x):
		hash1 = {}
		hash2 = {}
		for i in range(n):
			for j in range(n):
				c = mat1[i][j]
				if c not in hash1:
					hash1[c] = c
				d = mat2[i][j]
				if d not in hash2:
					hash2[d] = d
		count = 0
		for key in hash1.keys():
			temp = x - key
			if temp in hash2.keys():
				count = count + 1
		return count


class Solution:

	def countPairs(self, mat1, mat2, n, x):
		a1 = []
		a2 = []
		count = 0
		for i in range(len(mat1)):
			for j in range(len(mat1[0])):
				a1.append(mat1[i][j])
		for i in range(len(mat2)):
			for j in range(len(mat2[0])):
				a2.append(mat2[i][j])
		p1 = 0
		p2 = len(a2) - 1
		while p1 < len(a1) and p2 >= 0:
			sum = a1[p1] + a2[p2]
			if sum == x:
				count += 1
				p1 += 1
			if sum < x:
				p1 += 1
			if sum > x:
				p2 -= 1
		return count


class Solution:

	def countPairs(self, mat1, mat2, n, x):
		(lst1, lst2) = ([], [])
		for i in range(len(mat1)):
			lst1 += mat1[i]
		for i in range(len(mat2)):
			tmp = mat2[i]
			lst2 += tmp[::-1]
		Set = set()
		for i in range(len(lst2)):
			Set.add(lst2[i])
		cnt = 0
		for i in range(len(lst1)):
			if x - lst1[i] in Set:
				cnt += 1
		return cnt


class Solution:

	def countPairs(self, mat1, mat2, n, x):
		dict = {}
		count = 0
		for i in mat1:
			for j in i:
				if j not in dict:
					dict[j] = 1
				else:
					dict[j] += 1
		for i in mat2:
			for j in i:
				dif = x - j
				if dif in dict:
					if dict[dif] > 0:
						dict[dif] -= 1
						count += 1
		return count


class Solution:

	def countPairs(self, mat1, mat2, n, x):
		target = x
		hashSet = set()
		count = 0
		for i in range(len(mat2)):
			for j in range(len(mat2[0])):
				hashSet.add(mat2[i][j])
		for row in range(len(mat1)):
			for col in range(len(mat1[0])):
				d = target - mat1[row][col]
				if d in hashSet:
					count += 1
		return count


class Solution:

	def countPairs(self, mat1, mat2, n, x):
		count = 0
		for i in range(0, n):
			for j in range(0, n):
				m1 = mat1[i][j]
				if m1 > x:
					return count
				for k in range(0, n):
					if mat2[k][n - 1] >= x - m1:
						for l in range(0, n):
							if m1 + mat2[k][l] == x:
								count += 1
								break
						break
		return count


class Solution:

	def countPairs(self, mat1, mat2, n, x):
		count = 0
		hashSet = set()
		for i in range(n):
			for j in range(n):
				hashSet.add(mat2[i][j])
		for i in range(n):
			for j in range(n):
				key = x - mat1[i][j]
				if key in hashSet:
					count += 1
		return count

	def searchInMatrix(self, mat, key):
		i = 0
		j = len(mat) - 1
		while i < len(mat) and j >= 0:
			temp = mat[i][j]
			if temp == key:
				return True
			elif temp > key:
				j = j - 1
			else:
				i += 1
		return False


class Solution:

	def countPairs(self, mat1, mat2, n, x):
		count = 0
		arr = {}
		for i in range(n):
			for j in range(n):
				arr.setdefault(mat2[i][j], 1)
		for i in range(n):
			for j in range(n):
				if x - mat1[i][j] in arr and arr[x - mat1[i][j]] != 0:
					count += 1
					arr[x - mat1[i][j]] = 0
		return count


class Solution:

	def countPairs(self, mat1, mat2, n, x):
		l1 = []
		for i in mat1:
			for j in i:
				l1.append(j)
		l2 = []
		for i in mat2:
			for j in i:
				l2.append(j)
		p1 = 0
		p2 = n * n - 1
		res = 0
		while p1 <= n * n - 1 and p2 >= 0:
			if l1[p1] + l2[p2] > x:
				p2 -= 1
			elif l1[p1] + l2[p2] < x:
				p1 += 1
			else:
				res += 1
				p1 += 1
				p2 -= 1
		return res


class Solution:

	def countPairs(self, mat1, mat2, n, x):
		s = set()
		ct = 0
		for r in range(n):
			for c in range(n):
				s.add(mat2[r][c])
		for r in range(n):
			for c in range(n):
				if x - mat1[r][c] in s:
					ct += 1
		return ct


from collections import Counter

class Solution:

	def countPairs(self, mat1, mat2, n, x):
		st1 = set()
		st2 = set()
		cc = 0
		for r in range(n):
			for c in range(n):
				st1.add(mat1[r][c])
				st2.add(mat2[r][c])
		for v in st1:
			if x - v in st2:
				cc += 1
		return cc


from collections import Counter

class Solution:

	def countPairs(self, mat1, mat2, n, x):
		st1 = set()
		st2 = set()
		c = 0
		for l in mat1:
			st1.update(set(l))
		for l in mat2:
			st2.update(set(l))
		c1 = Counter(st1)
		c2 = Counter(st2)
		for v in st1:
			c1[v] = c1.get(v, 0) - 1
			res = x - v
			if c2.get(res, 0) > 0:
				c += 1
				c2[res] = c2.get(res, 0) - 1
		return c


from collections import Counter

class Solution:

	def countPairs(self, mat1, mat2, n, x):
		s = set()
		ans = 0
		for i in range(n):
			for j in range(n):
				s.add(mat2[i][j])
		for i in range(n):
			for j in range(n):
				if x - mat1[i][j] in s:
					ans += 1
		return ans


class Solution:

	def countPairs(self, mat1, mat2, n, x):
		i1 = 0
		j1 = 0
		i2 = n - 1
		j2 = n - 1
		count = 0
		while i1 < n and i2 >= 0:
			if mat1[i1][j1] + mat2[i2][j2] == x:
				count += 1
				j1 += 1
				if j1 == n:
					i1 += 1
					j1 = 0
				j2 -= 1
				if j2 < 0:
					j2 = n - 1
					i2 -= 1
			elif mat1[i1][j1] + mat2[i2][j2] < x:
				j1 += 1
				if j1 == n:
					i1 += 1
					j1 = 0
			else:
				j2 -= 1
				if j2 < 0:
					j2 = n - 1
					i2 -= 1
		return count


class Solution:

	def countPairs(self, mat1, mat2, n, x):
		flattern_mat2 = []
		for m in mat2:
			flattern_mat2 += m
		flattern_mat2 = set(flattern_mat2)
		ct = 0
		for i in range(n):
			for j in range(n):
				if x - mat1[i][j] in flattern_mat2:
					ct += 1
		return ct


class Solution:

	def countPairs(self, mat1, mat2, n, x):
		mp1 = {}
		count = 0
		for i in mat2:
			for j in i:
				mp1[j] = j
		for i in mat1:
			for j in i:
				if x - j in mp1:
					count += 1
		return count


class Solution:

	def countPairs(self, mat1, mat2, n, x):
		d = set()
		count = 0
		for i in range(len(mat1)):
			for j in range(len(mat1[0])):
				if mat1[i][j] in d:
					pass
				else:
					d.add(mat1[i][j])
		d2 = set()
		for i in range(len(mat2)):
			for j in range(len(mat2[0])):
				if mat2[i][j] in d2:
					pass
				else:
					if x - mat2[i][j] in d:
						count += 1
					d2.add(mat2[i][j])
		return count


class Solution:

	def countPairs(self, mat1, mat2, n, x):
		dic1 = {}
		dic2 = {}
		count = 0
		for i in range(n):
			for j in range(n):
				if x - mat1[i][j] in dic1:
					dic1[x - mat1[i][j]] += 1
				else:
					dic1[x - mat1[i][j]] = 1
		for i in range(n):
			for j in range(n):
				if mat2[i][j] in dic2:
					dic2[mat2[i][j]] += 1
				else:
					dic2[mat2[i][j]] = 1
		for i in dic1:
			if i in dic2:
				count += 1
		return count