1

With reference to the question , I have found out the accepted answer used Java Collections API to get the index. My question is there are so many other methods to solve the given problem, which would be the optimal solution ?

  1. Use two loops
  2. Use sorting and binary search
  3. Use sorting and merging
  4. Use hashing
  5. Use Collections api
Community
  • 1
  • 1
deadbug
  • 434
  • 5
  • 19
  • Try it out and benchmark them? Though I'd say the one requiring the least amount of code is often the best one. – UnholySheep Mar 25 '17 at 11:36

1 Answers1

3
  1. Use two loops will take O(n ^ 2) time
  2. Use sorting and binary search will take O(nlog n) time
  3. Use sorting and merging O(nlog n) time
  4. Use hashing will take O(k * n) time with some other overhead and additional space.
  5. Use Collections api will take O(n ^ 2) time as its use native algorithm under the hood

You can do it in optimal way along with the ways mentioned above by using Knuth–Morris–Pratt algorithm in linear O(n + m) time complexity where n and m are the lengths of the two arrays.

KMP algorithm is basically a pattern matching algorithm(finding the starting position of a needle in haystack) which works on character string. But you can easily use it for integer array.

You can do some benchmark test for all those implementations and choose which one is efficient enough to suit your requirement.

Kaidul
  • 15,409
  • 15
  • 81
  • 150
  • Thanks. But it seems the given algorithm is for strings. Is it good for integer arrays ? – deadbug Mar 25 '17 at 11:41
  • 1
    Yes, instead of comparing character array(string) `str1[i] == str2[j]` it will compare integer array `arr1[i] == arr2[j]`. Comparing character of string will compare one byte and for integer its four bytes. Nothing different than this. – Kaidul Mar 25 '17 at 11:45