CODEWITHSUNDEEP
javaarraysalgorithmoptimization
deadbug
deadbug

Reputation: 444

Algorithm Complexity : Finding the starting index of a sub array in a larger array

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

Upvotes: 1

Views: 233

Answers (1)

Kaidul
Kaidul

Reputation: 15875

  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.

Upvotes: 3

Related Questions