Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Solution: Find Eventual Safe States

Problem Statement

You are given a directed graph with n nodes, labeled from 0 to n-1. This graph is described by a 2D integer array graph, where graph[i] is an array of nodes adjacent to node i, indicating there is a directed edge from node i to each of the nodes in graph[i].

A node is called a terminal node if it has no outgoing edges. A node is considered safe if every path starting from that node leads to a terminal node (or another safe node).

Return an array of all safe nodes in ascending order.

Examples

Example 1:

  • Input: graph =

.....

.....

.....

Like the course? Get enrolled and start learning!
Siddhartha

Siddhartha

· a year ago

Instead of calling dfs function and storing each node in result array then sorting, we can just call dfs function then we can loop over visited array, sort adds overhead of O(vlon(v))

Show 1 reply
S

Sourav Rawat

· a year ago

As the question says I am struggling to solve these problems and have to jump to the solutions, this is first time working and learning graphs. I am struggling a bit when it comes to graph representation using adjacency matrices or when they are given like this. I find the questions that have the u, v representation easier.

Show 1 reply
J

jacob.glen.perin

· 2 months ago

from enum import Enum

class V(Enum):
  NOT_VISITED=0
  VISTING=1
  NOT_SAFE=2
  SAFE=3
  TERMINAL=4

class Solution:
    def eventualSafeNodes(self, graph):
        n = len(graph)
        result = []

        visited = [V.TERMINAL if not graph[x] else V.NOT_VISITED for x in range(n)]

        for i in range(n):
          if visited[i] != V.NOT_VISITED:
            continue
          s = [(i, 0)]

          while s: 
            v, phase = s.pop()

            if phase == 0:
              if visited[v] == V.VISTING: #cycle
                visited[v] = V.NOT_SAFE
                continue
              if visited[v] != V.NOT_VISITED:
                continue
              
              visited[v] = V.VISTING
              s.append((v, 1))

              for n in graph[v]: