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;

}

}