Python - Find All Pairs in an Array Whose Sum Equals a Given Number

Python – Find All Pairs in an Array Whose Sum Equals a Given Number

This tutorial explains how to find all pairs in an array that add up to a given target sum. We will look into problem statement, sample data, and Python Program.

Problem Statement

Given an array arr and a target sum target, find all unique pairs (a, b) in the array such that a + b = target. Each pair should be reported only once.

Sample Input and Output

Example 1:

</>

Copy

Input: arr = [1, 2, 3, 4, 5], target = 6
Output: [(1, 5), (2, 4)]

Example 2:

</>

Copy

Input: arr = [2, 4, 3, 5, 7, 8, 9], target = 7
Output: [(2, 5), (4, 3)]

Solution Steps

Understand the Problem: Identify that you need to find pairs (a, b) such that a + b = target.
Brute Force Approach: Use two nested loops to check every possible pair in the array. This method has a time complexity of O(n²).
Optimized Approach: Use a dictionary (hash map) to store elements and look for the complement (i.e., target - current_element) in a single pass, which reduces the time complexity to O(n).
Handle Edge Cases: Ensure that duplicate pairs are not reported multiple times.

Python Program

Method 1: Brute Force Approach

</>

Copy

# Function to find all pairs using a brute force method
def find_pairs_bruteforce(arr, target):
    pairs = []
    n = len(arr)
    for i in range(n):
        for j in range(i + 1, n):
            if arr[i] + arr[j] == target:
                pairs.append((arr[i], arr[j]))
    return pairs

# Sample Input
arr1 = [1, 2, 3, 4, 5]
target1 = 6
print("Brute Force Method Output:", find_pairs_bruteforce(arr1, target1))

Output:

Brute Force Method Output: [(1, 5), (2, 4)]

Method 2: Using a Dictionary for Optimization

This method uses a dictionary to track elements that have been seen and to check if the complement (target - element) exists in the dictionary. This approach efficiently finds pairs in a single pass through the array.

</>

Copy

# Function to find all pairs using a dictionary
def find_pairs_dict(arr, target):
    pairs = []
    seen = {}
    for num in arr:
        complement = target - num
        # If the complement exists and its count is positive, we found a pair
        if complement in seen and seen[complement] > 0:
            pairs.append((complement, num))
            seen[complement] -= 1  # Decrement count to avoid duplicate pairs
        else:
            seen[num] = seen.get(num, 0) + 1
    return pairs

# Sample Input
arr2 = [2, 4, 3, 5, 7, 8, 9]
target2 = 7
print("Dictionary Method Output:", find_pairs_dict(arr2, target2))

Output:

Dictionary Method Output: [(2, 5), (4, 3)]

Conclusion

In this tutorial, we explored two approaches to solve the problem of finding all pairs in an array whose sum equals a given number:

Brute Force Approach: A straightforward method using nested loops. Although easy to understand, it is less efficient for larger arrays.
Dictionary Approach: Uses a hash map to check for the complement of each element in one pass, making it more efficient for larger datasets.

TutorialKart

Python – Find All Pairs in an Array Whose Sum Equals a Given Number