Find pairs for a target sum in an array

Question

First there seems to lot of questions about this kind of problem but I couldn't find one that helps me.

I am trying find pairs of target with O(n) or linear time complexity.

int[] input = {1, 6, 3, 2, 5, 5, 7, 8, 4, 8, 2, 5, 9, 9, 1};
int target = 10;

Expected output (in any order):

(1,9)(1,9)(6,4)(3,7)(2,8)(2,8)(5,5)(5,5)(5,5)(8,2)(8,2)(9,1)(9,1)

I have tried bruteforce approach with two for loops and it gives me right output but O(n*n).

for (int i = 0; i < input.length; i++) {
    for (int j = i + 1; j < input.length; j++) {
        if (input[i] + input[j] == target) {
            System.out.println("(" + input[i] + "," + input[j] + ")");
        }
    }
}

Then I have tried the hashing which does not give all pairs. Two pairs are missing

Set<Integer> set = new HashSet<>();
for (int num : input) {
    set.add(num);
    if (set.contains(target - num)) {
        System.out.println("(" + (target - num) + "," + num + ")");
    }
}

Output:

(5,5)(5,5)(3,7)(2,8)(6,4)(2,8)(8,2)(5,5)(1,9)(1,9)(9,1)

I tried other approach which gave more pairs than expected

Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < input.length; i++) {
    map.put(input[i], i);
}

for (int num : input) {
    if (map.containsKey((target - num))) {
        System.out.println("(" + num + "," + (target - num) + ")");
    }
}

Output:

(1,9)(6,4)(3,7)(2,8)(5,5)(5,5)(7,3)(8,2)(4,6)(8,2)(2,8)(5,5)(9,1)(9,1)(1,9)

GURU Shreyansh GURU Shreyansh · Accepted Answer · 2021-06-25T16:08:27

The issue with HashMap is occurring because you are looking for a value and target multiple times as you have added all the array elements in the beginning.
For example: when the current map element num is 6, we found a pair as 4 (10-6) is there in the map.
Again when num is 4, we again found a pair as 6 (10-4) is there in the map.
So, to get the correct count and pairs, we need to check and add the numbers simultaneously.
Here is an O(N) implementation using HashMap.

class Solution
{
    static int getPairsCount(int[] arr, int n, int target)
    {
        HashMap<Integer,Integer> map = new HashMap<>();
        int pairs=0;
        for (int i=0; i<n; i++)
        {
            if (map.containsKey(target - arr[i]))
            {
                pairs += map.get(target - arr[i]);
                for (int j=1; j<=map.get(target - arr[i]); j++)
                    System.out.print("(" + (target-arr[i]) + "," + arr[i] + ") ");
            }
            map.put(arr[i] , map.getOrDefault(arr[i],0)+1);
        }
        return pairs;
    }
    public static void main (String [] args)
    {
        int[] input = {1, 6, 3, 2, 5, 5, 7, 8, 4, 8, 2, 5, 9, 9, 1};
        int target = 10;
        System.out.println(getPairsCount(input , input.length , target));
    }
}

Output: 13 (pairs)

(5,5) (3,7) (2,8) (6,4) (2,8) (8,2) (8,2) (5,5) (5,5) (1,9) (1,9) (9,1) (9,1)

And the issue with your HashSet approach is that it's removing the duplicate values and hence you are getting incorrect results.

Find pairs for a target sum in an array

1 Answers