Count pairs Sum in matrices

Given two matrices mat1[][] and mat2[][] of size n x n, where the elements in each matrix are arranged in strictly ascending order. Specifically, each row is sorted from left to right, and the last element of a row is smaller than the first element of the next row.
You’re given a target value x, your task is to find and countall pairs {a, b} such that a is from mat1 and b is from mat2 where the sum of a + b is equal to x.

Examples:

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 whose sum is found to be 21 are (1, 20), (5, 16), (8, 13) and (11, 10).

Input: n = 2, x = 10,
mat1[][] = [[1, 2], [3, 4]]
mat2[][] = [[4, 5], [6, 7]]
Output: 2
Explanation: The pairs whose sum found to be 10 are (4, 6) and (3, 7).

Constraints:
1 ≤ n ≤ 100
1 ≤ x ≤ 10⁵
1 ≤ mat1[i][j] , mat2[i][j] ≤ 10⁵

Approach 01:

class Solution {
public:
    int countPairs(vector<vector<int>> mat1, vector<vector<int>> mat2, int x) {
        int n = mat1.size();
        unordered_set<int> elementsInMat2;
        int pairCount = 0;

        for (int row = 0; row < n; ++row) {
            for (int col = 0; col < n; ++col) {
                elementsInMat2.insert(mat2[row][col]);
            }
        }

        for (int row = 0; row < n; ++row) {
            for (int col = 0; col < n; ++col) {
                if (elementsInMat2.count(x - mat1[row][col])) {
                    pairCount++;
                }
            }
        }

        return pairCount;
    }
};

class Solution:
    def countPairs(self, mat1, mat2, x):
        n = len(mat1)
        elementsInMat2 = set()
        pairCount = 0

        for row in range(n):
            for col in range(n):
                elementsInMat2.add(mat2[row][col])

        for row in range(n):
            for col in range(n):
                if (x - mat1[row][col]) in elementsInMat2:
                    pairCount += 1

        return pairCount

Time Complexity:

• Inserting elements from mat2 into the set:

  There are \(n^2\) elements → \(O(n^2)\).

• Iterating through mat1 and checking for complements:

  Again, \(n^2\) elements and each lookup in the set is \(O(1)\) → \(O(n^2)\).

• Total Time Complexity:

  \(O(n^2)\).

Space Complexity:

• Unordered set for elements of mat2:

  Stores up to \(n^2\) unique elements → \(O(n^2)\).

• Total Space Complexity:

  \(O(n^2)\).