CODEWITHSUNDEEP
javaarrays
JaZZyCooL
JaZZyCooL

Reputation: 1

Finding common element in two arrays with best performing method

Implement a method that checks whether an integer is present in both integer array parameter 1 and integer array parameter 2 and prints the result of the search, with the best performance you can. The method parameters are: (1) the first integer array and (2) the second integer array of the same size as parameter 1 and (3) the integer to search for.

Note - Consider better performance to mean that a better performing method requires fewer general work steps to solve the problem with the same size of arrays. You may want to review the Java SE API page for java.util.Arrays

I was able to implement the solution but I am not sure if it the best-performing one because I am not using any java.util.Arrays methods as I am not sure which one to use necessarily to get me the best answer

public static void findCommonElements(int[] arr1, int[] arr2, int num){

        for(int i = 0; i < arr1.length; i++){

            for(int j = 0; j < arr2.length; j++){

                if(arr1[i] == arr2[j] && arr1[i] == num){

                    System.out.println(num);

                }

            }
        }

    }

UPDATE: I was able to update the code with following solution which completely removes for loop and implements binary for better performance

int[] arr1 = {7,8,5,1,2,3,6,7};
int[] arr2 = {9,8,6,4,1,2,4,5};
Arrays.sort(arr1);
Arrays.sort(arr2);

int index1 = Arrays.binarySearch(arr1, 5);
int index2 = Arrays.binarySearch(arr2, 5);
System.out.println(index1);
System.out.println(index2);

if(index1 < 0 || index2 < 0){
    System.out.println("number not found in both arrays");
}
else{
    System.out.println("number found in both arrays");
}

Upvotes: 0

Views: 791

Answers (2)

Nowhere Man
Nowhere Man

Reputation: 19545

You can use search the arrays using streams:

public static boolean findCommonElements(int[] arr1, int[] arr2, int num) {
    return Arrays.stream(arr1).anyMatch(x -> x == num) &&
           Arrays.stream(arr2).anyMatch(x -> x == num);
}

Similar method using linear search in arrays of Integer using Arrays.asList to convert arrays:

public static boolean findCommonElements(Integer[] arr1, Integer[] arr2, int num) {
    return Arrays.asList(arr1).indexOf(num) > -1 &&
           Arrays.asList(arr2).indexOf(num) > -1;
}

Upvotes: 1

John Bollinger
John Bollinger

Reputation: 180103

The problem description is a bit hard to follow, but by reference to the example code, I take this to be a fair rewording: "Write the best-performing method you can that takes two int arrays of the same length and a scalar int value i as parameters, and prints whether the value of i appears in both arrays."

Your first solution tests each pair of elements drawn one from the first array and the other from the second to determine whether they are equal to each other and to the target value. This is grossly inefficient for the problem as interpreted.

Your second solution sorts the arrays first, so as to be able to use a binary search to try to find the target element. This is better, but still inefficient. Although the binary searches are quite fast, the sorting required to prepare for them takes a lot more work than is saved by a single binary search.

Since it is sufficient to determine only whether the target value appears in both arrays, you can

  • scan each array for the target value, once, independently of the other.
  • skip the second scan if the first one does not find the target value
  • break early from each scan when the target value is found

The latter two are minor improvements, as they reduce only the minimum and average number of steps. The first, however, is a huge improvement, especially as array size increases, because for arrays of length n, then this requires a number of steps proportional to n in the worst case, whereas your first example code requires steps proportional to n2 in both the average and worst cases, and your second requires time proportional to n log n in the average and worst cases.

The implementation is left as the exercise it is intended to be. However, with respect to

I was able to implement the solution but I am not sure if it the best-performing one because I am not using any java.util.Arrays methods as I am not sure which one to use necessarily to get me the best answer

, I don't think java.util.Arrays offers any method that particularly helps with this problem, especially given the orientation toward best possible performance.

Upvotes: 1

Related Questions