Find all pairs with a given sum

Slug: find-all-pairs-whose-sum-is-x5808 Difficulty: Easy Id: 703128 Topic Tags: Arrays, Hash, Data Structures Company Tags: Amazon, MakeMyTrip, Facebook, United Health Group

Summary

Find all pairs with a given sum is an easy problem that involves finding two elements in an array whose sum equals the given target value. This problem can be solved using a simple hash table approach.

Detailed Explanation

The problem requires us to find all unique pairs of numbers from a given array that have a specific sum (target). We can solve this by creating a frequency count of each element in the array and then iterating over the array again to find the pairs.

Here is the step-by-step breakdown:

1. Create an empty hash table (HashMap) to store the frequency count of elements.
2. Iterate over the given array, and for each element:
   • Check if the difference between the target sum and the current element exists in the hash table.
   • If it does, that means we have found a pair whose sum equals the target; add this pair to our result set.
   • Update the frequency count of the current element in the hash table.

Time Complexity: O(n), where n is the size of the input array. Space Complexity: O(min(n,m)), where m is the maximum value in the array.

Optimized Solutions

Java

java
import java.util.*;

public class FindAllPairs {
    public static List<List<Integer>> findPairs(int[] arr, int target) {
        Map<Integer, Integer> freqMap = new HashMap<>();
        List<List<Integer>> result = new ArrayList<>();

        for (int num : arr) {
            int complement = target - num;
            if (freqMap.containsKey(complement)) {
                result.add(Arrays.asList(num, complement));
            }
            freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
        }

        return result;
    }
}

Python

python
def find_pairs(arr, target):
    freq_map = {}
    result = []

    for num in arr:
        complement = target - num
        if complement in freq_map:
            result.append([num, complement])
        freq_map[num] = freq_map.get(num, 0) + 1

    return result

C++

cpp
#include <iostream>
#include <unordered_map>
#include <vector>

std::vector<std::vector<int>> findPairs(int* arr, int size, int target) {
    std::unordered_map<int, int> freqMap;
    std::vector<std::vector<int>> result;

    for (int i = 0; i < size; i++) {
        int complement = target - arr[i];
        if (freqMap.find(complement) != freqMap.end()) {
            result.push_back({arr[i], complement});
        }
        freqMap[arr[i]] = freqMap.find(arr[i]) == freqMap.end() ? 1 : freqMap[arr[i]] + 1;
    }

    return result;
}

JavaScript

javascript
function findPairs(arr, target) {
    let freqMap = new Map();
    let result = [];

    for (let num of arr) {
        let complement = target - num;
        if (freqMap.has(complement)) {
            result.push([num, complement]);
        }
        freqMap.set(num, (freqMap.get(num) || 0) + 1);
    }

    return result;
}