Count pairs Sum in matrices

JavaView on GFG

Time: O(n^2)

Space: O(n^2)

Intuition

Count pairs (one from each matrix) whose sum equals a target. Sort one matrix, binary search or two-pointer.

Algorithm

1Flatten and sort matrix1. For each element in matrix2: binary search for (target - elem) in matrix1.

Common Pitfalls

•O(m*n * log(m*n)). Alternatively: one sorted ascending, one sorted descending, two-pointer on flattened arrays.

Count pairs Sum in matrices.java

Java

// Approach: Flatten both matrices and use a two-pointer or hash set approach to count pairs summing to target.
// Time: O(n^2) Space: O(n^2)
import java.util.*;

class Solution {
    int countPairs(int[][] mat1, int[][] mat2, int x) {
        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < mat2.length; i++) {
            for (int j = 0; j < mat2[0].length; j++) {
                set.add(mat2[i][j]);
            }
        }
        int count = 0;
        for (int i = 0; i < mat1.length; i++) {
            for (int j = 0; j < mat1[0].length; j++) {
                if (set.contains(x - mat1[i][j]))
                    count++;
            }
        }
        return count;
    }
}

Was this solution helpful?