Checking Existence of Edge Length Limited Paths

HardGraphsunion find

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

An undirected graph has n nodes labeled 0 to n - 1. edgeList[i] = [u_i, v_i, dis_i] is an edge between u_i and v_i with length dis_i. There may be **multiple edges** between the same pair of nodes. Each query queries[j] = [p_j, q_j, limit_j] asks: is there a path from p_j to q_j in which **every edge is strictly shorter** than limit_j? Return a boolean array answer with answer[j] the result of the j-th query, in the original query order.

Examples

Input: n = 4, edgeList = [[0,1,3],[1,2,5],[2,3,2],[0,3,9]], queries = [[0,2,6],[0,3,5],[3,1,6]]
Output: [true,false,true]
Limit 6 allows edges 3, 5, 2, connecting 0-1-2-3. Limit 5 allows only the edges of length 3 and 2, leaving `{0,1}` and `{2,3}` apart.
Input: n = 3, edgeList = [[0,1,4],[0,1,2]], queries = [[0,1,2],[1,2,10]]
Output: [false,false]
Lengths must be strictly less than 2, so neither 0-1 edge qualifies. Node 2 has no edges at all.

Constraints

  • `2 <= n <= 10^5`
  • `1 <= edgeList.length, queries.length <= 10^5`
  • `0 <= u_i, v_i, p_j, q_j <= n - 1`
  • `u_i != v_i`, `p_j != q_j`
  • `1 <= dis_i, limit_j <= 10^9`

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More union find problems