##### Short Problem Definition:

You are given a square map of size n×n. Each cell of the map has a value denoting its depth. We will call a cell of the map a cavity if and only if this cell is not on the border of the map and each cell adjacent to it has **strictly smaller depth**. Two cells are adjacent if they have a common side.

##### Link

##### Complexity:

time complexity is O(N^2)

space complexity is O(1)

##### Execution:

*pun* You only get your cavities checked on an airport */pun*

I check all 4 surrounding elements if they are strictly smaller. If so, I mark the position with an ‘X’. Better runtime than n^2 is not possible as every element has to be visited!

##### Solution:

#!/usr/bin/py def transformCavity(arr, n): for idx_tb in xrange(1, n-1): for idx_lr in xrange(1, n-1): if arr[idx_tb-1][idx_lr] != 'X' and int(arr[idx_tb-1][idx_lr]) < int(arr[idx_tb][idx_lr]) and \ arr[idx_tb+1][idx_lr] != 'X' and int(arr[idx_tb+1][idx_lr]) < int(arr[idx_tb][idx_lr]) and \ arr[idx_tb][idx_lr-1] != 'X' and int(arr[idx_tb][idx_lr-1]) < int(arr[idx_tb][idx_lr]) and \ arr[idx_tb][idx_lr+1] != 'X' and int(arr[idx_tb][idx_lr+1]) < int(arr[idx_tb][idx_lr]): arr[idx_tb][idx_lr] = 'X' if __name__ == '__main__': n = input() arr = [] for _ in xrange(n): line = list(raw_input()) arr.append(line) transformCavity(arr, n) for line in arr: print ''.join(line)

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