Find all non duplicate pairs that sum to S

Find all non duplicate pairs that sum to S.

try to do it in O(nlogn).

Solution 1:

First sort the list, best possible way is O(nlogn).
Then take two pointers p1 and p2, p1 pointing at first and p2 pointing at last element in the list. Now if the sum is less then S, move p1 forward, if sum is greater then S move p2 backward, if equal put in a set. Keep on doing this till p1 and p2 crosses each other. This will take O(n) time so total complexity will be O(nlogn)

Java Code: Non Duplicate Pairs

//Save as NonDuplicatePairs.java
import java.util.HashSet;
import java.util.Set;


public class NonDuplicatePairs {

	private Set<String> getNonDuplicatePairsWithSum(int[] input, int S){
		int p1 = 0; //pointing @ start of the list
		int p2 = input.length -1;//pointing @ end
		Set<String> nonDuplicatePairs = new HashSet<String>();
		while(p1 <= p2){
			int sum = input[p1] + input[p2];
			
			if(sum < S){
				p1++;
				continue;
			}
			else if(sum > S){
				p2--;
				continue;
			}
			else{
				//To avoid cases like 3,5 and 5,3 putting smaller number first
				nonDuplicatePairs.add(""+Math.min(input[p1], input[p2]) +"," 
+Math.max(input[p1], input[p2]));
				p1++;
				p2--;
			}
		}
		
		return nonDuplicatePairs;
	}
	
	public static void main(String[] argv){
		int[] input = new int[]{1,2,3,4,5,6,7,8,9,10,11};
		Set<String> nonDuplicatePairs = 
                 new NonDuplicatePairs().getNonDuplicatePairsWithSum(input, 12);
		
		for(String pair: nonDuplicatePairs){
			System.out.println(pair);
		}
	}
}

Solution 2:
We can use a HashMap here, iterate over the list and put element and its number of occurrence in the map. Now iterate over the list again and look for S – i^th value in the map. if present put this pair in the set. There is a special case when i^th element = S-i^th element, in that case look for the number of occurrence, if more then 1 then consider this set else not. Here total time taken will be O(n) but will need O(n) extra space.

Facebook Comments