Count the Nodes in a Chain Reachable Only Through Left and Right Links

A chain of nodes is linked in a line. Each node can reach only its two neighbors, the node on its left and the node on its right; there is no head pointer, no stored length and no list of all nodes. You are handed one node somewhere in the chain. Count the nodes in the whole chain.

For this console, nodes are numbered, and the nodes of several separate chains are given together. links[i] = [left, right] holds the numbers of node i's left and right neighbors, with -1 where there is no neighbor on that side. Starting from node start, return the number of nodes in the chain that contains it.

The interviewer also expected you to write your own test cases.

Function Signature

def count_chain_nodes(links: list[list[int]], start: int) -> int:

Rules

• The links are consistent: for any two nodes i and j, links[i][1] == j exactly when links[j][0] == i. In words, j is the right neighbor of i exactly when i is the left neighbor of j.
• Every chain is a straight line with two ends. Following right links from any node ends at a node whose right neighbor is -1, and following left links ends at a node whose left neighbor is -1; no chain closes into a loop.
• A node whose two neighbors are both -1 forms a chain of one node.
• The count includes start itself.

Constraints

• 1 <= n <= 10^5, where n = len(links)
• Each links[i] has exactly two entries; each entry is -1 or an integer in [0, n - 1], and never equals i
• 0 <= start < n

Examples

Example 1

Input: links = [[-1, 1], [0, 2], [1, 3], [2, -1]], start = 2
Output: 4

From node 2, the left side holds nodes 1 and 0 and the right side holds node 3, so the chain is 0, 1, 2, 3.

Example 2

Input: links = [[2, -1], [-1, 3], [4, 0], [1, -1], [-1, 2]], start = 0
Output: 3

Node 0 has no right neighbor; to its left are node 2 and then node 4, which has no left neighbor. The chain is 4, 2, 0. Nodes 1 and 3 form a separate chain and are not counted.

Example 3

Input: links = [[-1, -1]], start = 0
Output: 1