Java : Taking 2 array find if the element that exists in both array return true if exist else false

Question

I am looking for some clarification on this solution. Can anyone guide me on the following two points:

Is the below algorithm good solution?
and is my Big O calculation correct?

your clarification is highly appreciated. Thanks in advance

public static void main(String[] args) {
    String[] a = {"a", "b", "c", "d"};
    String[] b = {"z", "f", "c"};

    boolean value1 = find(a, b);
    System.out.println(value1);

    boolean value2 = findArray(a, b);
    System.out.println(value2);

}

/*
since the both the array is of diff size for nested loop
Big O  = O(n*n)
if array size is same Big O = O(n^2)
 */
private static boolean find(String[] a, String[] b) {
    for (int i = 0; i < a.length; i++) {
        String val1 = a[i];
        for (int j = 0; j < b.length; j++) {
            if (val1.equals(b[j])) {
                System.out.println(val1 + " : " + b[j]);

                return true;
            }
        }// O(n)
    }// O(n)
    return false;
}// O(n*n)

/*
Big O  = O(n)
 */
private static boolean findArray(String[] a, String[] b) {
    //create array list from array
    List<String> list = new ArrayList<>(Arrays.asList(b));
    for (int i = 0; i < a.length; i++) {
        String val1 = a[i]; //O(1)

        if (list.contains(val1)) {
            System.out.println(val1 + " : contain in list b");
            return true;
        }// O(1)

    }// O(n)
    return false;
}// O(n)

Isn't this question more a codereview.stackexchange.com question? — Stephan Hogenboom
– Stephan Hogenboom, Commented Dec 4, 2019 at 11:20

mondayguy · Accepted Answer · 2019-12-05 04:36:27Z

1

Your second solution is also O(N^2), because contain works O(N) under the hood.

First Solution O(N*LogN):

Sort second array. NLogN
Iterate throught first one O(N) and binary search via second one O(logN) => O(NLogN)

Overall complexity O(NLogN)

Second solution O(N) - if arrays are sorted. If not O(NLogN), because of step 1

Sort both of arrays O(NlogN)
Do something like this

Code:

int curA = 0, curB = 0;
while (true) {
 if (curA >= a.length || curB >= b.length)
  break;
 if (a[curA] < b[curB]) {
  curA++;
  continue;
 }

 if (a[curA] > b[curB]) {
  curB++;
  continue;
 }

 return true;
}
return false;

edited Dec 5, 2019 at 4:36

answered Dec 4, 2019 at 13:14

mondayguy

9913 gold badges13 silver badges36 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Bommarn · Accepted Answer · 2019-12-04 11:17:05Z

0

I think that both algorithms looks reasonable.
ArrayList.contains time complexity is O(n).

The size, isEmpty, get, set, iterator, and listIterator operations run in constant time. The add operation runs in amortized constant time, that is, adding n elements requires O(n) time. All of the other operations run in linear time (roughly speaking). The constant factor is low compared to that for the LinkedList implementation.

https://docs.oracle.com/javase/6/docs/api/java/util/ArrayList.html

answered Dec 4, 2019 at 11:17

Bommarn

694 bronze badges

2 Comments

R Dewan Over a year ago

thank you for your answer. is there any better way to solve this problem in terms on time complexity .

Bommarn Over a year ago

Glad to help! I cant think of any better solution than what @mondayguy has suggested.

Collectives™ on Stack Overflow

Java : Taking 2 array find if the element that exists in both array return true if exist else false

2 Answers 2

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related