Capture Regions on Board | InterviewBit | Solution Explained
I explain the solution to the problem Capture Regions on Board in detail, along with visuals and annotated code in Python3.
0. Capture Regions on Board: Problem Discussion
0.0. IO Format
- input:
- a matrix of Xs and Os.
- output:
- the same matrix (in-place changes) where all the Os that are surrounded get converted to X
- condition:
- Os being surrounded means that they don’t have a connection from any of the borders. Look at the example below to understand better.
0.1. Examples
In the case above, the O marked in red gets converted to X, since it has no way of escape. On the other hands, all the Os marked in green have a way out to the border – either directly touching it, or through another Os touching it.
1. Capture Regions on Board: Observations & Logic
1.0. Intuitions
Since we know that all the Os that are connected to the border are safe, we can run a DFS/BFS from each of the Os on the border and mark the visited Os as “safe”. This would be fairly easy if we were allowed to create a new matrix, but since we can’t, how do we somehow add this “safe” information to the matrix?
1.1. Intermediate States
One way to deal with the above problem is that we can covert all the Os that are safe to #s. This will allow us to do two things:
- This let’s us mark Os which are safe.
- While doing DFS/BFS, we will know what all Os have been visited – they are converted to #s now. This will help us avoid infinite loops.
1.2. Cleaning the Board
Well, then what? Once we are done with the DFS or multi-source BFS, we do two things:
- Convert all the remaining Os to Xs, since they were not saved (otherwise they would be #s now)
- Convert all the #s back to Os, saying that they were saved – they had an escape to the border.
2. Capture Regions on Board: Optimized Implementation
2.0. Code
class Solution:
def solve(self, board):
# checks whether (i, j) is inside the board or not
def is_inside(i, j):
return 0 <= i < m and 0 <= j < n
# convert board's c1 character to c2
def convert_board(c1, c2):
for i in range(m):
for j in range(n):
if board[i][j] == c1:
board[i][j] = c2
return
# runs a dfs from (i, j)
def dfs(i, j):
# is (i, j) even in the board? if not, we don't care
if not is_inside(i, j): return
# is the current cell a non-O? then we don't care
if board[i][j] != "O": return
# otherwise we "save" it by converting it to a #
board[i][j] = "#"
# go over all the neighbours
for ii, jj in [(i+1, j), (i-1, j), (i, j+1), (i, j-1)]:
dfs(ii, jj)
m, n = len(board), len(board[0])
# start from all the 4 borders of the board
for i in range(m):
dfs(i, 0)
dfs(i, n-1)
for j in range(n):
dfs(0, j)
dfs(m-1, j)
# convert O -> X (captured)
convert_board('O', 'X')
# convert # -> O (saved/escaped)
convert_board('#', 'O')
return
2.1. Complexity Analysis
- Time:
O(MN), since we might have a case of a board with all Os, so we will convert all of them to #s, taking O(MN) time. - Space:
O(1), we don’t use any auxiliary space.
Producing high-quality intuitive explanations of interview problems. Currently covering LeetCode and InterviewBit.
Recommended Posts
Gas Station | InterviewBit | Solution Explained
June 13, 2022
Majority Element | InterviewBit | Solution Explained
June 13, 2022
Comments
Leave a Reply
This site uses Akismet to reduce spam. Learn how your comment data is processed.
Please write the proof.
This solution need an amendment for 2 digit number.
Please write a Proof for this
Matt Michael D’Agati is the founder of Renewables Worldwide, an Solar Firm in MA.
A few age ago, taking a leap of faith, Matt D’Agati delved into the realm of solar, and/or in a short occasion commenced effectively marketing significant amounts of power, primarily around the business industry, collaborating with solar farm developers and local businesses in the “design” of their unique plans.
Ongoing marketing within the sector, offered Matthew to participate a regional startup two years in the, and in a short time, he assumed the role of their Chief Strategy Officer, in charge of all operation and endeavor improvement, in addition to being marketed social group property.
To planned unions and shear get the job done mentality, Matthew D’Agati brought that firm from an initial initial-year revenue to in excess of a 2 hundred% surge in overall money by yr two. Based on that foundation, RW, a experienced-operated company, was produced with goal of giving you alternative electrical remedies for a more intelligent and more sustainable future.
Even more mainly, recognizing there is an untapped market in the market place and an improved approach to realize final results, RW is one of a handful of manufactures in the u.s. to place emphasis on individual acquire, concentrating in both industrial and home solar-powered town off-take. Its visualization is to make a purchases commercial infrastructure on a community-based, statewide, countrywide level, offering various sustainable fuel goods within the of RW.
This enthusiasm in the actual sustainable industry goes on to stimulate and inspire Matthew in enduring his solicit to work with institutions that have the unchanging of offering limitless fuel tips for a a whole lot more ecological destiny. Matt has already a new in companies from Hesser College.
Understanding why solar energy consultants assist clients via Matthew D’Agati.
Sustainable Energy and Electricity Poverty: Bridging the Imbalance by matt d’agatiMatt D’Agati e3d74c8