Pair with given sum in matrix

0 0 5 minutes read

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 matrix
bool 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 code
int 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 sum
import java.util.*;
 
class GFG
{
     
// Function to check if a pair with 
// given sum exists in the matrix
static 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 code
public 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 sum
using System;
using System.Collections.Generic;
 
class GFG
{
     
// Function to check if a pair with 
// given sum exists in the matrix
static 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 code
public 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 sum
 
N= 4
M= 4
 
# Function to check if a pair with given sum
# exists in the matrix
def 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 code
if __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 matrix
function 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 zambiatek!