How do I account for duplicate values when solving the the two sum problem using a hash table?

Question

Say I have the classic Two Sum Problem but with a twist

If I am given a list of integers and target

I need to print all the pairs of values that add up to the sum

Without repeating symmetrical values

Without reusing a value

I am trying to avoid the brute force approach for obvious reasons, but if I implement a hash-map with each value as the key and the element being the frequency of that value in the original array. How do I get the algorithm to only print each value pair once?

function findPairs(arr, target){

  let hashMap = {};

  let results = [];

  for(let i = 0; i < arr.length; i++){
    if(hashMap.hasOwnProperty(arr[i])){
      hashMap[arr[i]]++;
    }else{
      hashMap[arr[i]] = 1;
    }
  }

  for(let i = 0; i < arr.length; i++){

    let diff = target - arr[i];

    if(hashMap.hasOwnProperty(diff) && hashMap[diff] > 0){ 
        results.push([arr[i], diff]);
        hashMap[diff]--;
    }
  }

  console.log(results);

}

findPairs([1, 3, -1, 11, 7], 10);
findPairs([5, 5, 5, 5, 5], 10);

findPairs([1, 3, -1, 11, 7], 10)

(3, 7) (-1, 11)

findPairs([5, 5, 5], 10)

(5, 5)

findPairs([5, 5, 5, 5], 10)

(5, 5) (5, 5)

findPairs([5, 5, 5, 5, 5], 10)

(5, 5) (5, 5)

findPairs([5, 5, 5, 5, 5, 5 ], 10)

(5, 5) (5, 5) (5, 5)

Answer 1

This is the summary of the question as far as I understood:

• Your array can have duplicate elements eg:- [1, 2, 3, 2, 4]

• You want to print duplicate [4, 1, 2, 3, 2, 4] as (2, 4), (2, 4)

  vector<pair<int, int> > findPairs(vector<int> arr, int target){
      int size = arr.size();
      map<int, int> hashMap;
  
      for(int i = 0; i < size; i++){
              // C++ map assigns 0 as default if the key is not present, C++ map uses Red Black Tree 
              if(hashMap[arr[i]] == 0)
                      hashMap[arr[i]] = 1;
              else
                      hashMap[arr[i]]++;
      }
      /** Use to store result in (int, int) form
       *  Vector is a Dynamic array
       */
      vector<pair<int, int> > results;
      for(int i = 0; i < size; i++){
              int diff = target - arr[i];
              hashMap[arr[i]]--;
              if(hashMap[diff] >= 1)
                      results.push_back(make_pair(arr[i], diff));
              hashMap[diff]--;
      }
      return results;
  

  }

This code is based on the examples you have provided in the question.