chris chris - 3 months ago 10
Java Question

Find a sum pair in array with duplicates in O(n)

Array with duplicates

[4,4,1]
. Find pairs with sum
5
in
O(n)
.
Expected output
(4,1)
and
(4,1)
and count is
2
.

Approach#1:
Using
HashSet
:

public static int twoSum(int[] numbers, int target) {
HashSet<Integer> set = new HashSet<Integer>();
int c = 0;
for(int i:numbers){
if(set.contains(target-i)){
System.out.println(i+"-"+(target-i));
c++;
}
set.add(i);
}
return c;
}


Output is
1
.

Approach #2 as stated in this link:

private static final int MAX = 100000;

static int printpairs(int arr[],int sum)
{
int count = 0;
boolean[] binmap = new boolean[MAX];
for (int i=0; i<arr.length; ++i)
{
int temp = sum-arr[i];
if (temp>=0 && binmap[temp])
{
count ++;
}
binmap[arr[i]] = true;
}
return count;
}


Output
1
.

However the
O(nlog n)
solution is using sorting the array:

public static int findPairs(int [] a, int sum){

Arrays.sort(a);
int l = 0;
int r = a.length -1;
int count = 0;
while(l<r){

if((a[l] + a[r]) == sum){
count ++;
System.out.println(a[l] + " "+ a[r]);
r--;
}
else if((a[l] + a[r])>sum ){
r--;
}else{
l++;
}
}
return count;
}


Can we get the solution in
O(n)
?

Answer

You can use your second approach - just change boolean to int:

public static void main(String[] args) {
    System.out.println(printPairs(new int[]{3, 3, 3, 3}, 6)); // 6
    System.out.println(printPairs(new int[]{4, 4, 1}, 5)); // 2
    System.out.println(printPairs(new int[]{1, 2, 3, 4, 5, 6}, 7)); // 3
    System.out.println(printPairs(new int[]{3, 3, 3, 3, 1, 1, 5, 5}, 6)); // 10
}

public static int printPairs(int arr[], int sum) {
    int count = 0;
    int[] quantity = new int[sum];
    for (int i = 0; i < arr.length; ++i) {
        int supplement = sum - arr[i];
        if (supplement >= 0) {
            count += quantity[supplement];
        }
        quantity[arr[i]]++; // You may need to check that arr[i] is in bounds
    }
    return count;
}
Comments