Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Checking Existence of Edge Length Limited Paths II

Problem (restated)

Design DistanceLimitedPathsExist(n, edgeList) with query(p, q, limit): true iff there is a path p → q whose maximum edge is strictly less than limit. Queries are online.

Intuition

The min-max bottleneck between two vertices lives on the unique MST path. Kruskal builds that tree; binary lifting stores parent[k][v] and maxEdge[k][v] for 2^k jumps. A query is “max on path < limit”. Disconnected → false.

Approaches

MST + binary lifting

Unverified

Time O((n+E) log n) build, O(log n) querySpace O(n log n)

Idea. Sort edges, Kruskal a forest. DFS (or stack) each component to set depth and up[0]. Double: up[k][v] = up[k-1][up[k-1][v]], mx takes the max of the two hops. Query: lift the deeper node, then lift both until parents match, tracking max.

Walkthrough. n=3, edges 0-1:2, 1-2:4, 2-0:8. Query (0,1,2) → max=2 not < 2 → false. (0,2,5) → path 0-1-2 max 4 < 5 → true.

Trade-offs. LC 1697 is the offline twin (sort queries with edges). Here queries interleave so you need an online max-on-path structure, not a growing UF.

Solution

export class DistanceLimitedPathsExist {
  private up: number[][];
  private mx: number[][];
  private depth: number[];
  private LOG: number;
  private comp: number[];

  constructor(n: number, edgeList: number[][]) {
    const edges = edgeList.map((e) => [e[0]!, e[1]!, e[2]!]).sort((a, b) => a[2]! - b[2]!);
    const parent = Array.from({ length: n }, (_, i) => i);
    const find = (x: number): number => (parent[x] === x ? x : (parent[x] = find(parent[x]!)));
    const adj: [number, number][][] = Array.from({ length: n }, () => []);
    for (const e of edges) {
      const a = find(e[0]!), b = find(e[1]!);
      if (a === b) continue;
      parent[a] = b;
      adj[e[0]!]!.push([e[1]!, e[2]!]);
      adj[e[1]!]!.push([e[0]!, e[2]!]);
    }
    this.comp = Array.from({ length: n }, (_, i) => find(i));

    this.LOG = 1;
    while ((1 << this.LOG) < n) this.LOG++;
    this.up = Array.from({ length: this.LOG }, () => new Array<number>(n).fill(0));
    this.mx = Array.from({ length: this.LOG }, () => new Array<number>(n).fill(0));
    this.depth = new Array<number>(n).fill(-1);

    for (let s = 0; s < n; s++) {
      if (this.depth[s] !== -1) continue;
      this.depth[s] = 0;
      this.up[0]![s] = s;
      const stack = [s];
      while (stack.length) {
        const u = stack.pop()!;
        for (const [v, w] of adj[u]!) {
          if (v === this.up[0]![u] || this.depth[v] !== -1) continue;
          this.depth[v] = this.depth[u]! + 1;
          this.up[0]![v] = u;
          this.mx[0]![v] = w;
          stack.push(v);
        }
      }
    }

    for (let k = 1; k < this.LOG; k++) {
      for (let v = 0; v < n; v++) {
        const mid = this.up[k - 1]![v]!;
        this.up[k]![v] = this.up[k - 1]![mid]!;
        this.mx[k]![v] = Math.max(this.mx[k - 1]![v]!, this.mx[k - 1]![mid]!);
      }
    }
  }

  query(a: number, b: number, limit: number): boolean {
    if (this.comp[a] !== this.comp[b]) return false;
    return this.maxOnPath(a, b) < limit;
  }

  private maxOnPath(a: number, b: number): number {
    if (this.depth[a]! < this.depth[b]!) {
      const t = a; a = b; b = t;
    }
    let ans = 0;
    const diff = this.depth[a]! - this.depth[b]!;
    for (let k = this.LOG - 1; k >= 0; k--) {
      if ((diff >> k) & 1) {
        ans = Math.max(ans, this.mx[k]![a]!);
        a = this.up[k]![a]!;
      }
    }
    if (a === b) return ans;
    for (let k = this.LOG - 1; k >= 0; k--) {
      if (this.up[k]![a] !== this.up[k]![b]) {
        ans = Math.max(ans, this.mx[k]![a]!, this.mx[k]![b]!);
        a = this.up[k]![a]!;
        b = this.up[k]![b]!;
      }
    }
    return Math.max(ans, this.mx[0]![a]!, this.mx[0]![b]!);
  }
}

export class DistanceLimitedPathsExist {
  private up: number[][];
  private mx: number[][];
  private depth: number[];
  private LOG: number;
  private comp: number[];

  constructor(n: number, edgeList: number[][]) {
    const edges = edgeList.map((e) => [e[0]!, e[1]!, e[2]!]).sort((a, b) => a[2]! - b[2]!);
    const parent = Array.from({ length: n }, (_, i) => i);
    const find = (x: number): number => (parent[x] === x ? x : (parent[x] = find(parent[x]!)));
    const adj: [number, number][][] = Array.from({ length: n }, () => []);
    for (const e of edges) {
      const a = find(e[0]!), b = find(e[1]!);
      if (a === b) continue;
      parent[a] = b;
      adj[e[0]!]!.push([e[1]!, e[2]!]);
      adj[e[1]!]!.push([e[0]!, e[2]!]);
    }
    this.comp = Array.from({ length: n }, (_, i) => find(i));

    this.LOG = 1;
    while ((1 << this.LOG) < n) this.LOG++;
    this.up = Array.from({ length: this.LOG }, () => new Array<number>(n).fill(0));
    this.mx = Array.from({ length: this.LOG }, () => new Array<number>(n).fill(0));
    this.depth = new Array<number>(n).fill(-1);

    for (let s = 0; s < n; s++) {
      if (this.depth[s] !== -1) continue;
      this.depth[s] = 0;
      this.up[0]![s] = s;
      const stack = [s];
      while (stack.length) {
        const u = stack.pop()!;
        for (const [v, w] of adj[u]!) {
          if (v === this.up[0]![u] || this.depth[v] !== -1) continue;
          this.depth[v] = this.depth[u]! + 1;
          this.up[0]![v] = u;
          this.mx[0]![v] = w;
          stack.push(v);
        }
      }
    }

    for (let k = 1; k < this.LOG; k++) {
      for (let v = 0; v < n; v++) {
        const mid = this.up[k - 1]![v]!;
        this.up[k]![v] = this.up[k - 1]![mid]!;
        this.mx[k]![v] = Math.max(this.mx[k - 1]![v]!, this.mx[k - 1]![mid]!);
      }
    }
  }

  query(a: number, b: number, limit: number): boolean {
    if (this.comp[a] !== this.comp[b]) return false;
    return this.maxOnPath(a, b) < limit;
  }

  private maxOnPath(a: number, b: number): number {
    if (this.depth[a]! < this.depth[b]!) {
      const t = a; a = b; b = t;
    }
    let ans = 0;
    const diff = this.depth[a]! - this.depth[b]!;
    for (let k = this.LOG - 1; k >= 0; k--) {
      if ((diff >> k) & 1) {
        ans = Math.max(ans, this.mx[k]![a]!);
        a = this.up[k]![a]!;
      }
    }
    if (a === b) return ans;
    for (let k = this.LOG - 1; k >= 0; k--) {
      if (this.up[k]![a] !== this.up[k]![b]) {
        ans = Math.max(ans, this.mx[k]![a]!, this.mx[k]![b]!);
        a = this.up[k]![a]!;
        b = this.up[k]![b]!;
      }
    }
    return Math.max(ans, this.mx[0]![a]!, this.mx[0]![b]!);
  }
}

Template connection

Kruskal produces the tree; lifting is the query structure. Same bottleneck theorem as “min edge that connects p and q in Kruskal order.”

Reflection

Kruskal the edges by length, then binary-lift the forest: up[k] and the maximum edge on that jump.
A query lifts both nodes and tracks the maximum edge. The path exists when that maximum is strictly < limit.
The same node is true, because the max on an empty path is 0. Different components never meet. Equal edge lengths do not change that maximum.