What is the pricing and subscription model for Hi👋SpeedAlgo?

The entire core curriculum of 12 patterns and 201 archetypes is 100% free to access with no credit card required. Students receive 40 free compute coins upon registration, +20 daily login coins, and +25 referral coins. A 24-hour unlimited AI coaching pass costs only 5 coins. Alternatively, developers can use Bring-Your-Own-Key (BYOK) for completely free unlimited AI coaching with personal Gemini or OpenAI keys. There are no recurring subscription fees.

What is the refund and cancellation policy?

Hi👋SpeedAlgo has zero recurring subscriptions, zero automatic renewals, and zero hidden billing traps. Because the core platform and learning materials are free, students never face unwanted credit card charges or recurring payment obligations.

Who creates and maintains the curriculum?

Hi👋SpeedAlgo is developed and maintained by Hi👋WebEnterprise (https://hiwebenterprise.com), an engineering organization focused on developer education, deliberate practice methodologies, and cognitive ergonomics for technical interviews.

How does Hi👋SpeedAlgo prepare candidates for senior and staff SWE interviews?

Rather than rote LeetCode grinding, Hi👋SpeedAlgo enforces deliberate practice: proving invariants, articulating Big-O tradeoffs, managing edge cases, and defending algorithmic approaches to a Senior SWE AI Mock Coach in an integrated Monaco code editor.

17. Bridges (Tarjan's): Critical Connections in a Network (LC 1192) • Invariant Proof & Speed-Run

Theory Context•Graph Algorithms

HardLC 1192

Critical Connections in a Network (LeetCode 1192)

You will see how one DFS with discovery times and low-links finds every critical link of a network.

Target Frequency:AmazonGoogleMeta

Return every critical link of a network of n servers, numbered 0 to n - 1, in any order. The links are the pairs in connections: [ai, bi] is a two-way link between servers ai and bi, and together the links let every server reach every other one, directly or through other servers.

A link is critical when taking it away leaves some server unable to reach some other server. A critical link may be returned as [ai, bi] or as [bi, ai].

Worked Examples

Example 1

Input:n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]

Output:[[1,3]]

Explanation: Servers 0, 1 and 2 form a triangle, so any one of its links can go; the link 1-3 is server 3's only way in. `[[3,1]]` is accepted too.

Example 2

Input:n = 2, connections = [[0,1]]

Output:[[0,1]]

Explanation: The only link is the only way between the two servers.

⚖️Formal Constraints & Bounds

2 <= n <= 10⁵
n - 1 <= connections.length <= 10⁵
0 <= ai, bi <= n - 1
ai != bi
There are no repeated connections.

Deep-Dive & Conceptual Insights

Why It Works & Core Invariant

An edge parent -> node of the DFS tree is critical exactly when nothing in node's subtree can climb to parent or above by another edge, which is low[node] > disc[parent], strictly; one iterative DFS computes disc and low for every server.

Real-World Scenario & Production Applications

Finding single points of failure in a network: a link between data centres, a road or a pipe whose loss cuts one part of the system off from the rest.

Subproblems & Recurrence Decomposition3 Phases

🧩Subproblem 1: Discovery Order on an Explicit Stack

Store both directions of every link with its id, then run the DFS from a stack of frames (node, in_edge, idx), setting disc and low when a server is first reached.

Mathematical Recurrence / Code Invariant

disc[root] = low[root] = time
stack = [(root, -1, 0)]

Step-by-Step Execution Trace Table

Step-by-Step Tarjan (n = 4, connections = [[0,1],[1,2],[2,0],[1,3]])

Step 1 (Start at 0): disc[0] = low[0] = 0, stack = [(0, -1, 0)].
Step 2 (Down to 1, then 2): tree edges 0 -> 1 and 1 -> 2 set disc[1] = low[1] = 1 and disc[2] = low[2] = 2.
Step 3 (A Back Edge): from 2, the edge to 0 is not the edge 2 came in by and 0 is already reached, so low[2] = min(2, disc[0]) = 0.
Step 4 (2 Finishes): low[1] = min(1, 0) = 0; test low[2] > disc[1]: 0 > 1 is false, so 1-2 is on a cycle.
Step 5 (Down to 3 and Back): 3 has no other edge, so it finishes with low[3] = 3; test low[3] > disc[1]: 3 > 1 is true, so 1-3 is a bridge.
Step 6 (1 Finishes): low[0] = min(0, 0) = 0; test low[1] > disc[0]: 0 > 0 is false. Here low[1] equals disc[0]: the >= test would wrongly report 0-1. Return [[1,3]] ✅.

Full Walkthrough6 Steps

Input:n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]Expected:[[1,3]]

1⚡ STEP(Start at 0)

disc[0] = low[0] = 0, stack = [(0, -1, 0)].

2⚡ STEP(Down to 1, then 2)

tree edges 0 -> 1 and 1 -> 2 set disc[1] = low[1] = 1 and disc[2] = low[2] = 2.

3⚡ STEP(A Back Edge)

from 2, the edge to 0 is not the edge 2 came in by and 0 is already reached, so low[2] = min(2, disc[0]) = 0.

4⚡ STEP(2 Finishes)

low[1] = min(1, 0) = 0; test low[2] > disc[1]: 0 > 1 is false, so 1-2 is on a cycle.

5⚡ STEP(Down to 3 and Back)

3 has no other edge, so it finishes with low[3] = 3; test low[3] > disc[1]: 3 > 1 is true, so 1-3 is a bridge.

6✅ RECORD / GOAL(1 Finishes)

low[0] = min(0, 0) = 0; test low[1] > disc[0]: 0 > 0 is false. Here low[1] equals disc[0]: the >= test would wrongly report 0-1. Return [[1,3]] ✅.

Core Invariant Specification & Code Shape

Archetype Code Shape

Python

1	graph with both directions of each edge and its id; disc = [-1] * n; low = [0] * n
2	for each unreached root: an explicit DFS stack of (node, edge in, next index)
3	# next neighbour: skip the edge you came in by; a new node goes deeper, an old one updates low
4	# no neighbour left: pop, pass low up to the parent, test the edge
5	return ...

Target: Critical Connections in a Network (LeetCode 1192). The id tells the tree edge back to the parent apart from any other edge to the same node

Boundary Model: Graph Component Traversal & Visited State Machine

Maintains visited set or 3-color states (WHITE=unvisited, GREY=visiting/cycle, BLACK=processed) across adjacency lists.

Loop Invariant Termination

Loop outer vertices 0..V-1 to handle disconnected subgraphs; explore edges via BFS/DFS/PriorityQueue.

Conceptual Narrative

🧭 Conceptual Foundation & Pattern Intuition

A bridge is an edge whose removal splits an undirected graph. Tarjan's algorithm finds all of them in one depth-first search. It numbers the nodes in the order the DFS reaches them, disc, and for each node computes low: the earliest disc its subtree can reach by going down tree edges and then taking one other edge back up. When a child node finishes, the tree edge from parent to node is a bridge exactly when low[node] > disc[parent]: nothing below node can climb to parent or above, so that edge is the subtree's only connection.

🧗 The Analogy: Ropes on a Climbing Route

Picture the DFS tree as a climbing route hanging down from the root, with each tree edge a rope. Back edges are extra ropes that let a climber lower on the route clip back onto a higher anchor. A rope is critical when nobody below it has any other rope to an anchor at or above its top: cut it and everyone below falls away. low is the highest anchor anyone in a subtree can reach, and a rope is critical when that anchor is strictly below the rope's top.

🪄 Breaking Down the Code's "Magic Trick"

Code / Blueprint

if disc[nxt] == -1:
    disc[nxt] = low[nxt] = time             # tree edge: go deeper
    stack.append((nxt, edge, 0))
else:
    low[node] = min(low[node], disc[nxt])   # back edge: climb higher
...
low[parent] = min(low[parent], low[node])   # a finished child passes its climb up
if low[node] > disc[parent]:                # strictly below parent: a bridge
    bridges.append([parent, node])

Two details carry the algorithm. The edge the DFS came in by is skipped by its id, edge == in_edge, because it is the one edge that must not count as a way back. And the test is strict: when low[node] == disc[parent], the subtree climbs back exactly to parent, the edge sits on a cycle, and it is not a bridge. The >= version of the test answers a different question: whether parent is an articulation point.

💡 Summary

One DFS with disc and low finds every bridge in O(V + E); an explicit stack keeps it safe on graphs with long paths.

🧠 Variable Roles & Pattern Refresher:

disc[u]: when the DFS first reached u; -1 until then.
low[u]: the earliest disc that u's subtree reaches with one edge that isn't its tree edge in.
stack: frames (node, in_edge, idx): the node, the edge id it came in by, and the next neighbour to try.
parent: the node below which node hangs, read when node finishes.

>= instead of >: keep low[node] > disc[parent] strict: with >=, an edge whose subtree climbs back exactly to parent (a cycle through that edge) is reported as a bridge.
Skipping the wrong edge back: skip only the tree edge you came in by, edge == in_edge: skip nothing and every child reaches its parent, so low[node] <= disc[parent] always holds and no bridge is ever found; skip every edge to the parent node and two parallel edges look like a bridge.
Recursion on a long chain: keep the DFS on an explicit stack: Critical Connections in a Network (LC 1192) allows 10^5 servers in one chain, far deeper than a recursion limit.
Articulation points need a different test: as in Minimum Number of Days to Disconnect Island (LC 1568), use low[node] >= disc[parent] for a non-root parent, and count the root only when it has two or more DFS children.

Senior SWE Reasoning Architecture

4-Phase Thought Process Model

You will see how a senior engineer spots a bridge-finding problem and defends the strict low-link test.

Pattern Recognition Signals

The 10-second spot

A link is critical when "taking it away leaves some server unable to reach some other server", in a network of "two-way" links that "let every server reach every other one": the edges whose removal disconnects an undirected graph are its bridges, and Tarjan's algorithm finds all of them in one DFS.

Formulating the Predicate & Invariants

Turning intuition into a boolean rule

disc[u] is the order in which the DFS first reached u; once u is finished, low[u] is the smallest disc its subtree reaches with one edge other than its tree edge in. The tree edge parent -> node is a bridge exactly when low[node] > disc[parent].

Silent Failure Traps & Edge Cases

Where confident candidates still lose points

if low[node] > disc[parent], strict: in Example 1, low[1] == disc[0], and >= would report the link 0-1, which sits on the triangle.
if edge == in_edge: continue: skip only the edge you came in by; skipping nothing lets every child reach its parent, so no bridge is ever found.
stack = [(root, -1, 0)]: with 10^5 servers in a chain, a recursive DFS passes the recursion limit; the explicit stack does not.
low[parent] = min(low[parent], low[node]) after the child finishes: forgetting it leaves low[parent] too high, and edges above a cycle look like bridges.

The 60-Second Interview Pitch

Say this out loud before you type a single line

A critical connection is a bridge, so I'd use Tarjan's bridge algorithm: one depth-first search. I number the servers in the order I reach them, that's disc, and for each server I track low, the earliest disc its subtree can reach with one edge that isn't the tree edge it came in by. Going down a new edge sets the child's disc and low; seeing an old server lowers low. When a child finishes, I pass its low up to the parent and test the edge: if the child's low is strictly greater than the parent's disc, nothing below can climb back, so the edge is a bridge. The trap is that comparison: with greater-or-equal, an edge on a cycle through the parent gets reported. I also keep the search on an explicit stack, because a chain of a hundred thousand servers would blow the recursion limit. It's O(V plus E) time and space.

So: disc and low from one iterative DFS, skip only in_edge, and low[node] > disc[parent] marks a bridge.

Big-O Invariant Derivation

Complexity & Mathematical Proof

TIME COMPLEXITY

O(V + E)

Look at the code: building graph stores each link twice, O(E). The for root loop runs V times. A server is pushed on stack once, when disc[nxt] == -1 turns it from unreached to reached, and popped once when its neighbour index runs out. Each time a frame is on top with neighbours left, one adjacency entry is used; there are 2E entries, so the while stack loop runs at most 2E + 2V times, each with O(1) work. Total: O(V + E).

SPACE COMPLEXITY

O(V + E)

graph holds 2E entries; disc, low and stack hold at most V entries each. There is no recursion, so the call stack is O(1). The output bridges has at most V - 1 links.

Formal Recurrence Relation

T(V, E) = 2E (build) + V (roots) + 2V + 2E (stack steps) = O(V + E)

Derivation Progression

Build the adjacency list

2E appends

Each link is stored in both directions with its id.

Push and pop each server once

at most V pushes and V pops

A server is pushed when first reached (disc goes from -1 to a time) and popped when its neighbours run out.

Look at each adjacency entry once

2E neighbour steps, O(1) each

The frame's idx only moves forward, so every entry is used once: skip, tree edge or back edge.

Variable Definitions

$V$

Number of servers, n

$E$

Number of links, len(connections); the adjacency lists hold 2E entries

Memory Architecture & Bounds

🟣 Call Stack

O(1): an explicit stack, no recursion

🔵 Auxiliary Heap

O(V + E): graph has 2E entries; disc, low and stack have at most V

🟢 Output Space

O(V): at most V - 1 bridges

Boundary Best / Worst Cases

Best Case

$O(V + E)$ : every server and link is visited on every input.

Average Case

$O(V + E)$ .

Worst Case

$O(V + E)$ .

Graph & Tree Traversal Frontier

Synthesizing vector architecture diagram...

Staff+ Engineering Perspective

Senior SWE Deconstruction & Hardware Caveats

ARCHITECTURAL SIGNALS & INTERVIEW TRIGGERS

Triggers: "taking it away leaves some server unable to reach some other server", "two-way". Edges whose removal disconnects an undirected graph are bridges: one DFS with discovery times and low-links (Tarjan's bridges) finds all of them, instead of removing each link and re-checking.

CONSTRAINTS & BOUNDS

$V \le 10^5$ servers, $E \le 10^5$ links. Budget: $O(V + E)$ ; removing each link and re-running a BFS is $O(E \cdot (V + E)) = 10^{10}$ . A chain of $10^5$ servers is also far deeper than a recursion limit, so the DFS runs on an explicit stack.

FAANG PRODUCTION TRAPS & EDGE CASES

The strict comparison (>= is the articulation-point test). Skipping the incoming edge by id, not by neighbour, matters on multigraphs. At scale, recursion depth and the adjacency list's memory are the limits; the iterative version keeps O(V + E) memory and no call stack.

Core Algorithmic State Invariants

1. Discovery Order and Low-Link

disc[u] is when the DFS first reaches u. low[u] is the earliest disc its subtree reaches with one edge that is not its tree edge in: a back edge lowers it with disc[nxt], and a finished child passes its low up.

2. A Bridge Has No Way Back Up

When node finishes, parent -> node is a bridge exactly when low[node] > disc[parent], strictly. If low[node] == disc[parent], the subtree climbs back to parent, the edge sits on a cycle, and >= would report it wrongly.

3. One Iterative DFS

Frames (node, in_edge, idx) on an explicit stack skip only the incoming edge by id and survive a 10^5-server chain. Each server is pushed and popped once and each link seen twice: O(V + E) time and space.

Theory Context•Graph Algorithms

HardLC 1192

Critical Connections in a Network (LeetCode 1192)

You will see how one DFS with discovery times and low-links finds every critical link of a network.

Target Frequency:AmazonGoogleMeta

A link is critical when taking it away leaves some server unable to reach some other server. A critical link may be returned as [ai, bi] or as [bi, ai].

Worked Examples

Example 1

Input:n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]

Output:[[1,3]]

Explanation: Servers 0, 1 and 2 form a triangle, so any one of its links can go; the link 1-3 is server 3's only way in. `[[3,1]]` is accepted too.

Example 2

Input:n = 2, connections = [[0,1]]

Output:[[0,1]]

Explanation: The only link is the only way between the two servers.

⚖️Formal Constraints & Bounds

2 <= n <= 10⁵
n - 1 <= connections.length <= 10⁵
0 <= ai, bi <= n - 1
ai != bi
There are no repeated connections.

Deep-Dive & Conceptual Insights

Why It Works & Core Invariant

Real-World Scenario & Production Applications

Finding single points of failure in a network: a link between data centres, a road or a pipe whose loss cuts one part of the system off from the rest.

Subproblems & Recurrence Decomposition3 Phases

🧩Subproblem 1: Discovery Order on an Explicit Stack

Store both directions of every link with its id, then run the DFS from a stack of frames (node, in_edge, idx), setting disc and low when a server is first reached.

Mathematical Recurrence / Code Invariant

disc[root] = low[root] = time
stack = [(root, -1, 0)]

Step-by-Step Execution Trace Table

Step-by-Step Tarjan (n = 4, connections = [[0,1],[1,2],[2,0],[1,3]])

Step 1 (Start at 0): disc[0] = low[0] = 0, stack = [(0, -1, 0)].
Step 2 (Down to 1, then 2): tree edges 0 -> 1 and 1 -> 2 set disc[1] = low[1] = 1 and disc[2] = low[2] = 2.
Step 3 (A Back Edge): from 2, the edge to 0 is not the edge 2 came in by and 0 is already reached, so low[2] = min(2, disc[0]) = 0.
Step 4 (2 Finishes): low[1] = min(1, 0) = 0; test low[2] > disc[1]: 0 > 1 is false, so 1-2 is on a cycle.
Step 5 (Down to 3 and Back): 3 has no other edge, so it finishes with low[3] = 3; test low[3] > disc[1]: 3 > 1 is true, so 1-3 is a bridge.
Step 6 (1 Finishes): low[0] = min(0, 0) = 0; test low[1] > disc[0]: 0 > 0 is false. Here low[1] equals disc[0]: the >= test would wrongly report 0-1. Return [[1,3]] ✅.

Full Walkthrough6 Steps

Input:n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]Expected:[[1,3]]

1⚡ STEP(Start at 0)

disc[0] = low[0] = 0, stack = [(0, -1, 0)].

2⚡ STEP(Down to 1, then 2)

tree edges 0 -> 1 and 1 -> 2 set disc[1] = low[1] = 1 and disc[2] = low[2] = 2.

3⚡ STEP(A Back Edge)

from 2, the edge to 0 is not the edge 2 came in by and 0 is already reached, so low[2] = min(2, disc[0]) = 0.

4⚡ STEP(2 Finishes)

low[1] = min(1, 0) = 0; test low[2] > disc[1]: 0 > 1 is false, so 1-2 is on a cycle.

5⚡ STEP(Down to 3 and Back)

3 has no other edge, so it finishes with low[3] = 3; test low[3] > disc[1]: 3 > 1 is true, so 1-3 is a bridge.

6✅ RECORD / GOAL(1 Finishes)

low[0] = min(0, 0) = 0; test low[1] > disc[0]: 0 > 0 is false. Here low[1] equals disc[0]: the >= test would wrongly report 0-1. Return [[1,3]] ✅.

Core Invariant Specification & Code Shape

Archetype Code Shape

Python

1	graph with both directions of each edge and its id; disc = [-1] * n; low = [0] * n
2	for each unreached root: an explicit DFS stack of (node, edge in, next index)
3	# next neighbour: skip the edge you came in by; a new node goes deeper, an old one updates low
4	# no neighbour left: pop, pass low up to the parent, test the edge
5	return ...

Target: Critical Connections in a Network (LeetCode 1192). The id tells the tree edge back to the parent apart from any other edge to the same node

Boundary Model: Graph Component Traversal & Visited State Machine

Maintains visited set or 3-color states (WHITE=unvisited, GREY=visiting/cycle, BLACK=processed) across adjacency lists.

Loop Invariant Termination

Loop outer vertices 0..V-1 to handle disconnected subgraphs; explore edges via BFS/DFS/PriorityQueue.

Conceptual Narrative

🧭 Conceptual Foundation & Pattern Intuition

🧗 The Analogy: Ropes on a Climbing Route

🪄 Breaking Down the Code's "Magic Trick"

Code / Blueprint

if disc[nxt] == -1:
    disc[nxt] = low[nxt] = time             # tree edge: go deeper
    stack.append((nxt, edge, 0))
else:
    low[node] = min(low[node], disc[nxt])   # back edge: climb higher
...
low[parent] = min(low[parent], low[node])   # a finished child passes its climb up
if low[node] > disc[parent]:                # strictly below parent: a bridge
    bridges.append([parent, node])

💡 Summary

One DFS with disc and low finds every bridge in O(V + E); an explicit stack keeps it safe on graphs with long paths.

🧠 Variable Roles & Pattern Refresher:

disc[u]: when the DFS first reached u; -1 until then.
low[u]: the earliest disc that u's subtree reaches with one edge that isn't its tree edge in.
stack: frames (node, in_edge, idx): the node, the edge id it came in by, and the next neighbour to try.
parent: the node below which node hangs, read when node finishes.

>= instead of >: keep low[node] > disc[parent] strict: with >=, an edge whose subtree climbs back exactly to parent (a cycle through that edge) is reported as a bridge.
Skipping the wrong edge back: skip only the tree edge you came in by, edge == in_edge: skip nothing and every child reaches its parent, so low[node] <= disc[parent] always holds and no bridge is ever found; skip every edge to the parent node and two parallel edges look like a bridge.
Recursion on a long chain: keep the DFS on an explicit stack: Critical Connections in a Network (LC 1192) allows 10^5 servers in one chain, far deeper than a recursion limit.
Articulation points need a different test: as in Minimum Number of Days to Disconnect Island (LC 1568), use low[node] >= disc[parent] for a non-root parent, and count the root only when it has two or more DFS children.

Senior SWE Reasoning Architecture

4-Phase Thought Process Model

You will see how a senior engineer spots a bridge-finding problem and defends the strict low-link test.

Pattern Recognition Signals

The 10-second spot

Formulating the Predicate & Invariants

Turning intuition into a boolean rule

Silent Failure Traps & Edge Cases

Where confident candidates still lose points

if low[node] > disc[parent], strict: in Example 1, low[1] == disc[0], and >= would report the link 0-1, which sits on the triangle.
if edge == in_edge: continue: skip only the edge you came in by; skipping nothing lets every child reach its parent, so no bridge is ever found.
stack = [(root, -1, 0)]: with 10^5 servers in a chain, a recursive DFS passes the recursion limit; the explicit stack does not.
low[parent] = min(low[parent], low[node]) after the child finishes: forgetting it leaves low[parent] too high, and edges above a cycle look like bridges.

The 60-Second Interview Pitch

Say this out loud before you type a single line

A critical connection is a bridge, so I'd use Tarjan's bridge algorithm: one depth-first search. I number the servers in the order I reach them, that's disc, and for each server I track low, the earliest disc its subtree can reach with one edge that isn't the tree edge it came in by. Going down a new edge sets the child's disc and low; seeing an old server lowers low. When a child finishes, I pass its low up to the parent and test the edge: if the child's low is strictly greater than the parent's disc, nothing below can climb back, so the edge is a bridge. The trap is that comparison: with greater-or-equal, an edge on a cycle through the parent gets reported. I also keep the search on an explicit stack, because a chain of a hundred thousand servers would blow the recursion limit. It's O(V plus E) time and space.

So: disc and low from one iterative DFS, skip only in_edge, and low[node] > disc[parent] marks a bridge.

Big-O Invariant Derivation

Complexity & Mathematical Proof

TIME COMPLEXITY

O(V + E)

SPACE COMPLEXITY

O(V + E)

graph holds 2E entries; disc, low and stack hold at most V entries each. There is no recursion, so the call stack is O(1). The output bridges has at most V - 1 links.

Formal Recurrence Relation

T(V, E) = 2E (build) + V (roots) + 2V + 2E (stack steps) = O(V + E)

Derivation Progression

Build the adjacency list

2E appends

Each link is stored in both directions with its id.

Push and pop each server once

at most V pushes and V pops

A server is pushed when first reached (disc goes from -1 to a time) and popped when its neighbours run out.

Look at each adjacency entry once

2E neighbour steps, O(1) each

The frame's idx only moves forward, so every entry is used once: skip, tree edge or back edge.

Variable Definitions

$V$

Number of servers, n

$E$

Number of links, len(connections); the adjacency lists hold 2E entries

Memory Architecture & Bounds

🟣 Call Stack

O(1): an explicit stack, no recursion

🔵 Auxiliary Heap

O(V + E): graph has 2E entries; disc, low and stack have at most V

🟢 Output Space

O(V): at most V - 1 bridges

Boundary Best / Worst Cases

Best Case

$O(V + E)$ : every server and link is visited on every input.

Average Case

$O(V + E)$ .

Worst Case

$O(V + E)$ .

Graph & Tree Traversal Frontier

Synthesizing vector architecture diagram...

Staff+ Engineering Perspective

Senior SWE Deconstruction & Hardware Caveats

ARCHITECTURAL SIGNALS & INTERVIEW TRIGGERS

CONSTRAINTS & BOUNDS

FAANG PRODUCTION TRAPS & EDGE CASES

Core Algorithmic State Invariants

1. Discovery Order and Low-Link

2. A Bridge Has No Way Back Up

3. One Iterative DFS

Rosetta Dual-Monaco Comparison

Python 3

CANONICAL INVARIANT TEMPLATE

CONCRETE: CRITICAL CONNECTIONS IN A NETWORK (LEETCODE 1192)

T = O(V + E)S = O(V + E)

Pattern Implementation Mapping TableCanonical Invariant ⟷ Concrete Code ⟷ Engineering Rationale

Canonical Invariant	Concrete Code	Engineering Rationale
Both directions of every edge, with its id	`for i, (u, v) in enumerate(connections): graph[u].append((v, i)) graph[v].append((u, i))`	The id tells the tree edge back to the parent apart from any other edge to the same node
Discovery order and the lowest reachable order	`disc = [-1] * n low = [0] * n`	disc numbers the nodes in DFS order; low records how high a subtree can climb with one non-tree edge
An explicit DFS stack	`stack = [(root, -1, 0)] node, in_edge, idx = stack[-1]`	Each frame remembers the edge it came in by and the next neighbour to try, so 10^5 servers never hit a recursion limit
Skip only the edge you came in by	`if edge == in_edge: continue`	Every other edge to an earlier node is a way back up and lowers low[node]
Tree edge down, back edge up	`disc[nxt] = low[nxt] = time stack.append((nxt, edge, 0)) low[node] = min(low[node], disc[nxt])`	A new node goes deeper; an old one is a back edge that the subtree can climb
A finished child passes its low up and is tested	`low[parent] = min(low[parent], low[node]) if low[node] > disc[parent]: bridges.append([parent, node])`	The trap line: strictly greater means nothing below node reaches parent or above, so the edge is a bridge

if disc[nxt] == -1: disc[nxt] = low[nxt] = time # tree edge: go deeper stack.append((nxt, edge, 0)) else: low[node] = min(low[node], disc[nxt]) # back edge: climb higher ... low[parent] = min(low[parent], low[node]) # a finished child passes its climb up if low[node] > disc[parent]: # strictly below parent: a bridge bridges.append([parent, node])

Canonical Invariant

Concrete Code

Engineering Rationale

Both directions of every edge, with its id

for i, (u, v) in enumerate(connections):
graph[u].append((v, i))
graph[v].append((u, i))

The id tells the tree edge back to the parent apart from any other edge to the same node

Discovery order and the lowest reachable order

disc = [-1] * n
low = [0] * n

disc numbers the nodes in DFS order; low records how high a subtree can climb with one non-tree edge

An explicit DFS stack

stack = [(root, -1, 0)]
node, in_edge, idx = stack[-1]

Each frame remembers the edge it came in by and the next neighbour to try, so 10^5 servers never hit a recursion limit

Skip only the edge you came in by

if edge == in_edge:
continue

Every other edge to an earlier node is a way back up and lowers low[node]

Tree edge down, back edge up

disc[nxt] = low[nxt] = time
stack.append((nxt, edge, 0))
low[node] = min(low[node], disc[nxt])

A new node goes deeper; an old one is a back edge that the subtree can climb

A finished child passes its low up and is tested

low[parent] = min(low[parent], low[node])
if low[node] > disc[parent]:
bridges.append([parent, node])

The trap line: strictly greater means nothing below node reaches parent or above, so the edge is a bridge