Approach #1: Depth-First Search [Accepted]

Intuition and Algorithm

When visiting a room for the first time, look at all the keys in that room. For any key that hasn't been used yet, add it to the todo list (stack) for it to be used.

See the comments of the code for more details.

Complexity Analysis

  • Time Complexity: , where is the number of rooms, and is the total number of keys.

  • Space Complexity: in additional space complexity, to store stack and seen.