Hello, world. I have been brushing up on algorithms and data structures and a big part of what I do is working on solving some LeetCode and HackerRank challenges. I wanted to stay in the ready-for-interview mode for sometime. Who knows when an opportunity may come!
I encountered this problem: Keys and Rooms. Despite not solving many challenges related to graphs before, I felt that this challenge was a good way to start hacking into solving programming challenges that are based on graphs and their algorithms.
Problem Statement
Firstly, let’s look at the description. Which is straight forward: there are N rooms (named 0, 1, … N-1). Each room contains keys for other number of rooms. For example, room 0 could contain keys for rooms 1, 3.
If we could start going into one of the rooms, let’s say room 0, how do you think we make sure that all the rooms are reachable?
For example:
Input: [[1],[2],[3],[]]
Keys in room 0: {1}
Keys in room 1: {2}
Keys in room 2: {3}
Keys in room 3: {} (no keys)
Output: true
We go to room #0, we find a key to room #1. We go to room #1, we find a key to room #2. We go to room #2, we find a key to room #3. We go to room #3, we find no keys.
Eventually, we find out that the output is true because we could visit each and every room at least once.
How I solved it
It was really simple. Depth-first search. Think of the rooms as nodes in a graph, and the only way to move from one node (room) to another is an edge (key).
DFS (iterative version) pseudocode:
procedure DFS-iterative(G,v):
let S be a stack
S.push(v)
while S is not empty
v = S.pop()
if v is not labeled as discovered:
label v as discovered
for all edges from v to w in G.adjacentEdges(v) do
S.push(w)
We model the rooms as nodes, the keys as edges to the rooms designated by the value of the key. For instance, in the example: [[1,3],[3,0,1],[2],[0]] we build a graph of [0, N-1] nodes. That is, rooms: [0, 1, 2, 3]. For each node (room), we create an edge connecting the current room with the room referenced by the value of the key.
As we can see, room 2 contains a key only to itself and there’s no other room that contains a key to room 2. Hence, output should be false since there is at least one room we cannot visit.
The coding part
To sum up, I find it was a great experience to write about solving a challenge. Not just “solving a challenge”, but rather, the actual writing about the solution. Researching the algorithm, brushing up on Java for implementation and on algorithms to ensure the correctness of the expalnation, it really adds a lot.
Finally, as I first said, I believe it makes a person learn more about the topic they are writing about when they actually start to write.
I will try to make this a habit and probably keep solving interesting challenges and write about them, explaining the approach and the algorithm behind solving.