Hashing for pair - 1

Summary

Given an array of integers, find all unique pairs that sum up to a given target value. This problem involves using hashing as a fundamental concept in computer science.

Detailed Explanation

To solve this problem, we can use a hash map (or dictionary) to store the elements from the array as keys and their indices as values. Then, for each element in the array, check if the difference between the target value and the current element exists in the hash map. If it does, it means we have found a pair that sums up to the target value.

Here's a step-by-step breakdown of the solution:

1. Initialize an empty hash map.
2. Iterate through each element in the array.
3. For each element, calculate its difference with the target value.
4. Check if this difference exists as a key in the hash map.
5. If it does, retrieve the index associated with this difference and print out the pair (current element, element at the retrieved index).
6. Continue until all elements have been processed.

Time complexity: O(n), where n is the size of the array. Space complexity: O(n), for storing the hash map.

Optimized Solutions

Java

java
import java.util.HashMap;
import java.util.Map;

public class PairSum {
    public static void findPairs(int[] arr, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            int diff = target - arr[i];
            if (map.containsKey(diff)) {
                System.out.println("(" + arr[i] + ", " + arr[map.get(diff)] + ")");
            }
            map.put(arr[i], i);
        }
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        int target = 7;
        findPairs(arr, target);
    }
}

Python

python
def find_pairs(arr, target):
    map = {}
    for i in range(len(arr)):
        diff = target - arr[i]
        if diff in map:
            print((arr[i], arr[map[diff]]))
        map[arr[i]] = i

arr = [1, 2, 3, 4, 5]
target = 7
find_pairs(arr, target)

C++

cpp
#include <iostream>
#include <unordered_map>

void findPairs(int* arr, int size, int target) {
    std::unordered_map<int, int> map;
    for (int i = 0; i < size; i++) {
        int diff = target - arr[i];
        if (map.find(diff) != map.end()) {
            std::cout << "(" << arr[i] << ", " << arr[map[diff]] << ")" << std::endl;
        }
        map[arr[i]] = i;
    }
}

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int size = sizeof(arr) / sizeof(arr[0]);
    int target = 7;
    findPairs(arr, size, target);
    return 0;
}

JavaScript

javascript
function findPairs(arr, target) {
    let map = new Map();
    for (let i = 0; i < arr.length; i++) {
        let diff = target - arr[i];
        if (map.has(diff)) {
            console.log(`(${arr[i]}, ${arr[map.get(diff)]})`);
        }
        map.set(arr[i], i);
    }
}

let arr = [1, 2, 3, 4, 5];
let target = 7;
findPairs(arr, target);