HackerRank ‘The Grid Search’ Solution

Short Problem Definition:

Given a 2D array of digits, try to find the location of a given 2D pattern of digits

Link

The Grid Search

Complexity:

time complexity is O(n^2 * m^2)

space complexity is O(1)

Execution:

There are many sophisticated 2d pattern matching algorithms out there. Just think of computer vision, robotics, gaming… The issue with most of them is, that they are rather heuristics than complete matches. I first started solving this challenge by using brute force and well.. It passed the time constraints. I did not expect that. If anyone has a good way of reducing the number of subarray checks, please post it in the comments!

SubArray-Check reduction techniques:

  • keep the sum of the sub-array in a separate grid, check only if sum matches the pattern
  • Rabin-Karp string searching algorithm¬†on each line to¬†fast forward
Solution:
#!/usr/bin/py
def matchSubArray(arr, pat, x, y, pat_y, pat_x):
    for running_y in xrange(pat_y):
        for running_x in xrange(pat_x):
            if arr[running_y+y][running_x+x] != pat[running_y][running_x]:
                return False
    
    return True
            
            
def solveBruteForce(arr, pat, arr_y, arr_x, pat_y, pat_x):
    for y in xrange(arr_y-pat_y+1):
        for x in xrange(arr_x-pat_x+1):
            if matchSubArray(arr, pat, x, y, pat_y, pat_x):
                return True
    
    return False
    
if __name__ == '__main__':
    t = int(raw_input())
    for _ in xrange(t):
        arr_y, arr_x = map(int, raw_input().split())
        arr = [0] * arr_y
        for y in xrange(arr_y):
            arr[y] = list(raw_input())
        
        pat_y, pat_x = map(int, raw_input().split())
        pat = [0] * pat_y
        for y in xrange(pat_y):
            pat[y] = list(raw_input())
        
        if solveBruteForce(arr, pat, arr_y, arr_x, pat_y, pat_x):
            print "YES"
        else:
            print "NO"
        

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

Facebooktwittergoogle_plusredditpinterestlinkedin
  • Safwan Ahmad

    @Martin: Using brute force algorithm is obviously the straight forward approach. And you were lucky that the solution was accepted. But the thing that makes me curious is that if the same problem is asked during some technical interview then what can be done to optimize the solution. As suggested by you, that brute force can be made faster using Kabin Karp or matching the sum first, I want to know is there some known algorithm that the interviewer wants us to tell?

    • Hi Safwan. If you are applying to a company that has pattern matching algorithms in heavy use, you should definitely know them. Yet, why would anyone else require them? It is not something that you come across very often outside of universities and specialised libraries.