Geek Answers Handbook

Algorithm - find the existence of a 2d array in another 2d array

I came across this question during an interview, and I cannot find a better way to do this.

The question says that there are two 2d arrays, one larger than the other. Let's say

Array_1 = [[1,2], [5,6]]

and

 Array_2 = [[1,2,3,4], [5,6,7,8], [9,10,11,12]]

Since Array 2 contains Array 1 here, algo should return true. Otherwise, false.

The size of the array can be any.

+5
source share
4 answers

I would fill a smaller array with large sizes with zero values ​​(or with NaN), convert to 1D and truncate / cut unnecessary values:

 array_1 = [1, 2, null, null, 5, 6] array_2 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]

then compare 1D arrays, skipping zero values ​​- this will be O(n*m) in the worst case (for example, [1,1,1,2] vs [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1] ), and at best it will be O(n) (if each number in the larger array was different)

Edit : More logic is needed to ensure comparisons are only within the full lines of a larger array, not line by line ...

I think you could convert arrays to position dictionaries and figure out a slightly more complex and faster algorithm if you need to make a few comparisons ...

You can also rotate a smaller array if necessary, for example:
 array_1_270 = [6, 2, null, null, 1, 5]
+1
source

Try it.

 function Test() { var x = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]]; var y = [[6, 7], [10, 12]]; for (i = 0; i < x.length; i++) { for (j = 0; j < x[i].length; j++) { if (x[i][j] == y[0][0]) if (findMatch(x, y, i, j)) { console.log("Match Found"); return true; } } } console.log("Not found"); return false; } function findMatch(x, y, i, j) { var b = true; for (k = i; k < y.length; k++) { for (n = j; n < y[k].length; n++) { if (y[k - i][n - j] != x[k][n]) { b = false; break; } } } return b; }

Note that this does not match if the smaller array rotates inside the large array. (Written in javaScript)

+1
source

You can try aho-corasick algorithm for 2 dimensions. The Aho-corasick algorithm is the fastest matching of multiple patterns. Here is a similar question: is there any document or explanation of how to implement two-dimensional KMP?

0
source

Maybe a little easier in Python 2.6

 def check(): small=[[1,2],[5,6]] #matches upper left corner smallrows = len(small) #rows = 2 smallcols = len(small[0]) #cols = 2 big=[[1,2,3,4],[5,6,7,8],[9,10,11,12]] bigrows = len(big) #rows = 3 bigcols = len(big[0]) #cols = 4 for i in range(bigrows-smallrows+1): #i is number row steps for j in range(bigcols-smallcols+1): #j is number col steps flag = 0 for k in range(smallrows): for l in range(smallcols): if big[i+k][j+l] != small[k][l]: flag = 1 continue if flag == 0: return(True) return(False) print check()
0
source

More articles:


All Articles