Business
Jobs
  • About Us
  • Solutions
    • Job Postings
      Post your job and receive qualified candidates in 48h.
    • Candidate Assessments
      500+ technical and psychological tests, plus anti-fraud.
    • Headhunting
      Tailor-made executive search from start to finish.
    • Payroll + EOR
      Payroll dispersal and EOR across 15+ LATAM countries.
  • Pricing
  • Jobs

0

137
Views
What should be the best approach for this algorithm? DFS or BFS? and why?

When planting flowers in a pot, it's important to make sure that whenever you water your plant any water that doesn't get absorbed by the roots drains out the bottom of the pot. Otherwise, the water will pool in the bottom of the pot and cause your plant to rot.

You recently decided to plant some flowers of your own,
and decided to fill the base of the pot with gravel. You've
decided to write code to verify whether water will
successfully drain out of the pot.
Using a 2D array to represent your pot, individual pieces of
gravel are notated with a 1 and empty spaces between
gravel are notated with a 0.
Example Pot #1:

[
[0, 1, 1, 1, 1],
[0, 1, 0, 0, 0],
[0, 0, 0, 1, 0],
[1, 1, 1, 1, 0],
[1, 0, 0, 1, 0],
]

Write a function to determine whether the water can fall
from the top row to the bottom, moving through the
spaces between the gravel. Taking the example pot from
above, you can see the posible path, which is marked by
replacing the relevant 0's with asterisks (*)

[
[*, 1, 1, 1, 1],
[*, 1, *, *, *],
[*, *, *, 1, *],
[1, 1, 1, 1, *],
[1, 0, 0, 1, *],
]

Notice that the path includes both the top and bottom rows. Allowed moves: The only moves allowed are up, down, left, and right. Diagonals are not allowed.

Here are a few pots that don't drain properly, along with
explanations.

[
[1, 1, 1],
[1, 1, 0],
[1, 0, 0],
]

Explanation: The top row has no gaps

[
[1, 1, 0],
[1, 1, 0],
[1, 1, 1],
]

Explanation: The bottom row has no gaps
[
[1, 1, 0],
[1, 1, 0],
[1, 0, 1],
]
about 4 years ago · Juan Pablo Isaza
1 answers
Answer question

0

Both solutions work, and both can be implemented using only a constant amount of extra memory, by modifying the matrix in place. Since the task is to modify the matrix, you might as well take advantage of the ability to do this.

BFS is a little simpler, and will find the shortest path -- not a requirement, but couldn't hurt.

about 4 years ago · Juan Pablo Isaza Report
Answer question
Find remote jobs

Discover the new way to find a job!

Top jobs
Top job categories
Business
Post vacancy Pricing Sales
Legal
Terms and conditions Privacy policy
© 2026 PeakU Inc. All Rights Reserved.
Andres GPT
Show me some job opportunities
There's an error!