LeetCode 3112 - Minimum Time to Visit Disappearing Nodes

LeetCode Problem 3112

Difficulty: 🟡 Medium
Topics: Array, Graph Theory, Heap (Priority Queue), Shortest Path

Solution

Problem Understanding

The problem describes an undirected weighted graph with n vertices, represented by an array of edges. Each edge connects two vertices and has a weight. A walk is a sequence of vertices and edges that may revisit vertices or edges, and the cost of a walk is defined as the bitwise AND of all edge weights along the walk. Given multiple queries asking for the minimum cost of a walk from si to ti, we must return an array of answers, where each element represents the smallest possible cost for the corresponding query, or -1 if no walk exists.

Key points to note include:

• Multiple edges between the same pair of vertices are possible.
• Walks may revisit edges or vertices, which allows traversing higher-weight edges multiple times to reduce the bitwise AND.
• The constraints (n up to 10^5, edges.length up to 10^5, and edge weights ≤ 10^5) indicate that brute-force enumeration of all walks is infeasible. Efficient graph traversal with bit-level optimization is required.

Important edge cases are queries between disconnected nodes, graphs with zero-weight edges, and queries where the minimal bitwise AND requires revisiting nodes.

Approaches

The brute-force approach would be to enumerate all walks from si to ti for each query and compute the bitwise AND of edge weights along each walk. This guarantees correctness because it considers every possible path, but it is completely impractical due to the exponential number of possible walks and the high number of queries.

The optimal approach relies on the observation that the bitwise AND operation is monotonic under masking. For any two vertices u and v, if there exists a walk with cost c, then for each bit b that is not set in c, there is a way to avoid edges that would prevent that bit from being cleared. Therefore, we can apply bitmask-based BFS: we start from the highest bit and check connectivity using edges that have this bit set, iteratively considering lower bits. Alternatively, we can use a bitwise union-find approach for each bit, connecting nodes if the edge weight contains the bit, which allows fast queries for all pairs.

The key insight is that the minimum cost corresponds to the bitwise AND of a path constructed by repeatedly adding edges that do not eliminate bits unnecessarily, and we can efficiently find this by considering edges in terms of bit masks and connectivity.

Algorithm Walkthrough

1. Initialize a result array answer of length equal to the number of queries, filled with -1.
2. For each bit from 16 down to 0 (since max weight ≤ 10^5 fits in 17 bits), create a Union-Find data structure of size n.
3. Iterate over all edges and include an edge in the union-find only if the current bit is set in its weight.
4. For each query, if the two vertices si and ti are connected in the union-find structure, record the bit as part of the result mask for that query.
5. After processing all bits, each query will have accumulated the minimum possible AND cost as the combination of bits for which the nodes remained connected.
6. Return the answer array.

This algorithm works because each bit in the final AND can only remain set if a path exists using edges with that bit set. By checking connectivity per bit, we construct the minimum AND path without enumerating all walks.

Python Solution

from typing import List

class UnionFind:
    def __init__(self, n: int):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x: int) -> int:
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x: int, y: int) -> None:
        px, py = self.find(x), self.find(y)
        if px == py:
            return
        if self.rank[px] < self.rank[py]:
            self.parent[px] = py
        else:
            self.parent[py] = px
            if self.rank[px] == self.rank[py]:
                self.rank[px] += 1

class Solution:
    def minimumCost(self, n: int, edges: List[List[int]], query: List[List[int]]) -> List[int]:
        Q = len(query)
        answer = [0] * Q
        # Process bit by bit from highest to lowest
        for bit in range(16, -1, -1):
            uf = UnionFind(n)
            mask = 1 << bit
            for u, v, w in edges:
                if w & mask:
                    uf.union(u, v)
            for i in range(Q):
                s, t = query[i]
                if uf.find(s) == uf.find(t):
                    answer[i] |= mask
        # Replace 0 with -1 if no path exists
        for i in range(Q):
            if answer[i] == 0:
                # check if a path exists at all
                uf_all = UnionFind(n)
                for u, v, w in edges:
                    uf_all.union(u, v)
                if uf_all.find(query[i][0]) != uf_all.find(query[i][1]):
                    answer[i] = -1
        return answer

This Python implementation constructs the union-find structure per bit. For each query, it accumulates bits that can be preserved along a connected path. The final step ensures that queries with truly disconnected nodes are set to -1.

Go Solution

package main

type UnionFind struct {
	parent []int
	rank   []int
}

func NewUnionFind(n int) *UnionFind {
	uf := &UnionFind{
		parent: make([]int, n),
		rank:   make([]int, n),
	}
	for i := 0; i < n; i++ {
		uf.parent[i] = i
	}
	return uf
}

func (uf *UnionFind) Find(x int) int {
	if uf.parent[x] != x {
		uf.parent[x] = uf.Find(uf.parent[x])
	}
	return uf.parent[x]
}

func (uf *UnionFind) Union(x, y int) {
	px, py := uf.Find(x), uf.Find(y)
	if px == py {
		return
	}
	if uf.rank[px] < uf.rank[py] {
		uf.parent[px] = py
	} else {
		uf.parent[py] = px
		if uf.rank[px] == uf.rank[py] {
			uf.rank[px]++
		}
	}
}

func minimumCost(n int, edges [][]int, query [][]int) []int {
	Q := len(query)
	answer := make([]int, Q)

	for bit := 16; bit >= 0; bit-- {
		uf := NewUnionFind(n)
		mask := 1 << bit
		for _, e := range edges {
			u, v, w := e[0], e[1], e[2]
			if w&mask != 0 {
				uf.Union(u, v)
			}
		}
		for i := 0; i < Q; i++ {
			s, t := query[i][0], query[i][1]
			if uf.Find(s) == uf.Find(t) {
				answer[i] |= mask
			}
		}
	}
	// Handle disconnected nodes
	ufAll := NewUnionFind(n)
	for _, e := range edges {
		ufAll.Union(e[0], e[1])
	}
	for i := 0; i < Q; i++ {
		if answer[i] == 0 && ufAll.Find(query[i][0]) != ufAll.Find(query[i][1]) {
			answer[i] = -1
		}
	}
	return answer
}

The Go implementation mirrors the Python logic, with attention to slices, struct-based union-find, and explicit initialization of parent arrays.

Worked Examples

Example 1: n = 5, edges = [[0,1,7],[1,3,7],[1,2,1]], query = [[0,3],[3,4]]

1. Bit 2 (mask 4): edges [0,1,7] and [1,3,7] are connected. Union-find shows 0 and 3 connected. answer[0] |= 4
2. Bit 1 (mask 2): all edges connected, still path exists. answer[0] |= 2 → 6
3. Bit 0 (mask 1): [1,2,1] included. 0 and 3 connected via 0->1->2->1->3. answer[0] |= 1 → 7 & path yields minimal AND 1
4. For query [3,4], nodes are disconnected, so answer[1] = -1.

Complexity Analysis

| Measure | Complexity | Explanation |

|---|