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

Question

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 ?

Use two loops
Use sorting and binary search
Use sorting and merging
Use hashing
Use Collections api

Try it out and benchmark them? Though I'd say the one requiring the least amount of code is often the best one. — UnholySheep
– UnholySheep, Commented Mar 25, 2017 at 11:36

Kaidul · Accepted Answer · 2017-03-25 11:53:44Z

3

Use two loops will take O(n ^ 2) time
Use sorting and binary search will take O(nlog n) time
Use sorting and merging O(nlog n) time
Use hashing will take O(k * n) time with some other overhead and additional space.
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.

edited Mar 25, 2017 at 11:53

answered Mar 25, 2017 at 11:37

Kaidul

16k17 gold badges84 silver badges158 bronze badges

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

2 Comments

deadbug Over a year ago

Thanks. But it seems the given algorithm is for strings. Is it good for integer arrays ?

Kaidul Over a year ago

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.

Collectives™ on Stack Overflow

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

1 Answer 1

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related