SAMSUNG 49-Inch Odyssey G9

Because earth is not flat

Description

The problem is about determining if all the rooms in a set of rooms can be visited. Each room has a list of keys to other rooms, and you start in room 0. The task is to check if it's possible to visit all rooms starting from room 0.

Intuition

The problem can be visualized as a graph traversal where rooms are nodes and keys are edges connecting these nodes. The goal is to visit all nodes starting from the initial node (room 0). If all nodes can be reached, then all rooms can be visited.

Approach

1. Initialization: Create a list or array to track visited rooms and a stack to manage the rooms to be visited. Initially, mark room 0 as visited and push it onto the stack.

2. Traversal: Use a loop to process the rooms in the stack. For each room, retrieve its list of keys (i.e., neighboring rooms). If a neighboring room hasn’t been visited, mark it as visited and push it onto the stack.

3. Completion: After processing all rooms, check if the number of visited rooms matches the total number of rooms. If they match, all rooms can be visited; otherwise, not all rooms can be visited.

Complexity

Time Complexity:

O(N + E), where N is the number of rooms and E is the total number of keys (edges). We potentially visit each room and process each key once.

Space Complexity:

O(N), where N is the number of rooms. This is for the visited list and stack used during the traversal.

Code

C++

class Solution {
public:
    bool canVisitAllRooms(std::vector<std::vector<int>>& rooms) {
        int n = rooms.size();
        std::vector<bool> vis(n, false);
        std::stack<int> stack;
        stack.push(0);
        vis[0] = true;
        int count = 1;

        while (!stack.empty()) {
            int currentRoom = stack.top();
            stack.pop();
            for (int key : rooms[currentRoom]) {
                if (!vis[key]) {
                    stack.push(key);
                    vis[key] = true;
                    count++;
                }
            }
        }
        return count == n;
    }
};

Python

class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        n = len(rooms)
        vis = [False] * n
        stack = [0]
        vis[0] = True
        count = 1

        while stack:
            current_room = stack.pop()
            for key in rooms[current_room]:
                if not vis[key]:
                    stack.append(key)
                    vis[key] = True
                    count += 1
        
        return count == n

Java

class Solution {
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        int n = rooms.size();
        boolean[] vis = new boolean[n];
        Stack<Integer> stack = new Stack<>();
        stack.push(0);
        vis[0] = true;
        int count = 1;

        while (!stack.isEmpty()) {
            int currentRoom = stack.pop();
            for (int key : rooms.get(currentRoom)) {
                if (!vis[key]) {
                    stack.push(key);
                    vis[key] = true;
                    count++;
                }
            }
        }
        return count == n;
    }
}

JavaScript

var canVisitAllRooms = function (rooms) {

    let vis = new Array(rooms.length), stack = [0], count = 1
    vis[0] = 1
    while (stack.length) {
        let keys = rooms[stack.pop()]
        for (let k of keys)
            if (!vis[k]) stack.push(k), vis[k] = 1, count++
    }
    return rooms.length === count
};