Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.
You are given a directed acyclic graph of n nodes numbered from 0 to n − 1. This is represented by a 2D array edges of length m, where edges[i] = [ui, vi, costi] indicates a one‑way communication from node ui to node vi with a recovery cost of costi.
Some nodes may be offline. You are given a boolean array online where online[i] = true means node i is online. Nodes 0 and n − 1 are always online.
A path from 0 to n − 1 is valid if:
k.For each valid path, define its score as the minimum edge‑cost along that path.
Return the maximum path score (i.e., the largest minimum-edge cost) among all valid paths. If no valid path exists, return -1.
Example 1:
Input: edges = [[0,1,5],[1,3,10],[0,2,3],[2,3,4]], online = [true,true,true,true], k = 10
Output: 3
Explanation:
The graph has two possible routes from node 0 to node 3:
Path 0 → 1 → 3
Total cost = 5 + 10 = 15, which exceeds k (15 > 10), so this path is invalid.
Path 0 → 2 → 3
Total cost = 3 + 4 = 7 <= k, so this path is valid.
The minimum edge‐cost along this path is min(3, 4) = 3.
There are no other valid paths. Hence, the maximum among all valid path‐scores is 3.
Example 2:
Input: edges = [[0,1,7],[1,4,5],[0,2,6],[2,3,6],[3,4,2],[2,4,6]], online = [true,true,true,false,true], k = 12
Output: 6
Explanation:
Node 3 is offline, so any path passing through 3 is invalid.
Consider the remaining routes from 0 to 4:
Path 0 → 1 → 4
Total cost = 7 + 5 = 12 <= k, so this path is valid.
The minimum edge‐cost along this path is min(7, 5) = 5.
Path 0 → 2 → 3 → 4
Node 3 is offline, so this path is invalid regardless of cost.
Path 0 → 2 → 4
Total cost = 6 + 6 = 12 <= k, so this path is valid.
The minimum edge‐cost along this path is min(6, 6) = 6.
Among the two valid paths, their scores are 5 and 6. Therefore, the answer is 6.
Constraints:
n == online.length2 <= n <= 5 * 1040 <= m == edges.length <= min(105, n * (n - 1) / 2)edges[i] = [ui, vi, costi]0 <= ui, vi < nui != vi0 <= costi <= 1090 <= k <= 5 * 1013online[i] is either true or false, and both online[0] and online[n − 1] are true.Problem summary: You are given a directed acyclic graph of n nodes numbered from 0 to n − 1. This is represented by a 2D array edges of length m, where edges[i] = [ui, vi, costi] indicates a one‑way communication from node ui to node vi with a recovery cost of costi. Some nodes may be offline. You are given a boolean array online where online[i] = true means node i is online. Nodes 0 and n − 1 are always online. A path from 0 to n − 1 is valid if: All intermediate nodes on the path are online. The total recovery cost of all edges on the path does not exceed k. For each valid path, define its score as the minimum edge‑cost along that path. Return the maximum path score (i.e., the largest minimum-edge cost) among all valid paths. If no valid path exists, return -1.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array · Binary Search · Dynamic Programming · Topological Sort
[[0,1,5],[1,3,10],[0,2,3],[2,3,4]] [true,true,true,true] 10
[[0,1,7],[1,4,5],[0,2,6],[2,3,6],[3,4,2],[2,4,6]] [true,true,true,false,true] 12
Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #3620: Network Recovery Pathways
// Auto-generated Java example from go.
class Solution {
public void exampleSolution() {
}
}
// Reference (go):
// // Accepted solution for LeetCode #3620: Network Recovery Pathways
// package main
//
// import (
// "math"
// "slices"
// "sort"
// )
//
// // https://space.bilibili.com/206214
// func findMaxPathScore1(edges [][]int, online []bool, k int64) int {
// n := len(online)
// type edge struct{ to, wt int }
// g := make([][]edge, n)
// maxWt := -1
// for _, e := range edges {
// x, y, wt := e[0], e[1], e[2]
// if online[x] && online[y] {
// g[x] = append(g[x], edge{y, wt})
// if x == 0 {
// maxWt = max(maxWt, wt)
// }
// }
// }
//
// memo := make([]int, n)
// // 二分无法到达 n-1 的最小 lower，那么减一后，就是可以到达 n-1 的最大 lower
// ans := sort.Search(maxWt+1, func(lower int) bool {
// for i := range memo {
// memo[i] = -1
// }
// var dfs func(int) int
// dfs = func(x int) int {
// if x == n-1 { // 到达终点
// return 0
// }
// p := &memo[x]
// if *p != -1 { // 之前计算过
// return *p
// }
// res := math.MaxInt / 2 // 防止加法溢出
// for _, e := range g[x] {
// y := e.to
// if e.wt >= lower {
// res = min(res, dfs(y)+e.wt)
// }
// }
// *p = res // 记忆化
// return res
// }
// return dfs(0) > int(k)
// }) - 1
// return ans
// }
//
// func findMaxPathScore(edges [][]int, online []bool, k int64) int {
// n := len(online)
// type edge struct{ to, wt int }
// g := make([][]edge, n)
// deg := make([]int, n)
// maxWt := 0
// for _, e := range edges {
// x, y, wt := e[0], e[1], e[2]
// if online[x] && online[y] {
// g[x] = append(g[x], edge{y, wt})
// deg[y]++
// maxWt = max(maxWt, wt)
// }
// }
//
// // 先清理无法从 0 到达的边，比如 2 -> 0
// q := []int{}
// for i := 1; i < n; i++ {
// if deg[i] == 0 {
// q = append(q, i)
// }
// }
// for len(q) > 0 {
// x := q[0]
// q = q[1:]
// for _, e := range g[x] {
// y := e.to
// deg[y]--
// if deg[y] == 0 && y > 0 {
// q = append(q, y)
// }
// }
// }
//
// f := make([]int, n)
// ans := sort.Search(maxWt+1, func(lower int) bool {
// deg := slices.Clone(deg)
// for i := 1; i < n; i++ {
// f[i] = math.MaxInt / 2
// }
//
// q := []int{0}
// for len(q) > 0 {
// x := q[0]
// if x == n-1 {
// return f[x] > int(k)
// }
// q = q[1:]
// for _, e := range g[x] {
// y := e.to
// wt := e.wt
// if wt >= lower {
// f[y] = min(f[y], f[x]+wt)
// }
// deg[y]--
// if deg[y] == 0 {
// q = append(q, y)
// }
// }
// }
// return true
// }) - 1
// return ans
// }
// Accepted solution for LeetCode #3620: Network Recovery Pathways
package main
import (
"math"
"slices"
"sort"
)
// https://space.bilibili.com/206214
func findMaxPathScore1(edges [][]int, online []bool, k int64) int {
n := len(online)
type edge struct{ to, wt int }
g := make([][]edge, n)
maxWt := -1
for _, e := range edges {
x, y, wt := e[0], e[1], e[2]
if online[x] && online[y] {
g[x] = append(g[x], edge{y, wt})
if x == 0 {
maxWt = max(maxWt, wt)
}
}
}
memo := make([]int, n)
// 二分无法到达 n-1 的最小 lower，那么减一后，就是可以到达 n-1 的最大 lower
ans := sort.Search(maxWt+1, func(lower int) bool {
for i := range memo {
memo[i] = -1
}
var dfs func(int) int
dfs = func(x int) int {
if x == n-1 { // 到达终点
return 0
}
p := &memo[x]
if *p != -1 { // 之前计算过
return *p
}
res := math.MaxInt / 2 // 防止加法溢出
for _, e := range g[x] {
y := e.to
if e.wt >= lower {
res = min(res, dfs(y)+e.wt)
}
}
*p = res // 记忆化
return res
}
return dfs(0) > int(k)
}) - 1
return ans
}
func findMaxPathScore(edges [][]int, online []bool, k int64) int {
n := len(online)
type edge struct{ to, wt int }
g := make([][]edge, n)
deg := make([]int, n)
maxWt := 0
for _, e := range edges {
x, y, wt := e[0], e[1], e[2]
if online[x] && online[y] {
g[x] = append(g[x], edge{y, wt})
deg[y]++
maxWt = max(maxWt, wt)
}
}
// 先清理无法从 0 到达的边，比如 2 -> 0
q := []int{}
for i := 1; i < n; i++ {
if deg[i] == 0 {
q = append(q, i)
}
}
for len(q) > 0 {
x := q[0]
q = q[1:]
for _, e := range g[x] {
y := e.to
deg[y]--
if deg[y] == 0 && y > 0 {
q = append(q, y)
}
}
}
f := make([]int, n)
ans := sort.Search(maxWt+1, func(lower int) bool {
deg := slices.Clone(deg)
for i := 1; i < n; i++ {
f[i] = math.MaxInt / 2
}
q := []int{0}
for len(q) > 0 {
x := q[0]
if x == n-1 {
return f[x] > int(k)
}
q = q[1:]
for _, e := range g[x] {
y := e.to
wt := e.wt
if wt >= lower {
f[y] = min(f[y], f[x]+wt)
}
deg[y]--
if deg[y] == 0 {
q = append(q, y)
}
}
}
return true
}) - 1
return ans
}
# Accepted solution for LeetCode #3620: Network Recovery Pathways
# Time: O((n + e) * logr), r = max(e[2] for e in edges)
# Space: O(n + e)
# binary search, topological sort, dp
class Solution(object):
def findMaxPathScore(self, edges, online, k):
"""
:type edges: List[List[int]]
:type online: List[bool]
:type k: int
:rtype: int
"""
INF = float("inf")
def binary_search_right(left, right, check):
while left <= right:
mid = left+(right-left)//2
if not check(mid):
right = mid-1
else:
left = mid+1
return right
def topological_sort():
in_degree = [0]*len(adj)
for u in xrange(len(adj)):
for v, _ in adj[u]:
in_degree[v] += 1
result = []
q = [u for u in xrange(len(adj)) if not in_degree[u]]
while q:
new_q = []
for u in q:
result.append(u)
for v, _ in adj[u]:
in_degree[v] -= 1
if in_degree[v]:
continue
new_q.append(v)
q = new_q
return result
def check(x):
dist = [INF]*len(adj)
dist[0] = 0
for u in order:
if dist[u] == INF:
continue
for v, c in adj[u]:
if not (c >= x and online[v]):
continue
dist[v] = min(dist[v], dist[u]+c)
return dist[-1] <= k
adj = [[] for _ in xrange(len(online))]
for u, v, c in edges:
adj[u].append((v, c))
order = topological_sort()
left, right = INF, 0
for u in xrange(len(adj)):
for _, c in adj[u]:
left = min(left, c)
right = max(right, c)
result = binary_search_right(left, right, check)
return result if result >= left else -1
// Accepted solution for LeetCode #3620: Network Recovery Pathways
// Rust example auto-generated from go reference.
// Replace the signature and local types with the exact LeetCode harness for this problem.
impl Solution {
pub fn rust_example() {
// Port the logic from the reference block below.
}
}
// Reference (go):
// // Accepted solution for LeetCode #3620: Network Recovery Pathways
// package main
//
// import (
// "math"
// "slices"
// "sort"
// )
//
// // https://space.bilibili.com/206214
// func findMaxPathScore1(edges [][]int, online []bool, k int64) int {
// n := len(online)
// type edge struct{ to, wt int }
// g := make([][]edge, n)
// maxWt := -1
// for _, e := range edges {
// x, y, wt := e[0], e[1], e[2]
// if online[x] && online[y] {
// g[x] = append(g[x], edge{y, wt})
// if x == 0 {
// maxWt = max(maxWt, wt)
// }
// }
// }
//
// memo := make([]int, n)
// // 二分无法到达 n-1 的最小 lower，那么减一后，就是可以到达 n-1 的最大 lower
// ans := sort.Search(maxWt+1, func(lower int) bool {
// for i := range memo {
// memo[i] = -1
// }
// var dfs func(int) int
// dfs = func(x int) int {
// if x == n-1 { // 到达终点
// return 0
// }
// p := &memo[x]
// if *p != -1 { // 之前计算过
// return *p
// }
// res := math.MaxInt / 2 // 防止加法溢出
// for _, e := range g[x] {
// y := e.to
// if e.wt >= lower {
// res = min(res, dfs(y)+e.wt)
// }
// }
// *p = res // 记忆化
// return res
// }
// return dfs(0) > int(k)
// }) - 1
// return ans
// }
//
// func findMaxPathScore(edges [][]int, online []bool, k int64) int {
// n := len(online)
// type edge struct{ to, wt int }
// g := make([][]edge, n)
// deg := make([]int, n)
// maxWt := 0
// for _, e := range edges {
// x, y, wt := e[0], e[1], e[2]
// if online[x] && online[y] {
// g[x] = append(g[x], edge{y, wt})
// deg[y]++
// maxWt = max(maxWt, wt)
// }
// }
//
// // 先清理无法从 0 到达的边，比如 2 -> 0
// q := []int{}
// for i := 1; i < n; i++ {
// if deg[i] == 0 {
// q = append(q, i)
// }
// }
// for len(q) > 0 {
// x := q[0]
// q = q[1:]
// for _, e := range g[x] {
// y := e.to
// deg[y]--
// if deg[y] == 0 && y > 0 {
// q = append(q, y)
// }
// }
// }
//
// f := make([]int, n)
// ans := sort.Search(maxWt+1, func(lower int) bool {
// deg := slices.Clone(deg)
// for i := 1; i < n; i++ {
// f[i] = math.MaxInt / 2
// }
//
// q := []int{0}
// for len(q) > 0 {
// x := q[0]
// if x == n-1 {
// return f[x] > int(k)
// }
// q = q[1:]
// for _, e := range g[x] {
// y := e.to
// wt := e.wt
// if wt >= lower {
// f[y] = min(f[y], f[x]+wt)
// }
// deg[y]--
// if deg[y] == 0 {
// q = append(q, y)
// }
// }
// }
// return true
// }) - 1
// return ans
// }
// Accepted solution for LeetCode #3620: Network Recovery Pathways
// Auto-generated TypeScript example from go.
function exampleSolution(): void {
}
// Reference (go):
// // Accepted solution for LeetCode #3620: Network Recovery Pathways
// package main
//
// import (
// "math"
// "slices"
// "sort"
// )
//
// // https://space.bilibili.com/206214
// func findMaxPathScore1(edges [][]int, online []bool, k int64) int {
// n := len(online)
// type edge struct{ to, wt int }
// g := make([][]edge, n)
// maxWt := -1
// for _, e := range edges {
// x, y, wt := e[0], e[1], e[2]
// if online[x] && online[y] {
// g[x] = append(g[x], edge{y, wt})
// if x == 0 {
// maxWt = max(maxWt, wt)
// }
// }
// }
//
// memo := make([]int, n)
// // 二分无法到达 n-1 的最小 lower，那么减一后，就是可以到达 n-1 的最大 lower
// ans := sort.Search(maxWt+1, func(lower int) bool {
// for i := range memo {
// memo[i] = -1
// }
// var dfs func(int) int
// dfs = func(x int) int {
// if x == n-1 { // 到达终点
// return 0
// }
// p := &memo[x]
// if *p != -1 { // 之前计算过
// return *p
// }
// res := math.MaxInt / 2 // 防止加法溢出
// for _, e := range g[x] {
// y := e.to
// if e.wt >= lower {
// res = min(res, dfs(y)+e.wt)
// }
// }
// *p = res // 记忆化
// return res
// }
// return dfs(0) > int(k)
// }) - 1
// return ans
// }
//
// func findMaxPathScore(edges [][]int, online []bool, k int64) int {
// n := len(online)
// type edge struct{ to, wt int }
// g := make([][]edge, n)
// deg := make([]int, n)
// maxWt := 0
// for _, e := range edges {
// x, y, wt := e[0], e[1], e[2]
// if online[x] && online[y] {
// g[x] = append(g[x], edge{y, wt})
// deg[y]++
// maxWt = max(maxWt, wt)
// }
// }
//
// // 先清理无法从 0 到达的边，比如 2 -> 0
// q := []int{}
// for i := 1; i < n; i++ {
// if deg[i] == 0 {
// q = append(q, i)
// }
// }
// for len(q) > 0 {
// x := q[0]
// q = q[1:]
// for _, e := range g[x] {
// y := e.to
// deg[y]--
// if deg[y] == 0 && y > 0 {
// q = append(q, y)
// }
// }
// }
//
// f := make([]int, n)
// ans := sort.Search(maxWt+1, func(lower int) bool {
// deg := slices.Clone(deg)
// for i := 1; i < n; i++ {
// f[i] = math.MaxInt / 2
// }
//
// q := []int{0}
// for len(q) > 0 {
// x := q[0]
// if x == n-1 {
// return f[x] > int(k)
// }
// q = q[1:]
// for _, e := range g[x] {
// y := e.to
// wt := e.wt
// if wt >= lower {
// f[y] = min(f[y], f[x]+wt)
// }
// deg[y]--
// if deg[y] == 0 {
// q = append(q, y)
// }
// }
// }
// return true
// }) - 1
// return ans
// }
Use this to step through a reusable interview workflow for this problem.
Check every element from left to right until we find the target or exhaust the array. Each comparison is O(1), and we may visit all n elements, giving O(n). No extra space needed.
Each comparison eliminates half the remaining search space. After k comparisons, the space is n/2ᵏ. We stop when the space is 1, so k = log₂ n. No extra memory needed — just two pointers (lo, hi).
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Wrong move: Setting `lo = mid` or `hi = mid` can stall and create an infinite loop.
Usually fails on: Two-element ranges never converge.
Fix: Use `lo = mid + 1` or `hi = mid - 1` where appropriate.
Wrong move: An incomplete state merges distinct subproblems and caches incorrect answers.
Usually fails on: Correctness breaks on cases that differ only in hidden state.
Fix: Define state so each unique subproblem maps to one DP cell.