04/2/15

# 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

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 =  * arr_y
for y in xrange(arr_y):
arr[y] = list(raw_input())

pat_y, pat_x = map(int, raw_input().split())
pat =  * 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.

04/1/15

# HackerRank ‘Missing Numbers’ Solution

##### Short Problem Definition:

Numeros, the Artist, had two lists A and B, such that B was a permutation of A. Numeros was very proud of these lists. Unfortunately, while transporting them from one exhibition to another, some numbers from A got left out. Can you find the numbers missing?

Sherlock and Array

##### Complexity:

time complexity is O(n)

space complexity is O(n)

##### Execution:

The problem statement informs us, that there are only 100 different values. This calls for a counting sort.0

##### Solution:
```#!/usr/bin/py
def solveMissing(n, m):
n_cnt =  * 101
m_cnt =  * 101
offset = min(m)

for ele in m:
m_cnt[ele-offset] += 1

for ele in n:
n_cnt[ele-offset] += 1

for idx in xrange(101):
if m_cnt[idx] != n_cnt[idx]:
print idx + offset,

if __name__ == '__main__':
n = int(raw_input())
arr = map(int, raw_input().split())
m = int(raw_input())
arr2 = map(int, raw_input().split())
solveMissing(arr, arr2)
```

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