Validate Evaluation Chains and Resolve Boolean Outcomes

A collection of evaluations forms directed chains. Each evaluation points either to another evaluation or directly to the terminal value true or false. A chain is invalid if following its pointers enters a cycle.

Determine the outcome of every evaluation, including evaluations in disconnected components.

Function Contract

Implement evaluate_chains(targets) -> list[int], where targets is an integer array of length n. Evaluation identifiers are 0 through n - 1.

• targets[i] == -2 means evaluation i points directly to true.
• targets[i] == -1 means evaluation i points directly to false.
• Otherwise, targets[i] is the identifier of the next evaluation.

Return an integer array of length n in evaluation-identifier order:

• 1 if the chain starting at that evaluation reaches true.
• 0 if it reaches false.
• -1 if it enters a cycle, whether the starting evaluation belongs to the cycle or merely leads into it.

All evaluations are valid exactly when the returned array contains no -1. A valid chain that ends at false is different from an invalid chain.

Constraints and Clarifications

The integer identifiers and terminal encodings are explicit interface choices for this exercise.

• 0 <= n <= 200000.
• Each target is -2, -1, or an integer from 0 through n - 1; there are no missing evaluation references.
• Every evaluation has exactly one target. Several evaluations may share a target.
• Self-loops are cycles, and disconnected components must all be checked.
• For an empty collection, return []; the collection has no invalid evaluations.
• Aim for O(n) total time and O(n) additional space.

Examples

targets = [1, -2, -1]
Output: [1, 1, 0]

Evaluation 0 reaches true through evaluation 1. Evaluation 2 forms a separate chain ending at false.

targets = [1, 2, 1, -1, 3]
Output: [-1, -1, -1, 0, 0]

Evaluations 1 and 2 form a cycle. Evaluation 0 leads into that cycle. Evaluations 3 and 4 remain valid and both resolve to false.

Hint: Distinguish current paths from completed paths

Reaching a node already on the current unresolved path means something different from reaching a node whose final outcome has already been established.

Resolve Evaluation Chains to True, False, or Invalid

A collection of n evaluations forms directed chains. Evaluation identifiers are 0 through n - 1, and every evaluation points to exactly one target, given by the integer array targets of length n:

• targets[i] == -2 means evaluation i points directly to the terminal value true.
• targets[i] == -1 means evaluation i points directly to the terminal value false.
• Otherwise targets[i] is the identifier of the next evaluation in the chain, an integer from 0 through n - 1.

Following an evaluation's pointers therefore either reaches a terminal value or enters a cycle. A chain is invalid exactly when following its pointers enters a cycle.

Implement evaluate_chains(targets). Return an integer array of length n in evaluation-identifier order, where position i describes evaluation i:

• 1 if the chain starting at that evaluation reaches true.
• 0 if it reaches false.
• -1 if it enters a cycle, whether the starting evaluation belongs to the cycle or merely leads into it.

Several evaluations may share a target, self-loops are cycles, and evaluations in disconnected components must all be checked. All evaluations are valid exactly when the returned array contains no -1; a valid chain that ends at false (result 0) is different from an invalid chain (result -1). For an empty collection, return []; such a collection has no invalid evaluations.

Every value involved fits in a signed 32-bit integer: inputs range from -2 to n - 1 and results are always -1, 0, or 1, so no 64-bit type is needed.

Example 1

targets = [1, -2, -1]
Output: [1, 1, 0]

Evaluation 0 reaches true through evaluation 1. Evaluation 2 forms a separate chain ending at false.

Example 2

targets = [1, 2, 1, -1, 3]
Output: [-1, -1, -1, 0, 0]

Evaluations 1 and 2 form a cycle. Evaluation 0 leads into that cycle, so it is invalid as well. Evaluations 3 and 4 remain valid and both resolve to false.

Hints

1. Every evaluation has exactly one target, so an evaluation's outcome is fully determined by the outcome of the single evaluation or terminal it points at.
2. Reaching a node that is still part of the path you are currently following means something different from reaching a node whose final outcome has already been established.
3. The stated O(n) bound means each evaluation should be touched a constant number of times overall, and chains can be up to 200000 long, so avoid deep recursion.

Approach

Because every evaluation has exactly one target, the pointer structure is a functional graph: the outcome of evaluation i is entirely determined by the outcome of the single node (or terminal) it points at. So each node has one well-defined answer, and every node on a walk that ends at the same place shares that answer.

Algorithm. Keep two arrays: result[i] and state[i], where state is 0 (unvisited), 1 (currently on the walk being explored) or 2 (resolved). For each start index whose state is still 0, walk forward collecting the visited nodes in a path list and marking each as state 1. The walk stops in exactly one of four ways: the next pointer is -2 (outcome 1), the next pointer is -1 (outcome 0), the next node has state 1 (it is on the current walk, so the walk has closed a cycle and the outcome is -1), or the next node has state 2 (already resolved, so the outcome is that node's stored result). Then assign the outcome to every node collected on this walk and mark them state 2.

Invariant. A node with state 2 already holds its final answer, and a node with state 1 is an ancestor of the current position on the current walk. Both invariants hold at each step: nodes only become state 2 after the walk they belong to has terminated, and state 1 is only set as a node is appended to the path currently being followed.

Correctness. If the walk reaches a terminal, every node collected lies on the chain that reaches that terminal, so all of them share its value (1 or 0). If it reaches a state-1 node, that node lies on the current path, so the segment from it forward is a cycle and every collected node either belongs to the cycle or leads into it; by the definition given, all of them are -1. If it reaches a state-2 node, the current chain merges into an already-resolved chain and inherits its answer, which is correct because the outcome only depends on where the pointers lead; propagating -1 through this branch also handles tails that merge into a previously discovered cycle. Every node is pushed onto a path exactly once (it is marked state 1 the moment it is appended and never revisited as an unvisited node), so the total work is O(n) time and O(n) extra space for the three arrays.

Edge cases. n = 0 returns [] immediately. A self-loop targets[i] == i is caught because node i is state 1 when the walk steps back onto it. A chain ending at false returns 0 and must not be confused with the -1 invalid marker. Nodes that merely share a target with a valid chain inherit that chain's valid outcome rather than being reported as cycles, which is why the state-2 check is separate from the state-1 check. Chains can be up to 200000 nodes long, so the walk is iterative; a recursive formulation would overflow the stack.

• Time complexity: O(n)
• Space complexity: O(n)