CODEWITHSUNDEEP
arraysalgorithm
invincibleDudess
invincibleDudess

Reputation: 1792

Algorithm - Find existence of a 2d array in another 2d array

I came across this question while in an interview and i am unable to find the best way to do it.

The question says, there are two 2d arrays, one is bigger than the other. Lets say,

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

and 

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

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

The size of the array can be anything.

Upvotes: 5

Views: 1840

Answers (4)

Marichyasana
Marichyasana

Reputation: 3154

Maybe a little simpler 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()

Upvotes: 0

Cybercartel
Cybercartel

Reputation: 12592

You can try aho-corasick algorithm for 2 dimension. Aho-corasick algorithm is the fastest multiple pattern matching. Here is a similar question:is there any paper or an explanation on how to implement a two dimensional KMP?

Upvotes: 0

Aprillion
Aprillion

Reputation: 22322

I would fill in the smaller array to the bigger dimensions with null values (or with NaN), convert to 1D and truncate/strip the unnecessary nulls :

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

then compare the 1D arrays, while skipping the null values - this would be O(n*m) in the worst case (such as [1,1,1,2] vs [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]), and it would be O(n) in the best case (if every number in the bigger array was different)

Edit: more logic is needed to ensure comparison only within the complete rows of the bigger array, not across rows...

I guess you could convert the arrays to dictionaries of positions and figure out a bit more complicated and faster algorithm if you need to do multiple comparisons...

You could also rotate the smaller array if needed, e.g.:

array_1_270 = [6, 2, null, null, 1, 5]

Upvotes: 0

prasadmadanayake
prasadmadanayake

Reputation: 1435

Try this.

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 doesn't match if the smaller array is rotated inside the big array.(Written in javaScript)

Upvotes: 1

Related Questions