java - Count pairs from an array whose sum is equal to a given number?

Question

I just had an online coding interview and one of the questions asked there is for a given array of integers, find out the number of pairs whose summation is equal to a certain number (passed as parameter inside the method ). For example an array is given as,

int[] a = {3, 2, 1, 45, 27, 6, 78, 9, 0};
int k = 9; // given number

So, there will be 2 pairs (3, 6) and (9, 0) whose sum is equal to 9. It's good to mention that how the pairs are formed doesn't matter. The means (3,6) and (6,3) will be considered as same pair. I provided the following solution (in Java) and curious to know if I missed any edge cases?

public static int numberOfPairs(int[] a, int k ){

    int len = a.length;

    if (len == 0){
      return -1;
    }

    Arrays.sort(a);
    int count  = 0, left = 0, right = len -1; 

    while( left < right ){

        if ( a[left] + a[right] == k  ){

            count++; 

            if (a[left] == a[left+1] && left < len-1 ){
              left++;
            }

            if ( a[right] == a[right-1] && right >1 ){
              right-- ; 
            }

            right--; // right-- or left++, otherwise, will get struck in the while loop 
        }

        else if ( a[left] + a[right] < k ){
          left++;
        }

        else {
          right--;
        }
    }

    return count; 
}

Besides, can anyone propose any alternative solution of the problem ? Thanks.

Answer 1

Following solution will return the number of unique pairs

public static int numberOfPairs(Integer[] array, int sum) {
    Set<Integer> set = new HashSet<>(Arrays.asList(array));

    // this set will keep track of the unique pairs.
    Set<String> uniquePairs = new HashSet<String>();

    for (int i : array) {
        int x = sum - i;
        if (set.contains(x)) {
            int[] y = new int[] { x, i };
            Arrays.sort(y);
            uniquePairs.add(Arrays.toString(y));
        }
    }

    //System.out.println(uniquePairs.size());
    return uniquePairs.size();
}

The time complexity will be O(n).

Hope this helps.