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 falsebool 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 xint 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 aboveint 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 valueimport 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# falsedef 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 xdef 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 programmat1 = [[ 1, 5, 6 ], [ 8, 10, 11 ], [ 15, 16, 18 ] ]mat2 = [ [ 2, 4, 7 ], [ 9, 10, 12 ], [ 13, 16, 20 ] ]n = 3x = 21print( "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 valueusing 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 valuelet SIZE = 10; // Function to search 'val' in mat[][]// returns true if 'val' is present// else falsefunction 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 xfunction 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 codelet 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(n4).
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 falsebool 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 xint 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 aboveint 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 ximport 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 xSIZE = 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 falsedef 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 xdef 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 Codeif __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 xusing 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 falsefunction 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 xfunction 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 falsefunction 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 xfunction 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: (n2log2n).
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 xint 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 aboveint 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 xSIZE = 10# function to count pairs from two sorted matrices# whose sum is equal to a given value xdef 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 codemat1 = [[1, 5, 6],[8, 10, 11],[ 15, 16, 18]]mat2 = [[2, 4, 7],[9, 10, 12],[ 13, 16, 20]]n = 3x = 21print("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 xvar SIZE = 10;// function to count pairs from two sorted matrices// whose sum is equal to a given value xfunction 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 abovevar 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(n2).
Auxiliary Space: O(n2).
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 xint 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 aboveint 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 ximport 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 xSIZE = 10# function to count pairs from two sorted matrices# whose sum is equal to a given value xdef 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 abovemat1 = [ [1, 5, 6] ,[8, 10, 11 ],[15, 16, 18 ]]mat2 = [[2, 4, 7],[ 9, 10, 12],[13, 16, 20]]n = 3x = 21print("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 xusing 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 xfunction 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 xlet SIZE = 10; // Function to count pairs from// two sorted matrices whose sum// is equal to a given value xfunction 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 Codelet 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(n2).
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
