https://www.hackerrank.com/challenges/connected-cell-in-a-grid/problem
problem statement:
Consider a matrix where each cell contains either a 1 or a 0. Any cell containing a 1 is called a filled cell. Two cells are said to be connected if they are adjacent to each other horizontally, vertically, or diagonally. In the following grid, all cells marked X are connected to the cell marked Y.
XXX
XYX
XXX
If one or more filled cells are also connected, they form a region. Note that each cell in a region is connected to zero or more cells in the region but is not necessarily directly connected to all the other cells in the region.Given an matrix, find and print the number of cells in the largest region in the matrix. Note that there may be more than one region in the matrix.
For example, there are two regions in the following matrix. The larger region at the top left contains cells. The smaller one at the bottom right contains .
110
100
001
my solution:
# Complete the connectedCell function below.
def connectedCell(matrix)
highest_count = 0
visited = {}
(0...matrix.length).each do |i|
(0...matrix[0].length).each do |j|
next if visited[[i,j]]
if matrix[i][j] == 1
res = get_area_count([i,j], matrix)
if res[0] > highest_count
highest_count = res[0]
end
visited = visited.merge(res[1])
end
end
end
highest_count
end
def get_area_count(pos, matrix)
q = [pos]
visited = {}
count = 0
while q.length > 0
tile_pos = q.shift
if !visited[tile_pos]
count += 1
visited[tile_pos] = true
q += nbrs(tile_pos, matrix)
end
end
return [count, visited]
end
def nbrs(pos, matrix)
right = [pos[0], pos[1] + 1]
left = [pos[0], pos[1] - 1]
top = [pos[0] + 1, pos[1]]
bottom = [pos[0] - 1, pos[1]]
top_right = [top[0], right[1]]
bottom_right = [bottom[0], right[1]]
top_left = [top[0], left[1]]
bottom_left = [bottom[0], left[1]]
positions = [right, left, top, bottom, top_right, bottom_right, top_left, bottom_left]
positions.select{|npos| in_bounds?(npos, matrix.length, matrix[0].length) && matrix[npos[0]][npos[1]] == 1}
end
def in_bounds?(pos, m, n)
pos[0] >= 0 && pos[0] < m && pos[1] >= 0 && pos[1] < n
end
thought process:
My thought was to iterate through each cell in the matrix and then if it was a 1
I would do a depth-first traversal to find all other cells that had a 1
and were connected to the parent cell. then I would add 1 to the count whenever I visited a cell and add it to the visited
hash so that it wouldn't be added to the count. I added helper methods for in_bounds?
and nbrs
mostly for better readability in the get_area_count
method(which is the dfs implementation). The nbrs
method is pretty verbose, but I kept it that on purpose because I'm preparing for technical interviews, where accuracy is important, and I thought actually listing out each direction would help in debugging / explaining it to the interviewer.