Count pairs from two sorted matrices with given sum

0 0 29 minutes read

Given two sorted matrices mat1 and mat2 of size n x n of distinct 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, first element of row ‘i’ is greater than the last element of row ‘i-1’.

Examples:

Input : mat1[][] = { {1, 5, 6},
                    {8, 10, 11},
                   {15, 16, 18} }
                         
    mat2[][] = { {2, 4, 7},
                 {9, 10, 12},
                 {13, 16, 20} }
       x = 21 
Output : 4
The pairs are:
(1, 20), (5, 16), (8, 13) and (11, 10).

Method 1 (Naive Approach): For each element ele of mat1[][] linearly search (x – ele) in mat2[][].

C++

// C++ implementation to count pairs from two 
// sorted matrices whose sum is equal to a 
// given value x
#include <bits/stdc++.h>
 
using namespace std;
 
#define SIZE 10
 
// function to search 'val' in mat[][]
// returns true if 'val' is present
// else false
bool valuePresent(int mat[][SIZE], int n, int val)
{
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (mat[i][j] == val)
 
                // 'val' found
                return true;
 
    // 'val' not found
    return false;
}
 
// function to count pairs from two sorted matrices
// whose sum is equal to a given value x
int countPairs(int mat1[][SIZE], int mat2[][SIZE],
               int n, int x)
{
    int count = 0;
 
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
 
            // if value (x-mat1[i][j]) is found in mat2[][]
            if (valuePresent(mat2, n, x - mat1[i][j]))
                count++;
 
    // required count of pairs
    return count;
}
 
// Driver program to test above
int main()
{
    int mat1[][SIZE] = { { 1, 5, 6 },
                         { 8, 10, 11 },
                         { 15, 16, 18 } };
 
    int mat2[][SIZE] = { { 2, 4, 7 },
                         { 9, 10, 12 },
                         { 13, 16, 20 } };
 
    int n = 3;
    int x = 21;
 
    cout << "Count = "
         << countPairs(mat1, mat2, n, x);
 
    return 0;
}

Java

// java implementation to count 
// pairs from twosorted matrices 
// whose sum is equal to a given value
import java.io.*;
 
class GFG
{    
    int SIZE= 10;
     
    // function to search 'val' in mat[][]
    // returns true if 'val' is present
    // else false
    static boolean valuePresent(int mat[][], int n, 
                                            int val)
    {
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (mat[i][j] == val)
                     
                    // 'val' found
                    return true;
     
        // 'val' not found
        return false;
    }
     
    // function to count pairs from 
    // two sorted matrices whose sum
    // is equal to a given value x
    static int countPairs(int mat1[][], int mat2[][],
                                        int n, int x)
    {
        int count = 0;
     
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
            {
                // if value (x-mat1[i][j]) is 
                // found in mat2[][]
                if (valuePresent(mat2, n, x - mat1[i][j]))
                   count++;
            }
        // required count of pairs
        return count;
    }
 
    // Driver program 
    public static void main (String[] args) 
    {
        int mat1[][] = { { 1, 5, 6 },
                         { 8, 10, 11 },
                         { 15, 16, 18 } };
 
        int mat2[][] = { { 2, 4, 7 },
                         { 9, 10, 12 },
                         { 13, 16, 20 } };
     
        int n = 3;
        int x = 21;
     
        System.out.println ("Count = " +
                           countPairs(mat1, mat2, n, x));
         
    }
}
 
// This article is contributed by vt_m

Python3

# Python3 implementation to count pairs
# from two sorted matrices whose sum is
# equal to a given value x 
 
# function to search 'val' in mat[][] 
# returns true if 'val' is present else
# false
def valuePresent(mat, n, val):
 
    for i in range(0, n):
        for j in range(0, n):
 
            if mat[i][j] == val:
 
                # 'val' found
                return True
 
    # 'val' not found
    return False
 
# function to count pairs from two sorted
# matrices whose sum is equal to a given
# value x
def countPairs(mat1, mat2, n, x):
 
    count = 0
 
    for i in range(0, n):
        for j in range(0, n):
 
            # if value (x-mat1[i][j]) is found
            # in mat2[][]
            if valuePresent(mat2, n, x - mat1[i][j]):
                count += 1
 
    # required count of pairs
    return count
 
# Driver program
mat1 = [[ 1, 5, 6 ],
        [ 8, 10, 11 ],
        [ 15, 16, 18 ] ]
 
mat2 = [ [ 2, 4, 7 ],
         [ 9, 10, 12 ],
         [ 13, 16, 20 ] ]
 
n = 3
x = 21
 
print( "Count = "),
print(countPairs(mat1, mat2, n, x))
 
# This code is contributed by upendra bartwal

C#

//C# implementation to count 
// pairs from twosorted matrices 
// whose sum is equal to a given value
using System;
 
class GFG
{ 
    // int SIZE= 10;
     
    // function to search 'val' in mat[][]
    // returns true if 'val' is present
    // else false
    static bool valuePresent(int[,] mat, int n, 
                                        int val)
    {
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (mat[i, j] == val)
                     
                    // 'val' found
                    return true;
     
        // 'val' not found
        return false;
    }
     
    // function to count pairs from 
    // two sorted matrices whose sum
    // is equal to a given value x
    static int countPairs(int [,]mat1, int [,]mat2,
                                        int n, int x)
    {
        int count = 0;
     
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
            {
                // if value (x-mat1[i][j]) is 
                // found in mat2[][]
                if (valuePresent(mat2, n, x - mat1[i,j]))
                count++;
            }
        // required count of pairs
        return count;
    }
 
    // Driver program 
    public static void Main () 
    {
        int [,]mat1 = { { 1, 5, 6 },
                        { 8, 10, 11 },
                        { 15, 16, 18 } };
 
        int [,]mat2 = { { 2, 4, 7 },
                        { 9, 10, 12 },
                        { 13, 16, 20 } };
     
        int n = 3;
        int x = 21;
     
        Console.WriteLine("Count = " +
                        countPairs(mat1, mat2, n, x));
         
    }
}
 
// This article is contributed by vt_m

PHP

<?php
//PHP  implementation to count pairs from two 
// sorted matrices whose sum is equal to a 
// given value x 
// function to search 'val' in mat[][] 
// returns true if 'val' is present 
// else false 
function valuePresent($mat, $n, $val) 
{ 
    for ($i = 0; $i < $n; $i++) 
        for ($j = 0; $j < $n; $j++) 
            if ($mat[$i][$j] == $val) 
 
                // 'val' found 
                return true; 
 
    // 'val' not found 
    return false; 
} 
 
// function to count pairs from two sorted matrices 
// whose sum is equal to a given value x 
function countPairs($mat1, $mat2, $n, $x) 
{ 
    $count = 0; 
 
    for ($i = 0; $i < $n; $i++) 
        for ( $j = 0; $j < $n; $j++) 
 
            // if value (x-mat1[i][j]) is found in mat2[][] 
            if (valuePresent($mat2, $n, $x - $mat1[$i][$j])) 
                $count++; 
 
    // required count of pairs 
    return $count; 
} 
 
// Driver program to test above 
    $mat1 = array(array( 1, 5, 6 ), 
                array( 8, 10, 11 ), 
                array( 15, 16, 18 )); 
 
    $mat2 = array(array( 2, 4, 7 ), 
                array(9, 10, 12 ), 
                array(13, 16, 20 )); 
 
    $n = 3; 
    $x = 21; 
 
    echo "Count = ",
        countPairs($mat1, $mat2, $n, $x); 
 
#This code is contributed by ajit.
?>

Javascript

<script>
 
// Javascript implementation to count
// pairs from twosorted matrices
// whose sum is equal to a given value
let SIZE = 10;
  
// Function to search 'val' in mat[][]
// returns true if 'val' is present
// else false
function valuePresent(mat, n, val)
{
    for(let i = 0; i < n; i++)
        for(let j = 0; j < n; j++)
            if (mat[i][j] == val)
                  
                // 'val' found
                return true;
  
    // 'val' not found
    return false;
}
  
// Function to count pairs from
// two sorted matrices whose sum
// is equal to a given value x
function countPairs(mat1, mat2, n, x)
{
    let count = 0;
  
    for(let i = 0; i < n; i++)
        for(let j = 0; j < n; j++)
        {
             
            // If value (x-mat1[i][j]) is
            // found in mat2[][]
            if (valuePresent(mat2, n, x - mat1[i][j]))
               count++;
        }
         
    // Required count of pairs
    return count;
}
 
// Driver code
let mat1 = [ [ 1, 5, 6 ],
             [ 8, 10, 11 ],
             [ 15, 16, 18 ] ];
 
let mat2 = [ [ 2, 4, 7 ],
             [ 9, 10, 12 ],
             [ 13, 16, 20 ] ];
 
let n = 3;
let x = 21;
 
document.write("Count = " + 
               countPairs(mat1, mat2, n, x));
                
// This code is contributed by divyeshrabadiya07  
 
</script>

Output:

Count = 4

Time Complexity: O(n⁴).
Auxiliary Space: O(1).

Method 2 (Binary Search): As matrix is strictly sorted, use the concept of binary search technique. For each element ele of mat1[][] apply the binary search technique on the elements of the first column of mat2[][] to find the row index number of the largest element smaller than equal to (x – ele). Let it be row_no. If no such row exists then no pair can be formed with element ele. Else apply the concept of binary search technique to find the value (x – ele) in the row represented by row_no in mat2[][]. If value found then increment count.

C++

// C++ implementation to count pairs from two
// sorted matrices whose sum is equal to a given
// value x
#include <bits/stdc++.h>
 
using namespace std;
 
#define SIZE 10
 
// function returns the row index no of largest
// element smaller than equal to 'x' in first
// column of mat[][]. If no such element exists 
// then it returns -1.
int binarySearchOnRow(int mat[SIZE][SIZE],
                      int l, int h, int x)
{
    while (l <= h) {
        int mid = (l + h) / 2;
 
        // if 'x' is greater than or equal to mat[mid][0],
        // then search in mat[mid+1...h][0]
        if (mat[mid][0] <= x)
            l = mid + 1;
 
        // else search in mat[l...mid-1][0]
        else
            h = mid - 1;
    }
 
    // required row index number
    return h;
}
 
// function to search 'val' in mat[row][]
bool binarySearchOnCol(int mat[][SIZE], int l, int h,
                       int val, int row)
{
    while (l <= h) {
        int mid = (l + h) / 2;
 
        // 'val' found
        if (mat[row][mid] == val)
            return true;
 
        // search in mat[row][mid+1...h]
        else if (mat[row][mid] < val)
            l = mid + 1;
 
        // search in mat[row][l...mid-1]
        else
            h = mid - 1;
    }
 
    // 'val' not found
    return false;
}
 
// function to search 'val' in mat[][]
// returns true if 'val' is present
// else false
bool searchValue(int mat[][SIZE],
                 int n, int val)
{
    // to get the row index number of the largest element
    // smaller than equal to 'val' in mat[][]
    int row_no = binarySearchOnRow(mat, 0, n - 1, val);
 
    // if no such row exists, then
    // 'val' is not present
    if (row_no == -1)
        return false;
 
    // to search 'val' in mat[row_no][]
    return binarySearchOnCol(mat, 0, n - 1, val, row_no);
}
 
// function to count pairs from two sorted matrices
// whose sum is equal to a given value x
int countPairs(int mat1[][SIZE], int mat2[][SIZE],
               int n, int x)
{
    int count = 0;
 
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            // if value (x-mat1[i][j]) is found in mat2[][]
            if (searchValue(mat2, n, x - mat1[i][j]))
                count++;
 
    // required count of pairs
    return count;
}
 
// Driver program to test above
int main()
{
    int mat1[][SIZE] = { { 1, 5, 6 },
                         { 8, 10, 11 },
                         { 15, 16, 18 } };
 
    int mat2[][SIZE] = { { 2, 4, 7 },
                         { 9, 10, 12 },
                         { 13, 16, 20 } };
 
    int n = 3;
    int x = 21;
 
    cout << "Count = "
         << countPairs(mat1, mat2, n, x);
 
    return 0;
}

Java

// Java implementation to count 
// pairs from two sorted matrices 
// whose sum is equal to a given
// value x
import java.io.*;
 
class GFG {
    int SIZE= 10;
 
    // function returns the row index no of largest
    // element smaller than equal to 'x' in first
    // column of mat[][]. If no such element exists 
    // then it returns -1.
    static int binarySearchOnRow(int mat[][], int l,
                                       int h, int x)
    {
        while (l <= h)
        {
            int mid = (l + h) / 2;
     
            // if 'x' is greater than or 
            // equal to mat[mid][0], then 
            // search in mat[mid+1...h][0]
            if (mat[mid][0] <= x)
                l = mid + 1;
     
            // else search in mat[l...mid-1][0]
            else
                h = mid - 1;
        }
     
        // required row index number
        return h;
    }
     
    // function to search 'val' in mat[row][]
    static boolean binarySearchOnCol(int mat[][], int l, int h,
                                             int val, int row)
    {
        while (l <= h)
        {
            int mid = (l + h) / 2;
     
            // 'val' found
            if (mat[row][mid] == val)
                return true;
     
            // search in mat[row][mid+1...h]
            else if (mat[row][mid] < val)
                l = mid + 1;
     
            // search in mat[row][l...mid-1]
            else
                h = mid - 1;
        }
     
        // 'val' not found
        return false;
    }
     
    // function to search 'val' in mat[][]
    // returns true if 'val' is present
    // else false
    static boolean searchValue(int mat[][],
                               int n, int val)
    {
        // to get the row index number 
        // of the largest element smaller 
        // than equal to 'val' in mat[][]
        int row_no = binarySearchOnRow(mat, 0, n - 1, val);
     
        // if no such row exists, then
        // 'val' is not present
        if (row_no == -1)
            return false;
     
        // to search 'val' in mat[row_no][]
        return binarySearchOnCol(mat, 0, n - 1, val, row_no);
    }
     
    // function to count pairs from 
    // two sorted matrices whose sum 
    // is equal to a given value x
    static int countPairs(int mat1[][], int mat2[][],
                                        int n, int x)
    {
        int count = 0;
     
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
            {
                // if value (x-mat1[i][j]) is found in mat2[][]
                if (searchValue(mat2, n, x - mat1[i][j]))
                    count++;
            }    
        // required count of pairs
        return count;
    }
     
    // Driver program 
    public static void main (String[] args) 
    {
        int mat1[][] = { { 1, 5, 6 },
                         { 8, 10, 11 },
                         { 15, 16, 18 } };
 
        int mat2[][] = { { 2, 4, 7 },
                         { 9, 10, 12 },
                         { 13, 16, 20 } };
     
        int n = 3;
        int x = 21;
     
        System.out.println ( "Count = "  +
                           countPairs(mat1, mat2, n, x));
             
    }
}
 
// This code is contributed by vt_m

Python3

# Python 3 implementation to count pairs 
# from two sorted matrices whose sum is 
# equal to a given value x
 
SIZE = 10
 
# function returns the row index no of 
# largest element smaller than equal 
# to 'x' in first column of mat[][]. 
# If no such element exists then it returns -1.
def binarySearchOnRow(mat, l, h, x):
    while (l <= h):
        mid = int((l + h) / 2)
 
        # if 'x' is greater than or equal 
        # to mat[mid][0], then search in 
        # mat[mid+1...h][0]
        if (mat[mid][0] <= x):
            l = mid + 1
 
        # else search in mat[l...mid-1][0]
        else:
            h = mid - 1
 
    # required row index number
    return h
 
# function to search 'val' in mat[row][]
def binarySearchOnCol(mat, l, h, val, row):
    while (l <= h):
        mid = int((l + h) / 2)
 
        # 'val' found
        if (mat[row][mid] == val):
            return True
 
        # search in mat[row][mid+1...h]
        elif (mat[row][mid] < val):
            l = mid + 1
 
        # search in mat[row][l...mid-1]
        else:
            h = mid - 1
 
    # 'val' not found
    return False
 
# function to search 'val' in mat[][]
# returns true if 'val' is present
# else false
def searchValue(mat, n, val):
     
    # to get the row index number of the 
    # largest element smaller than equal 
    # to 'val' in mat[][]
    row_no = binarySearchOnRow(mat, 0, n - 1, val)
 
    # if no such row exists, then
    # 'val' is not present
    if (row_no == -1):
        return False
 
    # to search 'val' in mat[row_no][]
    return binarySearchOnCol(mat, 0, n - 1,
                               val, row_no)
 
# function to count pairs from two sorted matrices
# whose sum is equal to a given value x
def countPairs(mat1, mat2, n, x):
    count = 0
 
    for i in range(n):
        for j in range(n):
             
            # if value (x-mat1[i][j]) is 
            # found in mat2[][]
            if (searchValue(mat2, n, x - mat1[i][j])):
                count += 1
 
    # required count of pairs
    return count
 
# Driver Code
if __name__ == '__main__':
    mat1 = [[1, 5, 6],
            [8, 10,11],
            [15, 16, 18]]
 
    mat2 = [[2, 4, 7],
            [9, 10, 12],
            [13, 16, 20]]
 
    n = 3
    x = 21
 
    print("Count =", countPairs(mat1, mat2, n, x))
     
# This code is contributed by
# Shashank_Sharma

C#

// C# implementation to count 
// pairs from two sorted matrices 
// whose sum is equal to a given
// value x
using System;
 
class GFG 
{
    //int SIZE= 10;
 
    // function returns the row index no of largest
    // element smaller than equal to 'x' in first
    // column of mat[][]. If no such element exists 
    // then it returns -1.
    static int binarySearchOnRow(int [,]mat, int l,
                                    int h, int x)
    {
        while (l <= h)
        {
            int mid = (l + h) / 2;
     
            // if 'x' is greater than or 
            // equal to mat[mid][0], then 
            // search in mat[mid+1...h][0]
            if (mat[mid,0] <= x)
                l = mid + 1;
     
            // else search in mat[l...mid-1][0]
            else
                h = mid - 1;
        }
     
        // required row index number
        return h;
    }
     
    // function to search 'val' in mat[row][]
    static bool binarySearchOnCol(int [,]mat, int l, int h,
                                            int val, int row)
    {
        while (l <= h)
        {
            int mid = (l + h) / 2;
     
            // 'val' found
            if (mat[row,mid] == val)
                return true;
     
            // search in mat[row][mid+1...h]
            else if (mat[row,mid] < val)
                l = mid + 1;
     
            // search in mat[row][l...mid-1]
            else
                h = mid - 1;
        }
     
        // 'val' not found
        return false;
    }
     
    // function to search 'val' in mat[][]
    // returns true if 'val' is present
    // else false
    static bool searchValue(int [,]mat,
                            int n, int val)
    {
        // to get the row index number 
        // of the largest element smaller 
        // than equal to 'val' in mat[][]
        int row_no = binarySearchOnRow(mat, 0, n - 1, val);
     
        // if no such row exists, then
        // 'val' is not present
        if (row_no == -1)
            return false;
     
        // to search 'val' in mat[row_no][]
        return binarySearchOnCol(mat, 0, n - 1, val, row_no);
    }
     
    // function to count pairs from 
    // two sorted matrices whose sum 
    // is equal to a given value x
    static int countPairs(int [,]mat1, int [,]mat2,
                                        int n, int x)
    {
        int count = 0;
     
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
            {
                // if value (x-mat1[i][j]) is found in mat2[][]
                if (searchValue(mat2, n, x - mat1[i,j]))
                    count++;
            } 
        // required count of pairs
        return count;
    }
     
    // Driver program 
    public static void Main () 
    {
        int [,]mat1 = { { 1, 5, 6 },
                        { 8, 10, 11 },
                        { 15, 16, 18 } };
 
        int [,]mat2 = { { 2, 4, 7 },
                        { 9, 10, 12 },
                        { 13, 16, 20 } };
     
        int n = 3;
        int x = 21;
     
        Console.WriteLine ( "Count = " +
                        countPairs(mat1, mat2, n, x));
             
    }
}
 
// This code is contributed by vt_m

PHP

<?php
// PHP implementation to count pairs 
// from two sorted matrices whose sum 
// is equal to a given value x
 
// function returns the row index no. 
// of largest element smaller than 
// equal to 'x' in first column of 
// mat[][]. If no such element exists 
// then it returns -1.
function binarySearchOnRow($mat, $l,
                             $h, $x)
{
    while ($l <= $h)
    {
        $mid = ($l + $h) / 2;
 
        // if 'x' is greater than or 
        // equal to mat[mid][0], then
        // search in mat[mid+1...h][0]
        if ($mat[$mid][0] <= $x)
            $l = $mid + 1;
 
        // else search in mat[l...mid-1][0]
        else
            $h = $mid - 1;
    }
 
    // required row index number
    return $h;
}
 
// function to search 'val' in mat[row][]
function binarySearchOnCol($mat, $l, $h,
                           $val, $row)
{
    while ($l <= $h)
    {
        $mid = ($l + $h) / 2;
 
        // 'val' found
        if ($mat[$row][$mid] == $val)
            return true;
 
        // search in mat[row][mid+1...h]
        else if ($mat[$row][$mid] < $val)
            $l = $mid + 1;
 
        // search in mat[row][l...mid-1]
        else
            $h = $mid - 1;
    }
 
    // 'val' not found
    return false;
}
 
// function to search 'val' in mat[][]
// returns true if 'val' is present
// else false
function searchValue($mat,$n, $val)
{
    // to get the row index number of the
    // largest element smaller than equal 
    // to 'val' in mat[][]
    $row_no = binarySearchOnRow($mat, 0, 
                                $n - 1, $val);
 
    // if no such row exists, then
    // 'val' is not present
    if ($row_no == -1)
        return false;
 
    // to search 'val' in mat[row_no][]
    return binarySearchOnCol($mat, 0, $n - 1, 
                             $val, $row_no);
}
 
// function to count pairs from two 
// sorted matrices whose sum is equal 
// to a given value x
function countPairs($mat1, $mat2, $n, $x)
{
    $count = 0;
 
    for ($i = 0; $i < $n; $i++)
        for ($j = 0; $j < $n; $j++)
         
            // if value (x-mat1[i][j]) is
            // found in mat2[][]
            if (searchValue($mat2, $n, 
                            $x - $mat1[$i][$j]))
                $count++;
 
    // required count of pairs
    return $count;
}
 
// Driver Code
$mat1 = array(array(1, 5, 6 ),
              array(8, 10, 11 ),
              array(15, 16, 18 ));
 
$mat2 = array(array(2, 4, 7 ),
              array(9, 10, 12 ),
              array(13, 16, 20 ));
 
$n = 3;
$x = 21;
 
echo "Count = ",
      countPairs($mat1, $mat2,
                 $n, $x);
                  
// This code is contributed by ajit.
?>

Javascript

<script>
 
// Javascript implementation to count 
// pairs from two sorted matrices 
// whose sum is equal to a given
// value x
//int SIZE= 10;
// function returns the row index no of largest
// element smaller than equal to 'x' in first
// column of mat[][]. If no such element exists 
// then it returns -1.
function binarySearchOnRow(mat, l, h, x)
{
    while (l <= h)
    {
        var mid = parseInt((l + h) / 2);
 
        // if 'x' is greater than or 
        // equal to mat[mid][0], then 
        // search in mat[mid+1...h][0]
        if (mat[mid][0] <= x)
            l = mid + 1;
 
        // else search in mat[l...mid-1][0]
        else
            h = mid - 1;
    }
 
    // required row index number
    return h;
}
 
// function to search 'val' in mat[row][]
function binarySearchOnCol(mat, l, h, val, row)
{
    while (l <= h)
    {
        var mid = parseInt((l + h) / 2);
 
        // 'val' found
        if (mat[row][mid] == val)
            return true;
 
        // search in mat[row][mid+1...h]
        else if (mat[row][mid] < val)
            l = mid + 1;
 
        // search in mat[row][l...mid-1]
        else
            h = mid - 1;
    }
 
    // 'val' not found
    return false;
}
 
// function to search 'val' in mat[][]
// returns true if 'val' is present
// else false
function searchValue(mat, n, val)
{
    // to get the row index number 
    // of the largest element smaller 
    // than equal to 'val' in mat[][]
    var row_no = binarySearchOnRow(mat, 0, n - 1, val);
 
    // if no such row exists, then
    // 'val' is not present
    if (row_no == -1)
        return false;
 
    // to search 'val' in mat[row_no][]
    return binarySearchOnCol(mat, 0, n - 1, val, row_no);
}
 
// function to count pairs from 
// two sorted matrices whose sum 
// is equal to a given value x
function countPairs(mat1, mat2, n, x)
{
    var count = 0;
 
    for (var i = 0; i < n; i++)
        for (var j = 0; j < n; j++)
        {
            // if value (x-mat1[i][j]) is found in mat2[][]
            if (searchValue(mat2, n, x - mat1[i][j]))
                count++;
        } 
    // required count of pairs
    return count;
}
 
// Driver program 
var mat1 = [ [ 1, 5, 6 ],
                [ 8, 10, 11 ],
                [ 15, 16, 18 ] ];
var mat2 = [ [ 2, 4, 7 ],
                [ 9, 10, 12 ],
                [ 13, 16, 20 ] ];
var n = 3;
var x = 21;
document.write( "Count = " +
                countPairs(mat1, mat2, n, x));
     
 
</script>

Output:

Count = 4

Time Complexity: (n²log₂n).
Auxiliary Space: O(1).

Method 3 (Hashing): Create a hash table and insert all the elements of mat2[][] in it. Now for each element ele of mat1[][] find (x – ele) in the hash table.

C++

// C++ implementation to count pairs from two
// sorted matrices whose sum is equal to a 
// given value x
#include <bits/stdc++.h>
 
using namespace std;
 
#define SIZE 10
 
// function to count pairs from two sorted matrices
// whose sum is equal to a given value x
int countPairs(int mat1[][SIZE], int mat2[][SIZE],
               int n, int x)
{
    int count = 0;
 
    // unordered_set 'us' implemented as hash table
    unordered_set<int> us;
 
    // insert all the elements of mat2[][] in 'us'
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            us.insert(mat2[i][j]);
 
    // for each element of mat1[][]
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
 
            // if (x-mat1[i][j]) is in 'us'
            if (us.find(x - mat1[i][j]) != us.end())
                count++;
 
    // required count of pairs
    return count;
}
 
// Driver program to test above
int main()
{
    int mat1[][SIZE] = { { 1, 5, 6 },
                         { 8, 10, 11 },
                         { 15, 16, 18 } };
 
    int mat2[][SIZE] = { { 2, 4, 7 },
                         { 9, 10, 12 },
                         { 13, 16, 20 } };
 
    int n = 3;
    int x = 21;
 
    cout << "Count = "
         << countPairs(mat1, mat2, n, x);
 
    return 0;
}

Java

import java.util.*;
 
// Java implementation to count pairs from two 
// sorted matrices whose sum is equal to a 
// given value x 
class GFG 
{
 
    // Java 
    static int SIZE = 10;
 
    // function to count pairs from two sorted matrices 
    // whose sum is equal to a given value x 
    static int countPairs(int mat1[][], int mat2[][],
                                        int n, int x) 
    {
        int count = 0;
 
        // unordered_set 'us' implemented as hash table 
        HashSet<Integer> us = new HashSet<>();
 
        // insert all the elements of mat2[][] in 'us' 
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                us.add(mat2[i][j]);
            }
        }
 
        // for each element of mat1[][] 
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++) // if (x-mat1[i][j]) is in 'us' 
            {
                if (us.contains(x - mat1[i][j])) 
                {
                    count++;
                }
            }
        }
 
        // required count of pairs 
        return count;
    }
 
    // Driver code 
    public static void main(String[] args) 
    {
        int mat1[][] = {{1, 5, 6},
                        {8, 10, 11},
                        {15, 16, 18}};
 
        int mat2[][] = {{2, 4, 7},
                        {9, 10, 12},
                        {13, 16, 20}};
 
        int n = 3;
        int x = 21;
 
        System.out.println("Count = "
                + countPairs(mat1, mat2, n, x));
    }
}
 
/* This code contributed by PrinciRaj1992 */

Python3

# Python implementation to count pairs from two
# sorted matrices whose sum is equal to a 
# given value x
SIZE = 10
 
# function to count pairs from two sorted matrices
# whose sum is equal to a given value x
def countPairs(mat1, mat2, n, x):
    count = 0
     
    # unordered_set 'us' implemented as hash table
    us = set()
     
    # insert all the elements of mat2[][] in 'us'
    for i in range(n):
        for j in range(n):
            us.add(mat2[i][j])
             
    # for each element of mat1[][]
    for i in range(n):
        for j in range(n):
             
            # if (x-mat1[i][j]) is in 'us'
            if (x - mat1[i][j]) in us:
                count += 1
                 
    # required count of pairs
    return count
 
# Driver code
mat1 = [[1, 5, 6],[8, 10, 11],[ 15, 16, 18]]
 
mat2 = [[2, 4, 7],[9, 10, 12],[ 13, 16, 20]]
 
n = 3
x = 21
 
print("Count =",countPairs(mat1, mat2, n, x))
 
# This code is contributed by shubhamsingh10

C#

// C# implementation to count pairs from two 
// sorted matrices whose sum is equal to a 
// given value x 
using System;
using System.Collections.Generic;
 
class GFG 
{
 
    // C#
    static int SIZE = 10;
 
    // function to count pairs from two sorted matrices 
    // whose sum is equal to a given value x 
    static int countPairs(int [,]mat1, int [,]mat2,
                                        int n, int x) 
    {
        int count = 0;
 
        // unordered_set 'us' implemented as hash table 
        HashSet<int> us = new HashSet<int>();
 
        // insert all the elements of mat2[,] in 'us' 
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                us.Add(mat2[i,j]);
            }
        }
 
        // for each element of mat1[,] 
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++) // if (x-mat1[i,j]) is in 'us' 
            {
                if (us.Contains(x - mat1[i,j])) 
                {
                    count++;
                }
            }
        }
 
        // required count of pairs 
        return count;
    }
 
    // Driver code 
    public static void Main(String[] args) 
    {
        int [,]mat1 = {{1, 5, 6},
                        {8, 10, 11},
                        {15, 16, 18}};
 
        int [,]mat2 = {{2, 4, 7},
                        {9, 10, 12},
                        {13, 16, 20}};
 
        int n = 3;
        int x = 21;
 
        Console.WriteLine("Count = "
                + countPairs(mat1, mat2, n, x));
    }
}
 
// This code has been contributed by 29AjayKumar

Javascript

<script>
 
// Javascript implementation to count pairs from two
// sorted matrices whose sum is equal to a 
// given value x
 
var SIZE = 10;
 
// function to count pairs from two sorted matrices
// whose sum is equal to a given value x
function countPairs(mat1, mat2, n, x)
{
    var count = 0;
 
    // unordered_set 'us' implemented as hash table
    var us = new Set();
 
    // insert all the elements of mat2[][] in 'us'
    for (var i = 0; i < n; i++)
        for (var j = 0; j < n; j++)
            us.add(mat2[i][j]);
 
    // for each element of mat1[][]
    for (var i = 0; i < n; i++)
        for (var j = 0; j < n; j++)
 
            // if (x-mat1[i][j]) is in 'us'
            if (us.has(x - mat1[i][j]))
                count++;
 
    // required count of pairs
    return count;
}
 
// Driver program to test above
var mat1 = [ [ 1, 5, 6 ],
                     [ 8, 10, 11 ],
                     [ 15, 16, 18 ] ];
var mat2 = [ [ 2, 4, 7 ],
                     [ 9, 10, 12 ],
                     [ 13, 16, 20 ] ];
var n = 3;
var x = 21;
document.write( "Count = "
      + countPairs(mat1, mat2, n, x));
 
 
</script>

Output:

Count = 4

Time complexity: O(n²).
Auxiliary Space: O(n²).

Method 4 (Efficient Approach): From the top leftmost element traverse mat1[][] in forward direction (i.e., from the topmost row up to last, each row is being traversed from left to right) and from the bottom rightmost element traverse mat2[][] in backward direction (i.e, from the bottom row up to first, each row is being traversed from right to left). For each element e1 of mat1[][] and e2 of mat2[][] encountered, calculate val = (e1 + e2). If val == x, increment count. Else if val is less than x, move to next element of mat1[][] in forward direction. Else move to next element of mat2[][] in backward direction. Continue this process until either of the two matrices gets completely traversed.

C++

// C++ implementation to count pairs from two 
// sorted matrices whose sum is equal to a
// given value x
#include <bits/stdc++.h>
 
using namespace std;
 
#define SIZE 10
 
// function to count pairs from two sorted matrices
// whose sum is equal to a given value x
int countPairs(int mat1[][SIZE], int mat2[][SIZE],
                                    int n, int x)
{
    // 'r1' and 'c1' for pointing current element
    // of mat1[][]
    // 'r2' and 'c2' for pointing current element
    // of mat2[][]
    int r1 = 0, c1 = 0;
    int r2 = n - 1, c2 = n - 1;
 
    // while there are more elements
    // in both the matrices
    int count = 0;
    while ((r1 < n) && (r2 >= -1)) {
        int val = mat1[r1][c1] + mat2[r2][c2];
 
        // if true
        if (val == x) {
 
            // increment 'count'
            count++;
 
            // move mat1[][] column 'c1' to right
            // move mat2[][] column 'c2' to left
            c1++;
            c2--;
        }
 
        // if true, move mat1[][] column 'c1' to right
        else if (val < x)
            c1++;
 
        // else move mat2[][] column 'c2' to left
        else
            c2--;
 
        // if 'c1' crosses right boundary
        if (c1 == n) {
 
            // reset 'c1'
            c1 = 0;
 
            // increment row 'r1'
            r1++;
        }
 
        // if 'c2' crosses left boundary
        if (c2 == -1) {
 
            // reset 'c2'
            c2 = n - 1;
 
            // decrement row 'r2'
            r2--;
        }
    }
 
    // required count of pairs
    return count;
}
 
// Driver program to test above
int main()
{
    int mat1[][SIZE] = { { 1, 5, 6 },
                         { 8, 10, 11 },
                         { 15, 16, 18 } };
 
    int mat2[][SIZE] = { { 2, 4, 7 },
                         { 9, 10, 12 },
                         { 13, 16, 20 } };
 
    int n = 3;
    int x = 21;
 
    cout << "Count = "
         << countPairs(mat1, mat2, n, x);
 
    return 0;
}

Java

// java implementation to count 
// pairs from two  sorted 
// matrices whose sum is 
// equal to agiven value x
import java.io.*;
 
class GFG 
{
    int SIZE = 10;
     
    // function to count pairs from 
    // two sorted matrices whose sum 
    // is equal to a given value x
    static int countPairs(int mat1[][], int mat2[][],
                                        int n, int x)
    {
        // 'r1' and 'c1' for pointing current 
        // element of mat1[][]
        // 'r2' and 'c2' for pointing current 
        // element of mat2[][]
        int r1 = 0, c1 = 0;
        int r2 = n - 1, c2 = n - 1;
     
        // while there are more elements
        // in both the matrices
        int count = 0;
        while ((r1 < n) && (r2 >= 0)) 
        {
            int val = mat1[r1][c1] + mat2[r2][c2];
     
            // if true
            if (val == x) {
     
                // increment 'count'
                count++;
     
                // move mat1[][] column 'c1' to right
                // move mat2[][] column 'c2' to left
                c1++;
                c2--;
            }
     
            // if true, move mat1[][] 
            // column 'c1' to right
            else if (val < x)
                c1++;
     
            // else move mat2[][] column
            // 'c2' to left
            else
                c2--;
     
            // if 'c1' crosses right boundary
            if (c1 == n) {
     
                // reset 'c1'
                c1 = 0;
     
                // increment row 'r1'
                r1++;
            }
     
            // if 'c2' crosses left boundary
            if (c2 == -1) {
     
                // reset 'c2'
                c2 = n - 1;
     
                // decrement row 'r2'
                r2--;
            }
        }
     
        // required count of pairs
        return count;
    }
     
    // Driver code 
    public static void main (String[] args) 
    {
        int mat1[][] = { { 1, 5, 6 },
                         { 8, 10, 11 },
                         { 15, 16, 18 } };
 
        int mat2[][] = { { 2, 4, 7 },
                         { 9, 10, 12 },
                         { 13, 16, 20 } };
     
        int n = 3;
        int x = 21;
     
        System.out.println ( "Count = " + 
                            countPairs(mat1, mat2, n, x));
             
    }
}
 
// This article is contributed by vt_m

Python3

# Python implementation to count pairs from two 
# sorted matrices whose sum is equal to a
# given value x
 
SIZE = 10
 
# function to count pairs from two sorted matrices
# whose sum is equal to a given value x
def countPairs(mat1, mat2, n, x):
     
    # 'r1' and 'c1' for pointing current element
    # of mat1[][]
    # 'r2' and 'c2' for pointing current element
    # of mat2[][]
    r1 = 0
    c1 = 0
    r2 = n - 1
    c2 = n - 1
     
    # while there are more elements
    # in both the matrices
    count = 0
    while ((r1 < n) and (r2 >= -1)):
         
        val = mat1[r1][c1] + mat2[r2][c2]
         
        # if true
        if (val == x):
             
            # increment 'count'
            count += 1
             
            # move mat1[][] column 'c1' to right
            # move mat2[][] column 'c2' to left
            c1 += 1
            c2 -= 1
             
        # if true, move mat1[][] column 'c1' to right
        elif (val < x):
            c1 += 1
         
        # else move mat2[][] column 'c2' to left
        else:
            c2 -= 1
             
        # if 'c1' crosses right boundary
        if (c1 == n):
             
            # reset 'c1'
            c1 = 0
             
            # increment row 'r1'
            r1 += 1
             
        # if 'c2' crosses left boundary
        if (c2 == -1):
             
            # reset 'c2'
            c2 = n - 1
             
            # decrement row 'r2'
            r2 -= 1
             
    # required count of pairs
    return count
 
# Driver program to test above
mat1 = [ [1, 5, 6] ,[8, 10, 11 ],[15, 16, 18 ]]
 
mat2 = [[2, 4, 7],[ 9, 10, 12],[13, 16, 20]]
 
n = 3
x = 21
 
print("Count =",countPairs(mat1, mat2, n, x))
 
# This code is contributed by shubhamsingh10

C#

// C# implementation to count pairs
// from two sorted matrices whose 
// sum is equal to a given value x
using System;
 
class GFG {
 
    // function to count pairs from 
    // two sorted matrices whose sum 
    // is equal to a given value x
    static int countPairs(int [,]mat1,
            int [,]mat2, int n, int x)
    {
         
        // 'r1' and 'c1' for pointing
        // current element of mat1[][]
        // 'r2' and 'c2' for pointing
        // current element of mat2[][]
        int r1 = 0, c1 = 0;
        int r2 = n - 1, c2 = n - 1;
     
        // while there are more elements
        // in both the matrices
        int count = 0;
        while ((r1 < n) && (r2 >= -1)) 
        {
            int val = mat1[r1,c1] 
                          + mat2[r2,c2];
     
            // if true
            if (val == x) {
     
                // increment 'count'
                count++;
     
                // move mat1[][] column 
                // 'c1' to right
                // move mat2[][] column 
                // 'c2' to left
                c1++;
                c2--;
            }
     
            // if true, move mat1[][] 
            // column 'c1' to right
            else if (val < x)
                c1++;
     
            // else move mat2[][] column
            // 'c2' to left
            else
                c2--;
     
            // if 'c1' crosses right
            // boundary
            if (c1 == n) {
     
                // reset 'c1'
                c1 = 0;
     
                // increment row 'r1'
                r1++;
            }
     
            // if 'c2' crosses left
            // boundary
            if (c2 == -1) {
     
                // reset 'c2'
                c2 = n - 1;
     
                // decrement row 'r2'
                r2--;
            }
        }
     
        // required count of pairs
        return count;
    }
     
    // Driver code 
    public static void Main () 
    {
        int [,]mat1 = { { 1, 5, 6 },
                        { 8, 10, 11 },
                        { 15, 16, 18 } };
 
        int [,]mat2 = { { 2, 4, 7 },
                        { 9, 10, 12 },
                        { 13, 16, 20 } };
     
        int n = 3;
        int x = 21;
     
        Console.Write ( "Count = " + 
            countPairs(mat1, mat2, n, x));
             
    }
}
 
// This code is contributed by 
// nitin mittal

PHP

<?php
// PHP implementation to count pairs  
// from two sorted matrices whose sum 
// is equal to a given value x
 
// function to count pairs from two 
// sorted matrices whose sum is equal 
// to a given value x
function countPairs(&$mat1, &$mat2, $n, $x)
{
    // 'r1' and 'c1' for pointing 
    // current element of mat1[][]
    // 'r2' and 'c2' for pointing 
    // current element of mat2[][]
    $r1 = 0;
    $c1 = 0;
    $r2 = $n - 1;
    $c2 = $n - 1;
 
    // while there are more elements
    // in both the matrices
    $count = 0;
    while (($r1 < $n) && ($r2 >= -1)) 
    {
        $val = $mat1[$r1][$c1] + 
               $mat2[$r2][$c2];
 
        // if true
        if ($val == $x) 
        {
 
            // increment 'count'
            $count++;
 
            // move mat1[][] column 'c1' to right
            // move mat2[][] column 'c2' to left
            $c1++;
            $c2--;
        }
 
        // if true, move mat1[][] 
        // column 'c1' to right
        else if ($val < $x)
            $c1++;
 
        // else move mat2[][] column
        // 'c2' to left
        else
            $c2--;
 
        // if 'c1' crosses right boundary
        if ($c1 == $n)
        {
 
            // reset 'c1'
            $c1 = 0;
 
            // increment row 'r1'
            $r1++;
        }
 
        // if 'c2' crosses left boundary
        if ($c2 == -1)
        {
 
            // reset 'c2'
            $c2 = $n - 1;
 
            // decrement row 'r2'
            $r2--;
        }
    }
 
    // required count of pairs
    return $count;
}
 
// Driver Code
$mat1 = array(array(1, 5, 6 ),
              array(8, 10, 11 ),
              array(15, 16, 18 ));
 
$mat2 = array(array(2, 4, 7),
               array(9, 10, 12),
              array(13, 16, 20 ));
 
$n = 3;
$x = 21;
 
echo ("Count = ");
echo countPairs($mat1, $mat2, $n, $x);
 
// This code is contributed 
// by Shivi_Aggarwal
?>

Javascript

<script>
 
// Javascript implementation to count
// pairs from two  sorted
// matrices whose sum is
// equal to agiven value x
let SIZE = 10;
  
// Function to count pairs from
// two sorted matrices whose sum
// is equal to a given value x
function countPairs(mat1, mat2, n, x)
{
     
    // 'r1' and 'c1' for pointing current
    // element of mat1[][]
    // 'r2' and 'c2' for pointing current
    // element of mat2[][]
    let r1 = 0, c1 = 0;
    let r2 = n - 1, c2 = n - 1;
  
    // While there are more elements
    // in both the matrices
    let count = 0;
    while ((r1 < n) && (r2 >= 0))
    {
        let val = mat1[r1][c1] + mat2[r2][c2];
  
        // If true
        if (val == x)
        {
             
            // Increment 'count'
            count++;
  
            // Move mat1[][] column 'c1' to right
            // move mat2[][] column 'c2' to left
            c1++;
            c2--;
        }
  
        // If true, move mat1[][]
        // column 'c1' to right
        else if (val < x)
            c1++;
  
        // Else move mat2[][] column
        // 'c2' to left
        else
            c2--;
  
        // If 'c1' crosses right boundary
        if (c1 == n) 
        {
             
            // Reset 'c1'
            c1 = 0;
  
            // Increment row 'r1'
            r1++;
        }
  
        // If 'c2' crosses left boundary
        if (c2 == -1)
        {
             
            // Reset 'c2'
            c2 = n - 1;
  
            // Decrement row 'r2'
            r2--;
        }
    }
  
    // Required count of pairs
    return count;
}
 
// Driver Code
let mat1 = [ [ 1, 5, 6 ],
             [ 8, 10, 11 ],
             [ 15, 16, 18 ] ];
 
let mat2 = [ [ 2, 4, 7 ],
             [ 9, 10, 12 ],
             [ 13, 16, 20 ] ];
 
let n = 3;
let x = 21;
 
document.write("Count = " +
           countPairs(mat1, mat2, n, x));
            
// This code is contributed by mukesh07 
 
</script>

Output:

Count = 4

Time Complexity: O(n²).
Auxiliary Space: O(1).

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!