Find a Specific Pair in Matrix

Understanding the Problem

The goal is to find a specific pair of elements in a matrix that adds up to a given sum.

Method 1: Brute Force

This method checks all pairs in the matrix.

def find_pair(matrix, target):
    rows = len(matrix)
    cols = len(matrix[0])

    for i in range(rows):
        for j in range(cols):
            for k in range(i, rows):
                for l in range(j + 1 if k == i else 0, cols):
                    if matrix[i][j] + matrix[k][l] == target:
                        print(f"Pair found: ({matrix[i][j]}, {matrix[k][l]})")
                        return True
    return False

# Example usage
matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]
target = 10
if not find_pair(matrix, target):
    print("No pair found.")
            

Output:

Pair found: (1, 9)

Method 2: Using Hashing

This method uses a hash table to store elements and check for pairs.

def find_pair(matrix, target):
    elements = set()

    for row in matrix:
        for num in row:
            complement = target - num
            if complement in elements:
                print(f"Pair found: ({num}, {complement})")
                return True
            elements.add(num)
    return False

# Example usage
matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]
target = 10
if not find_pair(matrix, target):
    print("No pair found.")
            

Output:

Pair found: (1, 9)

Method 3: Using Two-Pointer Technique

This method assumes the matrix is sorted and uses two pointers to find pairs.

def find_pair(matrix, target):
    rows = len(matrix)
    cols = len(matrix[0])
    left, right = 0, rows * cols - 1

    while left < right:
        sum = matrix[left // cols][left % cols] + matrix[right // cols][right % cols]
        if sum == target:
            print(f"Pair found: ({matrix[left // cols][left % cols]}, {matrix[right // cols][right % cols]})")
            return True
        elif sum < target:
            left += 1
        else:
            right -= 1
    return False

# Example usage
matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]
target = 10
if not find_pair(matrix, target):
    print("No pair found.")
            

Output:

Pair found: (1, 9)