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 an undirected weighted graph of n nodes numbered from 0 to n - 1. The graph consists of m edges represented by a 2D array edges, where edges[i] = [ai, bi, wi] indicates that there is an edge between nodes ai and bi with weight wi.
Consider all the shortest paths from node 0 to node n - 1 in the graph. You need to find a boolean array answer where answer[i] is true if the edge edges[i] is part of at least one shortest path. Otherwise, answer[i] is false.
Return the array answer.
Note that the graph may not be connected.
Example 1:
Input: n = 6, edges = [[0,1,4],[0,2,1],[1,3,2],[1,4,3],[1,5,1],[2,3,1],[3,5,3],[4,5,2]]
Output: [true,true,true,false,true,true,true,false]
Explanation:
The following are all the shortest paths between nodes 0 and 5:
0 -> 1 -> 5: The sum of weights is 4 + 1 = 5.0 -> 2 -> 3 -> 5: The sum of weights is 1 + 1 + 3 = 5.0 -> 2 -> 3 -> 1 -> 5: The sum of weights is 1 + 1 + 2 + 1 = 5.Example 2:
Input: n = 4, edges = [[2,0,1],[0,1,1],[0,3,4],[3,2,2]]
Output: [true,false,false,true]
Explanation:
There is one shortest path between nodes 0 and 3, which is the path 0 -> 2 -> 3 with the sum of weights 1 + 2 = 3.
Constraints:
2 <= n <= 5 * 104m == edges.length1 <= m <= min(5 * 104, n * (n - 1) / 2)0 <= ai, bi < nai != bi1 <= wi <= 105Problem summary: You are given an undirected weighted graph of n nodes numbered from 0 to n - 1. The graph consists of m edges represented by a 2D array edges, where edges[i] = [ai, bi, wi] indicates that there is an edge between nodes ai and bi with weight wi. Consider all the shortest paths from node 0 to node n - 1 in the graph. You need to find a boolean array answer where answer[i] is true if the edge edges[i] is part of at least one shortest path. Otherwise, answer[i] is false. Return the array answer. Note that the graph may not be connected.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: General problem-solving
6 [[0,1,4],[0,2,1],[1,3,2],[1,4,3],[1,5,1],[2,3,1],[3,5,3],[4,5,2]]
4 [[2,0,1],[0,1,1],[0,3,4],[3,2,2]]
Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #3123: Find Edges in Shortest Paths
class Solution {
public boolean[] findAnswer(int n, int[][] edges) {
List<int[]>[] g = new List[n];
Arrays.setAll(g, k -> new ArrayList<>());
int m = edges.length;
for (int i = 0; i < m; ++i) {
int a = edges[i][0], b = edges[i][1], w = edges[i][2];
g[a].add(new int[] {b, w, i});
g[b].add(new int[] {a, w, i});
}
int[] dist = new int[n];
final int inf = 1 << 30;
Arrays.fill(dist, inf);
dist[0] = 0;
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
pq.offer(new int[] {0, 0});
while (!pq.isEmpty()) {
var p = pq.poll();
int da = p[0], a = p[1];
if (da > dist[a]) {
continue;
}
for (var e : g[a]) {
int b = e[0], w = e[1];
if (dist[b] > dist[a] + w) {
dist[b] = dist[a] + w;
pq.offer(new int[] {dist[b], b});
}
}
}
boolean[] ans = new boolean[m];
if (dist[n - 1] == inf) {
return ans;
}
Deque<Integer> q = new ArrayDeque<>();
q.offer(n - 1);
while (!q.isEmpty()) {
int a = q.poll();
for (var e : g[a]) {
int b = e[0], w = e[1], i = e[2];
if (dist[a] == dist[b] + w) {
ans[i] = true;
q.offer(b);
}
}
}
return ans;
}
}
// Accepted solution for LeetCode #3123: Find Edges in Shortest Paths
func findAnswer(n int, edges [][]int) []bool {
g := make([][][3]int, n)
for i, e := range edges {
a, b, w := e[0], e[1], e[2]
g[a] = append(g[a], [3]int{b, w, i})
g[b] = append(g[b], [3]int{a, w, i})
}
dist := make([]int, n)
const inf int = 1 << 30
for i := range dist {
dist[i] = inf
}
dist[0] = 0
pq := hp{{0, 0}}
for len(pq) > 0 {
p := heap.Pop(&pq).(pair)
da, a := p.dis, p.u
if da > dist[a] {
continue
}
for _, e := range g[a] {
b, w := e[0], e[1]
if dist[b] > dist[a]+w {
dist[b] = dist[a] + w
heap.Push(&pq, pair{dist[b], b})
}
}
}
ans := make([]bool, len(edges))
if dist[n-1] == inf {
return ans
}
q := []int{n - 1}
for len(q) > 0 {
a := q[0]
q = q[1:]
for _, e := range g[a] {
b, w, i := e[0], e[1], e[2]
if dist[a] == dist[b]+w {
ans[i] = true
q = append(q, b)
}
}
}
return ans
}
type pair struct{ dis, u int }
type hp []pair
func (h hp) Len() int { return len(h) }
func (h hp) Less(i, j int) bool { return h[i].dis < h[j].dis }
func (h hp) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v any) { *h = append(*h, v.(pair)) }
func (h *hp) Pop() any { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }
# Accepted solution for LeetCode #3123: Find Edges in Shortest Paths
class Solution:
def findAnswer(self, n: int, edges: List[List[int]]) -> List[bool]:
g = defaultdict(list)
for i, (a, b, w) in enumerate(edges):
g[a].append((b, w, i))
g[b].append((a, w, i))
dist = [inf] * n
dist[0] = 0
q = [(0, 0)]
while q:
da, a = heappop(q)
if da > dist[a]:
continue
for b, w, _ in g[a]:
if dist[b] > dist[a] + w:
dist[b] = dist[a] + w
heappush(q, (dist[b], b))
m = len(edges)
ans = [False] * m
if dist[n - 1] == inf:
return ans
q = deque([n - 1])
while q:
a = q.popleft()
for b, w, i in g[a]:
if dist[a] == dist[b] + w:
ans[i] = True
q.append(b)
return ans
// Accepted solution for LeetCode #3123: Find Edges in Shortest Paths
// Rust example auto-generated from java 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 (java):
// // Accepted solution for LeetCode #3123: Find Edges in Shortest Paths
// class Solution {
// public boolean[] findAnswer(int n, int[][] edges) {
// List<int[]>[] g = new List[n];
// Arrays.setAll(g, k -> new ArrayList<>());
// int m = edges.length;
// for (int i = 0; i < m; ++i) {
// int a = edges[i][0], b = edges[i][1], w = edges[i][2];
// g[a].add(new int[] {b, w, i});
// g[b].add(new int[] {a, w, i});
// }
// int[] dist = new int[n];
// final int inf = 1 << 30;
// Arrays.fill(dist, inf);
// dist[0] = 0;
// PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
// pq.offer(new int[] {0, 0});
// while (!pq.isEmpty()) {
// var p = pq.poll();
// int da = p[0], a = p[1];
// if (da > dist[a]) {
// continue;
// }
// for (var e : g[a]) {
// int b = e[0], w = e[1];
// if (dist[b] > dist[a] + w) {
// dist[b] = dist[a] + w;
// pq.offer(new int[] {dist[b], b});
// }
// }
// }
// boolean[] ans = new boolean[m];
// if (dist[n - 1] == inf) {
// return ans;
// }
// Deque<Integer> q = new ArrayDeque<>();
// q.offer(n - 1);
// while (!q.isEmpty()) {
// int a = q.poll();
// for (var e : g[a]) {
// int b = e[0], w = e[1], i = e[2];
// if (dist[a] == dist[b] + w) {
// ans[i] = true;
// q.offer(b);
// }
// }
// }
// return ans;
// }
// }
// Accepted solution for LeetCode #3123: Find Edges in Shortest Paths
// Auto-generated TypeScript example from java.
function exampleSolution(): void {
}
// Reference (java):
// // Accepted solution for LeetCode #3123: Find Edges in Shortest Paths
// class Solution {
// public boolean[] findAnswer(int n, int[][] edges) {
// List<int[]>[] g = new List[n];
// Arrays.setAll(g, k -> new ArrayList<>());
// int m = edges.length;
// for (int i = 0; i < m; ++i) {
// int a = edges[i][0], b = edges[i][1], w = edges[i][2];
// g[a].add(new int[] {b, w, i});
// g[b].add(new int[] {a, w, i});
// }
// int[] dist = new int[n];
// final int inf = 1 << 30;
// Arrays.fill(dist, inf);
// dist[0] = 0;
// PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
// pq.offer(new int[] {0, 0});
// while (!pq.isEmpty()) {
// var p = pq.poll();
// int da = p[0], a = p[1];
// if (da > dist[a]) {
// continue;
// }
// for (var e : g[a]) {
// int b = e[0], w = e[1];
// if (dist[b] > dist[a] + w) {
// dist[b] = dist[a] + w;
// pq.offer(new int[] {dist[b], b});
// }
// }
// }
// boolean[] ans = new boolean[m];
// if (dist[n - 1] == inf) {
// return ans;
// }
// Deque<Integer> q = new ArrayDeque<>();
// q.offer(n - 1);
// while (!q.isEmpty()) {
// int a = q.poll();
// for (var e : g[a]) {
// int b = e[0], w = e[1], i = e[2];
// if (dist[a] == dist[b] + w) {
// ans[i] = true;
// q.offer(b);
// }
// }
// }
// return ans;
// }
// }
Use this to step through a reusable interview workflow for this problem.
Two nested loops check every pair or subarray. The outer loop fixes a starting point, the inner loop extends or searches. For n elements this gives up to n²/2 operations. No extra space, but the quadratic time is prohibitive for large inputs.
Most array problems have an O(n²) brute force (nested loops) and an O(n) optimal (single pass with clever state tracking). The key is identifying what information to maintain as you scan: a running max, a prefix sum, a hash map of seen values, or two pointers.
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.