Given a NxM matrix and a sum S. The task is to check if a pair with given Sum exists in the matrix or not.
Examples:
Input: mat[N][M] = {{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12},
{13, 14, 15, 16}};
sum = 31
Output: YES
Input: mat[N][M] = {{1, 2, 3, 4},
{5, 6, 7, 8}};
sum = 150
Output: NO
Approach:
- Take a hash to store all elements of the matrix in the hash.
- Start traversing through the matrix, and while traversing check if abs(sum-matrix_element) is present in the hash.
- If present, then return true, else insert the current matrix element into the hash.
- If all elements of the matrix are traversed and no pair is found, return false.
Below is the implementation of the above approach:
C++
// CPP code to check for pair with given sum#include <bits/stdc++.h>using namespace std;#define N 4#define M 4// Function to check if a pair with given sum// exists in the matrixbool isPairWithSum(int mat[N][M], int sum){ // hash to store elements unordered_set<int> s; // looping through elements // if present in the matrix // return true, else push // the element in matrix for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { if (s.find(sum - mat[i][j]) != s.end()) { return true; } else { s.insert(mat[i][j]); } } } return false;}// Driver codeint main(){ // Input matrix int mat[N][M] = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 }, { 13, 14, 15, 16 } }; // given sum int sum = 11; if (isPairWithSum(mat, sum)) { cout << "YES" << endl; } else cout << "NO" << endl; return 0;} |
Java
// Java code to check for pair// with given sumimport java.util.*;class GFG{ // Function to check if a pair with // given sum exists in the matrixstatic final int N = 4;static final int M = 4;static boolean isPairWithSum(int [][]mat, int sum){ // hash to store elements Set<Integer> s = new HashSet<Integer>(); // looping through elements // if present in the matrix // return true, else push // the element in matrix for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { if (s.contains(sum - mat[i][j])) { return true; } else { s.add(mat[i][j]); } } } return false;}// Driver codepublic static void main(String []args){ // Input matrix int [][]mat = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 }, { 13, 14, 15, 16 } }; // given sum int sum = 11; if (isPairWithSum(mat, sum)) { System.out.println("YES"); } else System.out.println("NO");}}// This code is contributed by ihritik |
C#
// C# code to check for pair// with given sumusing System;using System.Collections.Generic;class GFG{ // Function to check if a pair with // given sum exists in the matrixstatic readonly int N = 4;static readonly int M = 4;static bool isPairWithSum(int [,]mat, int sum){ // hash to store elements HashSet<int> s = new HashSet<int>(); // looping through elements // if present in the matrix // return true, else push // the element in matrix for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { if (s.Contains(sum - mat[i, j])) { return true; } else { s.Add(mat[i, j]); } } } return false;}// Driver codepublic static void Main(String []args){ // Input matrix int [,]mat = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 }, { 13, 14, 15, 16 } }; // given sum int sum = 11; if (isPairWithSum(mat, sum)) { Console.WriteLine("YES"); } else Console.WriteLine("NO");}}// This code contributed by Rajput-Ji |
Python3
# python code to check for pair with given sumN= 4M= 4# Function to check if a pair with given sum# exists in the matrixdef isPairWithSum(mat, sum): # hash to store elements s = set() # looping through elements # if present in the matrix # return true, else push # the element in matrix for i in range(N): for j in range(M): if (sum - mat[i][j]) in s : return True else : s.add(mat[i][j]) return False# Driver codeif __name__ == '__main__': # Input matrix mat = [[ 1, 2, 3, 4 ], [ 5, 6, 7, 8] , [ 9, 10, 11, 12] , [13, 14, 15, 16]] # given sum sum = 11 if (isPairWithSum(mat, sum)) : print("YES") else: print("NO") # This code is contributed by AbhiThakur |
PHP
<?php // PHP code to check for pair with given sum $N = 4;$M = 4; // Function to check if a pair with given sum// exists in the matrixfunction isPairWithSum(&$mat, $sum){ global $N,$M; // array to store elements $s = array(); // looping through elements // if present in the matrix // return true, else push // the element in matrix for ($i = 0; $i < $N; $i++) { for ($j = 0; $j < $M; $j++) { if (in_array($sum - $mat[$i][$j],$s) != end($s)) { return true; } else { array_push($s,$mat[$i][$j]); } } } return false;} // Driver code // Input matrix $mat = array(array( 1, 2, 3, 4 ), array( 5, 6, 7, 8 ), array( 9, 10, 11, 12 ), array(13, 14, 15, 16 )); // given sum $sum = 11; if (isPairWithSum($mat, $sum)) { echo "YES" ."\n"; } else echo "NO" ."\n"; return 0;?> |
Javascript
<script>// Javascript code to check for pair// with given sum // Function to check if a pair with // given sum exists in the matrix let N = 4; let M = 4; function isPairWithSum(mat,sum) { // hash to store elements let s = new Set(); // looping through elements // if present in the matrix // return true, else push // the element in matrix for (let i = 0; i < N; i++) { for (let j = 0; j < M; j++) { if (s.has(sum - mat[i][j])) { return true; } else { s.add(mat[i][j]); } } } return false; } // Driver code // Input matrix let mat = [[ 1, 2, 3, 4 ], [ 5, 6, 7, 8] , [ 9, 10, 11, 12] , [13, 14, 15, 16]] ; // given sum let sum = 11; if (isPairWithSum(mat, sum)) { document.write("YES"); } else document.write("NO"); // This code is contributed by rag2127</script> |
Output
YES
Time Complexity: O(N*M)
Auxiliary Space: O(N*M)
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!
