twoSum

import java.util.*;

class Main {
    public static void main(String[] args) {
        // given an array find the pair that equals to given sum
        
        // {1,2,3,5,6} --> sum = 4
        // {1,2,5, 9} --> sum = 4
        
        // Given sorted array, and only integers and can have negative numbers
        
        // if there is a matching pair return true, otherwise return false, return true if you find atleat one matching pair
        
        // main goal is find the efficient solution
        
        // Naive, brute force method
        
        int [] inputArray = {1,2,5,9,25,34,87};
       System.out.println(new Main().evaluateMatchingPairUsingTreeSet(inputArray, 33));
        
        
    }
    
     public boolean evaluateMatchingPairBruteForce(int[] input, int sum){
            
            for(int i = 0 ; i < input.length; i++){
                for(int j = i+1; j < input.length; j++){
                    int calSum = input[i] + input[j];
                    if(calSum == sum){
                        return true;
                    }
                }
            }
            return false;
        }
        
        // optimised code
        
        // I would consider the below approach where i add the first and last sum and if is more than the sum i will decrease the index or increase the index if greater than
        
        
        public boolean evaluateMatchingPair(int[] input, int sum){
            
            int higherIndex = input.length-1;
            int lowerIndex = 0;
            
            while(lowerIndex<higherIndex){
                int calSum = input[higherIndex] + input[lowerIndex];
                if(calSum == sum)
                    return true;
                else if(calSum < sum)
                    lowerIndex++;
                else
                    higherIndex--;
                
            }
            
            return false;
            
        }
        
        // the above solution only works for sorted numbers what if the numbers are not sorted how would you find
        // {1,3,2,5,6} --> sum = 4
        
        public boolean evaluateMatchingPairUsingTreeSet(int[] input, int sum){
            
            Set<Integer> comp = new TreeSet<>();
            
            for(int i =0; i<input.length; i++){
                if(comp.contains(input[i]))
                    return true;
                comp.add(sum-input[i]);
            }
            return false;
        }
}