Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Move from brute-force thinking to an efficient approach using core interview patterns strategy.
There are n rooms labeled from 0 to n - 1 and all the rooms are locked except for room 0. Your goal is to visit all the rooms. However, you cannot enter a locked room without having its key.
When you visit a room, you may find a set of distinct keys in it. Each key has a number on it, denoting which room it unlocks, and you can take all of them with you to unlock the other rooms.
Given an array rooms where rooms[i] is the set of keys that you can obtain if you visited room i, return true if you can visit all the rooms, or false otherwise.
Example 1:
Input: rooms = [[1],[2],[3],[]] Output: true Explanation: We visit room 0 and pick up key 1. We then visit room 1 and pick up key 2. We then visit room 2 and pick up key 3. We then visit room 3. Since we were able to visit every room, we return true.
Example 2:
Input: rooms = [[1,3],[3,0,1],[2],[0]] Output: false Explanation: We can not enter room number 2 since the only key that unlocks it is in that room.
Constraints:
n == rooms.length2 <= n <= 10000 <= rooms[i].length <= 10001 <= sum(rooms[i].length) <= 30000 <= rooms[i][j] < nrooms[i] are unique.Problem summary: There are n rooms labeled from 0 to n - 1 and all the rooms are locked except for room 0. Your goal is to visit all the rooms. However, you cannot enter a locked room without having its key. When you visit a room, you may find a set of distinct keys in it. Each key has a number on it, denoting which room it unlocks, and you can take all of them with you to unlock the other rooms. Given an array rooms where rooms[i] is the set of keys that you can obtain if you visited room i, return true if you can visit all the rooms, or false otherwise.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: General problem-solving
[[1],[2],[3],[]]
[[1,3],[3,0,1],[2],[0]]
graph-valid-tree)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #841: Keys and Rooms
class Solution {
private int cnt;
private boolean[] vis;
private List<List<Integer>> g;
public boolean canVisitAllRooms(List<List<Integer>> rooms) {
g = rooms;
vis = new boolean[g.size()];
dfs(0);
return cnt == g.size();
}
private void dfs(int i) {
if (vis[i]) {
return;
}
vis[i] = true;
++cnt;
for (int j : g.get(i)) {
dfs(j);
}
}
}
// Accepted solution for LeetCode #841: Keys and Rooms
func canVisitAllRooms(rooms [][]int) bool {
n := len(rooms)
cnt := 0
vis := make([]bool, n)
var dfs func(int)
dfs = func(i int) {
if vis[i] {
return
}
vis[i] = true
cnt++
for _, j := range rooms[i] {
dfs(j)
}
}
dfs(0)
return cnt == n
}
# Accepted solution for LeetCode #841: Keys and Rooms
class Solution:
def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
def dfs(i: int):
if i in vis:
return
vis.add(i)
for j in rooms[i]:
dfs(j)
vis = set()
dfs(0)
return len(vis) == len(rooms)
// Accepted solution for LeetCode #841: Keys and Rooms
impl Solution {
pub fn can_visit_all_rooms(rooms: Vec<Vec<i32>>) -> bool {
let n = rooms.len();
let mut is_open = vec![false; n];
let mut keys = vec![0];
while !keys.is_empty() {
let i = keys.pop().unwrap();
if is_open[i] {
continue;
}
is_open[i] = true;
rooms[i].iter().for_each(|&key| keys.push(key as usize));
}
is_open.iter().all(|&v| v)
}
}
// Accepted solution for LeetCode #841: Keys and Rooms
function canVisitAllRooms(rooms: number[][]): boolean {
const n = rooms.length;
const vis: boolean[] = Array(n).fill(false);
const dfs = (i: number) => {
if (vis[i]) {
return;
}
vis[i] = true;
for (const j of rooms[i]) {
dfs(j);
}
};
dfs(0);
return vis.every(v => v);
}
Use this to step through a reusable interview workflow for this problem.
Two nested loops check every pair or subarray. The outer loop fixes a starting point, the inner loop extends or searches. For n elements this gives up to n²/2 operations. No extra space, but the quadratic time is prohibitive for large inputs.
Most array problems have an O(n²) brute force (nested loops) and an O(n) optimal (single pass with clever state tracking). The key is identifying what information to maintain as you scan: a running max, a prefix sum, a hash map of seen values, or two pointers.
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.