5 Best Ways to Find All Distinct Pairs With Difference Equal to k in Python

by

💡 Problem Formulation: We aim to identify all the unique pairs of numbers within a given array where the absolute difference between them is a specific value k. For instance, given the input array [1, 5, 3, 4, 2] and a difference value k = 3, the desired output would be a list of pairs such as [(1, 4), (2, 5)], where each pair differs by 3.

Method 1: Brute Force Approach

The brute force approach involves checking each pair in the array to see if it meets the difference criterion. It’s straightforward but inefficient for large arrays. The function can be written to iterate over each element, comparing them to find pairs with the exact difference k.

♥️ Info: Are you AI curious but you still have to create real impactful projects? Join our official AI builder club on Skool (only $5): SHIP! - One Project Per Month

Here’s an example:

def find_pairs_with_difference(arr, k):
    pairs = []
    for i in range(len(arr)):
        for j in range(i+1, len(arr)):
            if abs(arr[i] - arr[j]) == k:
                pairs.append((arr[i], arr[j]))
    return pairs

print(find_pairs_with_difference([1, 5, 3, 4, 2], 3))

Output: [(1, 4), (2, 5)]

This method iterates through each element, using a nested loop to check every possible pair in the array for the desired difference. Although simple, the time complexity is O(n^2), making it inefficient for larger datasets.

Method 2: Using Set for Lookup

This method improves efficiency by using a set for constant-time lookups. We iterate through the array and for each element, check if element plus or minus k is in the set. It provides a significant performance improvement over the brute force approach.

Here’s an example:

def find_pairs_with_difference(arr, k):
    pairs = set()
    elements = set(arr)
    for num in arr:
        if num + k in elements:
            pairs.add((num, num + k))
        if num - k in elements:
            pairs.add((num - k, num))
    return list(pairs)

print(find_pairs_with_difference([1, 5, 3, 4, 2], 3))

Output: [(4, 1), (2, 5)]

This snippet creates a set of elements for O(1) lookups. We then iterate through the array once, leading to a time complexity of O(n), and only add pairs that meet the criteria to the output set, ensuring uniqueness.

Method 3: Sorting and Binary Search

In this method, we sort the array and then use binary search to look for the complement (current element ± k). This method benefits from the sorting properties and efficient searching but has a pre-processing cost.

Here’s an example:

import bisect

def find_pairs_with_difference(arr, k):
    pairs = set()
    arr.sort()
    for i in range(len(arr)):
        if bisect.bisect_left(arr, arr[i] + k, i+1) < len(arr):
            pairs.add((arr[i], arr[i] + k))
    return list(pairs)

print(find_pairs_with_difference([1, 5, 3, 4, 2], 3))

Output: [(1, 4), (2, 5)]

Post sorting, this code utilizes the bisect_left function to perform a binary search, reducing the time complexity for search after sorting to O(log n). However, the initial sort incurs O(n log n) cost.

Method 4: Hash Map (Dictionary) Lookup

Hash maps or dictionaries in Python offer O(1) average time complexity for lookups. This method leverages a dictionary to store each number’s occurrence and then iterates through the keys to find potential pairs.

Here’s an example:

def find_pairs_with_difference(arr, k):
    pairs = set()
    element_dict = {num: True for num in arr}
    for num in element_dict:
        if num + k in element_dict:
            pairs.add((num, num + k))
    return list(pairs)

print(find_pairs_with_difference([1, 5, 3, 4, 2], 3))

Output: [(1, 4), (2, 5)]

By creating a dictionary from the array elements, we can iterate over the dictionary’s keys and check for the existence of the complement. While the dictionary setup has a one-time cost, each lookup and insertion is O(1).

Bonus One-Liner Method 5: List Comprehension with a Set

For those who prefer concise Pythonic solutions, a single-line method applies list comprehension and a set to derive the distinct pairs quickly.

Here’s an example:

pairs = lambda arr, k: list({(min(a,b), max(a,b)) for a in arr for b in arr if abs(a-b) == k})

print(pairs([1, 5, 3, 4, 2], 3))

Output: [(1, 4), (2, 5)]

The one-liner features a set comprehension to ensure uniqueness and generates pairs by going through each element with every other, applying the condition inline.

Summary/Discussion

  • Method 1: Brute Force. Simple method; good for small arrays. Inefficient for larger arrays with O(n^2) complexity.
  • Method 2: Set for Lookup. Efficient with O(n) complexity. Easy to understand and requires minimal code changes from brute force to optimisation.
  • Method 3: Sorting and Binary Search. Efficient search O(log n) after sorting. Pre-processing sort incurs O(n log n), which can be costly for large, unsorted arrays.
  • Method 4: Hash Map Lookup. Highly efficient and fast for lookups. Minor overhead for dictionary creation, still maintains overall O(n) complexity.
  • Bonus Method 5: List Comprehension. Elegant and concise. Utilizes the power of Python’s list comprehension along with set for a one-liner solution.