FastPrep
Problem · Graph

Process Graph Rule Validation

Learn this problem
● HardHadrian logoHadrianFULLTIMEPHONE SCREEN

Problem statement

A process system is represented by a directed acyclic graph. Node i has type processTypes.charAt(i), one of A, B, C, or D. Each row [u, v] in edges means that process u can be followed directly by process v.

A complete execution path starts at any node with indegree 0 and ends at any node with outdegree 0. The system is valid only if every complete execution path satisfies all three rules:

  1. The path contains at least one process of type B.
  2. No process of type A appears before a later process of type B on the same path.
  3. Every process of type D has at least one earlier process of type C on the same path.

Return true when every complete execution path is valid; otherwise return false.

Function

isValidProcessSystem(processTypes: String, edges: int[][]) → boolean

Examples

Example 1

processTypes = "BCAD"edges = [[0,1],[1,2],[2,3]]return = true

The only complete path is B -> C -> A -> D. It contains B, its B is before its A, and its D has an earlier C.

Example 2

processTypes = "AB"edges = [[0,1]]return = false

The path contains an A before a later B, which violates the second rule.

Example 3

processTypes = "BCBD"edges = [[0,1],[0,2],[1,3],[2,3]]return = false

The path 0 -> 2 -> 3 reaches D without an earlier C. One invalid complete path makes the whole system invalid.

Constraints

  • 1 <= processTypes.length <= 100000
  • Every character of processTypes is A, B, C, or D.
  • 0 <= edges.length <= 200000
  • Every edge has the form [u, v], where 0 <= u, v < processTypes.length and u != v.
  • The edges are unique and the directed graph is acyclic.
drafts saved locally
public boolean isValidProcessSystem(String processTypes, int[][] edges) {
    // Write your solution here
}
processTypes"BCAD"
edges[[0,1],[1,2],[2,3]]
expectedtrue
checking account