Program to find target sum from given set of two arrays in java

Problem Statement:- Given two integer arrays, determine whether there is any pair of numbers from both arrays that return the target sum.

Solution: To solve this problem we can loop both arrays and by adding elements from both arrays we can find target sum. But this is very basic solution as its time complexity would be O(n^2) because we are looping both arrays two times.

To optimize this solution we can use dpp approach to store the numbers in a map then use it is in other solution .

Here in example we have solved it using normal loop and memorization .

1. Using Loop :  In this approach we will loop the array until start index is less than end index and swap the values of array with corresponding index .

Steps:- 

• assign variable for msg and break 
• loop both arrays
• add element from both arrays and check that its equal to target sum or not
• if true print the sub array and break loop

private static String targetSumInTwoArrayNonOptimize(int[] ar1, int[] ar2, int num) {
String msg="false";
boolean isFound=false;
for (int elem1:ar1) {
for (int elem2 : ar2) {
if (elem1+elem2==num) {
msg = true + " [" + elem1 + "," + elem2 + "] ";
isFound = true;
break;
}
}
if(isFound)break;
}
return msg;
}

Time Complexity : O(n) * O(n) = O(n^2)  , as it are looping loop inside loop .

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 

2. Using memorization(dpp) :  In this solution we will use dynamic programming memorization approach to store the numbers from first array to map.

First we will check that which array has least element as we will loop this array fully .Then we will get number that we need to search in other array using 

                num = sum-element

then we will store this num as key in map with value of current element.

After that we will loop other array and check that each element is present in map or not . If element is present in map then we will break the loop and return the pair .

This solution is better than previous one as its time complexity is O(n) and in worst case it could be O(logn) .

Steps:-

• assign two temp arrays one for small and another one for big array.
• we will check array based on length and assign to corresponding temp array.
• Initialize map for memorization .
• loop the small array and get the element that we need to find in other array by subtracting the first array element from target sum
• check this num is present in map , if not then put that in map, num as key and element as value.
• loop the big array , check that if array is present in map if yes then break the loop and return the pair 

private static String targetSumInTwoArrayDpp(int[] ar1, int[] ar2, int num) {
    String msg="false";
    int[] smallAr;  int[] bigAr;
    if(ar1.length>ar2.length){
        smallAr=ar2;
        bigAr=ar1;
    }else{
        smallAr=ar1;
        bigAr=ar2;
    }
    HashMap<Integer,Integer> map = new HashMap<>();

    for (int elem:smallAr) {
        if (!map.containsKey(num - elem)) {
            map.put(num-elem,elem);
        }
    }

    for (int elem : bigAr) {
        if (map.containsKey(elem)) {
            msg = true + " [" + map.get(elem) + "," + elem + "] ";
            break;
        }
    }
    return msg;
}

Time Complexity : 

best case=>  O(n) + O(n) + O(n) = 3 O(n) = O(n)

worst case => O(logn) + O(n) + O(n) = O(logn)

__________________________________________________________

output:- 

target-sum-7

target-sum-15

target-sum-14

Here in this run as we can see the optimize and non-optimize solutions are different because in non-optimize solution we are iterating one by one and in non-optimize solution we are looping based on array size . 

 You can found the full program on below link - target sum from two arrays

Thanks .