ThreeSumProblem

********************************** I. Using Naive Approach ********************************************

/*
 * Question:
Given an array of integers, return one set of 3 elements such that the 3 numbers add up to zero
(VERY IMP NOTE: REPETITIONS OF ELEMENTS ARE ALLOWED) 
{10, -2, -1, 3} -> true 
{10, -2, 1} -> true -2 + 1 +1 =0
 *
 * Source: http://www.geeksforgeeks.org/find-a-triplet-that-sum-to-a-given-value/
 * 
 * Algorithm : This is a THREE SUM PROBLEM:
 *             Generate all possible three set sums and check whether any of them matches with the given sum.
 * 			   1. Run first loop from i to arraySize
 *  		      1.1 Run second loop from j=i+1 to arraySize
 *                    1.1.1 Run third loop from k=j+1 to arraySize
 *                          Check if array[i]+array[j]+array[k]=Sum
 *                          
 */


package ThreeSumProblem;

import java.util.Scanner;

public class UsingNaiveApproach {
public static void main(String[] args) {
	Scanner in = new Scanner(System.in);
	try{
		System.out.println("Enter the number of elements in the array");
		int n = in.nextInt();
		int[] array = new int[n];
		System.out.println("Enter the elements of the array");
		for(int i=0;i<n;i++)
			array[i]=in.nextInt();
		System.out.println("Enter the sum that you need to find in the array");
		int sum = in.nextInt();
		System.out.println("The elements whose addition returns the sum are: ");
		usingNaiveApproach(array,sum);
	}
	finally{
		in.close();
	}
}

private static void usingNaiveApproach(int[] array, int sum) {
	outerloop:                               // label the outer loop
	for(int i=0;i<array.length;i++)
		for(int j=i+1;j<array.length;j++)
			for(int k=j+1;k<array.length;k++)
				if(array[i]+array[j]+array[k]==sum){
					System.out.println(array[i]+" "+array[j]+" "+array[k]);
					break outerloop;         // break the outer loop so that all internal loops are also broken           
				}
}

}
/*
 * Analysis:
 * Time Complexity = O(n^3)
 * Space Complexity = O(1)
 */

********************************** II. Using Sorting ***********************************************

/*
 * Question:
Given an array of integers, return one set of 3 elements such that the 3 numbers add up to zero
(VERY IMP NOTE: REPETITIONS OF ELEMENTS ARE ALLOWED) 
{10, -2, -1, 3} -> true 
{10, -2, 1} -> true -2 + 1 +1 =0
 *
 * Source: http://www.geeksforgeeks.org/find-a-triplet-that-sum-to-a-given-value/
 * 
 * Algorithm : This is a THREE SUM PROBLEM:
 *             Sort the array and then apply the Two Sum Logic
 *             1. Sort the array
 *             2. Run a loop starting from i=0 to (arraySize-2) 
 *                2.1 Take a fixed element as fixedElement = array[i]
 *                2.2 Find the other two elements from the SORTED ARRAY CORNERS
 *                    low = [i+1]    // Next Element
 *                    high = [arraySize-1]     // last element of the array
 *                         2.2.1 while(low<high)
 *                         		 Check if(fixed+low+high == sum). If yes then print the elements and break
 *                                     if(fixed+low+high < sum). Then low++
 *                                     if(fixed+low+high > sum). Then high--
 */


package ThreeSumProblem;

import java.util.Arrays;
import java.util.Scanner;

public class UsingSorting {
public static void main(String[] args) {
	Scanner in = new Scanner(System.in);
	try{
		System.out.println("Enter the number of elements in the array");
		int n = in.nextInt();
		int[] array = new int[n];
		System.out.println("Enter the elements of the array");
		for(int i=0;i<n;i++)
			array[i]=in.nextInt();
		System.out.println("Enter the sum that you need to find in the array");
		int sum = in.nextInt();
		System.out.println("The elements whose addition returns the sum are: ");
		usingSorting(array,sum);
	}
	finally{
		in.close();
	}
}

private static void usingSorting(int[] array, int sum) {
	int low=0;
	int high=0;
	/* Sort the elements */
	Arrays.sort(array);
	/* Now fix the first element one by one and find the
    other two elements */
	outerloop:
	for(int i=0;i<(array.length-2);i++){
		// To find the other two elements, start two index variables
        // from two corners of the array and move them toward each
        // other
		low=i+1;
		high = array.length-1;
		while(low<high){
			if(array[i]+array[low]+array[high]==sum){
				System.out.println(array[i]+" "+array[low]+" "+array[high]);
				break outerloop;
			}
			if(array[i]+array[low]+array[high]<sum)
				low++;
			if(array[i]+array[low]+array[high]>sum)
				high--;
			
		}
	}
}



}
/*
 * Analysis:
 * Time Complexity = O(n^2) due to nested for and while loop
 * Space Complexity = O(1)
 */


**************************** III Solving Three Sum Problem Using HashMap ****************************************

VERY IMP NOTE: Time Complexity of Three Sum Problem using:
1. HashMap = O(n^3)
The reason why we need to use HashMap is because if the interviewer specifies that there are duplicate elements in
the array, then we need to use HashMap. If interviewer says that all elements of the array are unique then
we can SAFELY use HashSet.
2. HashSet = O(n^2)
HashSet is used when array elements are unique.

/*
 * Question:
Given an array of integers, return one set of 3 elements such that the 3 numbers add up to zero
(VERY IMP NOTE: REPETITIONS OF ELEMENTS ARE ALLOWED) 
{10, -2, -1, 3} -> true 
{10, -2, 1} -> true -2 + 1 +1 =0
 *
 * Source: http://www.careercup.com/question?id=5736292639834112
 * 
 * Algorithm : This is a THREE SUM PROBLEM:
 * 			   1. Store all elements in a HashSet
 *             2. for i=0 to array.length
 *                     for j = i to array.length
 *                          check if [-(i+j)] exists in HashMap OR HashSet
 *                          
 * VERY IMPORTANT NOTE:
 * 1. If the array elements can contain duplicates then we are forced to use HashMap, since HashSet would overwrite
 * on duplicate elements(thus not allowing duplicates) since same values will hash to the same bucket location
 * 
 * 2. However, if the interviewer says that duplicates are not present in the array, then we can use HashSet
 * 
 */


package ThreeSumProblem;

import java.util.HashMap;
import java.util.Scanner;

public class UsingHashMap {
public static void main(String[] args) {
	Scanner in = new Scanner(System.in);
	try{
		System.out.println("Enter the number of elements in the array");
		int n = in.nextInt();
		int[] array = new int[n];
		System.out.println("Enter the elements of the array");
		for(int i=0;i<n;i++)
			array[i]=in.nextInt();
		System.out.println("Enter the sum that you need to find in the array");
		int sum = in.nextInt();
		System.out.println("The elements whose addition returns the sum are: ");
		findThreeSumUsingHashMap(array,sum);
	}
	finally{
		in.close();
	}
}

private static void findThreeSumUsingHashMap(int[] array, int sum) {
	// store the array elements in the HashMap
	HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
	for(int i=0;i<array.length;i++)
		map.put(i,array[i]);
	// iterate through the array elements and check whether the third is in the HashMap
	outerloop:                          // using label in Java to break the outer loop
	for(int i=0;i<array.length;i++)
		for(int j=i+1;j<array.length;j++)  // start from the next element
			if(map.containsValue(sum-(array[i]+array[j]))){    // containsValue time complexity is O(n)
				System.out.print(array[i]+" "+array[j]+" "+(sum-(array[i]+array[j])));
				break outerloop;     // we can use labels to break directly the outer loop (which in turn breaks inner loop)
			}                       // Otherwise, we would have to implement some mechanism to break both the loops simultaneously
	
	}
}
/*
 * Analysis:
 * Time Complexity = O(n^3) since time complexity of containsValue is O(n) and two for loops account for O(n^2) time
 * Space Complexity = O(n)
 */


**************************** IV. Solving Three Sum Problem Using HashSet ****************************************
/*
 * Question:
Given an array of integers, return one set of 3 elements such that the 3 numbers add up to zero
(VERY IMP NOTE: REPETITIONS OF ELEMENTS ARE ALLOWED) 
{10, -2, -1, 3} -> true 
{10, -2, 1} -> true -2 + 1 +1 =0
 *
 * Source: http://www.careercup.com/question?id=5736292639834112
 * 
 * Algorithm : This is a THREE SUM PROBLEM:
 * 			   1. Store all elements in a HashSet
 *             2. for i=0 to array.length
 *                     for j = i to array.length
 *                          check if [-(i+j)] exists in HashMap OR HashSet
 *                          
 * VERY IMPORTANT NOTE:
 * 1. If the array elements can contain duplicates then we are forced to use HashMap, since HashSet would overwrite
 * on duplicate elements(thus not allowing duplicates) since same values will hash to the same bucket location
 * 
 * 2. However, if the interviewer says that duplicates are not present in the array, then we can use HashSet
 * 
 */


package ThreeSumProblem;

import java.util.HashSet;
import java.util.Scanner;

public class UsingHashSet {
public static void main(String[] args) {
	Scanner in = new Scanner(System.in);
	try{
		System.out.println("Enter the number of elements in the array");
		int n = in.nextInt();
		int[] array = new int[n];
		System.out.println("Enter the elements of the array");
		for(int i=0;i<n;i++)
			array[i]=in.nextInt();
		System.out.println("Enter the sum that you need to find in the array");
		int sum = in.nextInt();
		System.out.println("The elements whose addition returns the sum are: ");
		findThreeSumUsingHashSet(array,sum);
	}
	finally{
		in.close();
	}
}

private static void findThreeSumUsingHashSet(int[] array, int sum) {
	// store the array elements in the HashMap
	HashSet<Integer> set = new HashSet<Integer>();
	for(int element: array)
		set.add(element);
	// iterate through the array elements and check whether the third is in the HashMap
	outerloop:                          // using label in Java to break the outer loop
	for(int i=0;i<array.length;i++)
		for(int j=i+1;j<array.length;j++)  // start from the next element
			if(set.contains(sum-(array[i]+array[j]))){   // time complexity of contains method of HashSet is O(1)
				System.out.print(array[i]+" "+array[j]+" "+(sum-(array[i]+array[j])));
				break outerloop;     // we can use labels to break directly the outer loop (which in turn breaks inner loop)
			}                       // Otherwise, we would have to implement some mechanism to break both the loops simultaneously
	
	}
}
/*
 * Analysis:
 * Time Complexity = O(n^2) since time complexity of contains is O(1) and two for loops account for O(n^2) time
 * Space Complexity = O(n)
 */