Find pairs with given sum such that elements of pair are in different rows

Difficulty Level Medium
Frequently asked in Amazon DE Shaw Directi GreyOrange Indeed Pinterest Teradata
Array Hash MatrixViews 2606

Problem Statement

“Find pairs with given sum such that elements of pair are in different rows” problem states that you are given a matrix of integers and a value called “sum”. The problem statement asks to find out all the pairs in a matrix that sums up to a given value called sum and also both of the numbers should be from a different row. (Both of the numbers should not be from the same row).

Example

int matrix[][]= {{3, 4, 7, 2},

{8, 9, 1, 10},

{5, 4, 0, 4},

{12, 0, 1, 13}};



sum = 15
(3, 12), (7, 8), (2, 13), (10, 5)

Explanation: Each of the numbers of each pair is from a different row.

Algorithm to find pairs with given sum such that elements of pair are in different rows

1. Declare a map.
2. Put all the values of the matrix into the map with their row and column index.
3. Traverse the matrix.
  1. Set the remainingValue to the difference of sum and each value of the matrix.
  2. Check if the map contains the value of remainingValue if true then get its row and column index which we already put it into the map.
    1. Check if this row value is not equal to current i and also a row is greater than i.
      1. If true then print the matrix[i][j] and matrix[row][column].
4. Keep repeating the process until the whole matrix is traversed.

Explanation

We are given a matrix of integers. We have to find out all the pairs in a matrix such that the element of each pair has a sum equal to the given value. And also there is a condition given, the numbers we select in a pair should be from the different row in a matrix. If we continue solving it with the naive approach. And traverse each row in the element then it would take O (n4). We will solve it using the hashing or Map/HashMap. We will be declaring a map. Start traversing the matrix, and put the elements of the matrix into the map as a key. And its matrix element’s row and column index as a value.

We can put the row and column index’s value in a map using the make_pair method in C++. Or if we are using java we can create simply a class and that’s class objects we can store it into the map. Later on, if we have to get that value we will use that class object to get those row and column values.

The next thing we will be doing is traversing the matrix. In a nested loop, we will we picking up each element of the matrix and subtract it from the given sum value and store it the variable called remainingSum and check if the map contains this value if true then check for both the matrix’s current element and remainingSum should not belong to the same row, if all of the condition becomes true then print the elements of a pair and proceed for further traversing find out the all the pairs. We had also got that map’s row and column values as object form as we mentioned above in the explanation.

Find pairs with given sum such that elements of pair are in different rows

Code

C++ code to find pairs with given sum such that elements of pair are in different rows

#include<iostream>
#include<unordered_map>

using namespace std;

const int MAX = 100;

void makePairWithGivenSum (int matrix[][MAX], int n, int sum)
{
    unordered_map<int, pair<int, int> > MAP;
    for (int i=0; i<n; i++)
        for (int j=0; j<n; j++)
            MAP[matrix[i][j]] = make_pair(i, j);

    for (int i=0; i<n; i++)
    {
        for (int j=0; j<n; j++)
        {
            int remainingSum = sum - matrix[i][j];
            auto it = MAP.find(remainingSum);

            if (it != MAP.end())
            {
                pair<int, int> p = it->second;
                int row = p.first, col = p.second;
                if (row != i && row > i)
                    cout << "(" << matrix[i][j] << ", "
                         << matrix[row][col] << "), ";
            }
        }
    }
}
int main()
{
    int n = 4, sum = 11;
    int matrix[][MAX]= {{3, 4, 7, 2},
        {8, 9, 1, 10},
        {5, 4, 0, 4},
        {12, 0, 1, 13}
    };
    makePairWithGivenSum (matrix, n, sum);
    return 0;
}

(3, 8), (7, 4), (2, 9), (10, 1),

Java code to find pairs with given sum such that elements of pair are in different rows

import java.util.HashMap;
class Pair
{
    int first, second;
    Pair(int first, int second)
    {
        this.first=first;
        this.second=second;
    }
}
class pairSum
{
    public static void makePairWithGivenSum(int matrix[][], int n, int sum)
    {
        HashMap<Integer, Pair > MAP=new HashMap<Integer, Pair>();
        for (int i=0; i<n; i++)
        {
            for (int j=0; j<n; j++)
            {
                MAP.put(matrix[i][j], new Pair(i,j));
            }
        }
        for (int i=0; i<n; i++)
        {
            for (int j=0; j<n; j++)
            {
                int remainingSum = sum - matrix[i][j];

                if (MAP.containsKey(remainingSum))
                {
                    Pair p = MAP.get(remainingSum);
                    int row = p.first, col = p.second;
                    if (row != i && row > i)
                        System.out.print("(" + matrix[i][j] + ", " + matrix[row][col] + "), ");

                }
            }
        }
    }
    public static void main(String [] args)
    {
        int n = 4, sum = 15;
        int matrix[][]= {{3, 4, 7, 2},
            {8, 9, 1, 10},
            {5, 4, 0, 4},
            {12, 0, 1, 13}
        };
        makePairWithGivenSum (matrix, n, sum);
    }
}

(3, 12), (7, 8), (2, 13), (10, 5),

Complexity Analysis

Time Complexity

We are traversing the matrix and since we are using HashMap, we are able to achieve O(n2) where “n” is the number of elements in the matrix.

Space Complexity

O(N) where “N” is the number of elements in the matrix.

Translate »