Log inSign up
hardGeeksforGeeksNot Started

Offline Queries with DSU

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Advanced DSA
Solve on GeeksforGeeks
Lesson

Problem Statement

Given an undirected graph with n nodes labeled from 0 to n - 1 and an array edges where edges[i] = [u, v, weight], answer an array of offline queries queries where queries[j] = [p, q, limit].

For each query, determine whether there exists a path between node p and node q such that every edge in the path has a weight strictly less than limit. Return a boolean array answer where answer[j] is true if such a path exists, and false otherwise.

Sorting queries offline allows utilizing a Disjoint Set Union (DSU / Union-Find) data structure to incrementally insert valid edges without repeatedly restarting graph traversals.

Example 1 · Example 1:

Input: n = 3, edges = [[0, 1, 2], [1, 2, 4], [2, 0, 8]], queries = [[0, 2, 5], [0, 2, 3]]
Output: [true, false]
Explanation: For query [0, 2, 5], path 0-1-2 uses edges with weights 2 and 4, both < 5. For query [0, 2, 3], only edge (0,1) with weight 2 is < 3, so 0 and 2 are disconnected.

Example 2 · Example 2:

Input: n = 5, edges = [[0, 1, 10], [1, 2, 5], [2, 3, 9], [3, 4, 13]], queries = [[0, 4, 14], [1, 4, 13]]
Output: [true, false]
Explanation: Query [0, 4, 14] can use all edges (max weight 13 < 14). Query [1, 4, 13] cannot use edge (3, 4) since its weight is 13 (not strictly < 13).

Constraints:

  • 2 <= n <= 105
  • 1 <= edges.length <= 105
  • edges[i].length == 3
  • 0 <= u_i, v_i < n, u_i != v_i
  • 1 <= weight_i, limit_j <= 109
  • 1 <= queries.length <= 105
  • queries[j].length == 3
  • 0 <= p_j, q_j < n, p_j != q_j

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the 3 distinct approaches for Offline Queries with DSU.
  • Implement fully runnable solutions in C++, Java, Python, and JavaScript.
  • Analyze algorithmic trade-offs across data structure designs.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Offline Queries with DSU
  • Advanced Data Structures & Algorithmic Paradigm
  • Fast Range Queries or Amortized Dynamic Operations

Algorithmic Decision Tree:

  • BRUTE_FORCE: Viable only when the number of queries is very small (Q <= 50).
  • BETTER: Excellent when queries must be answered online (cannot be sorted ahead of time) and edge updates are absent.
  • OPTIMAL: The industry standard approach when queries are known in advance (offline) and the condition is a monotonically increasing threshold.

Connected Patterns:

Segment TreeFenwick TreeDisjoint Set UnionDesign Data Structures

1. Per-Query Breadth-First Search (BFS)

Intuition

For every query [p, q, limit], construct or filter the graph adjacency list keeping only edges where weight < limit. Then, run standard BFS or DFS starting from node p to see if q is reachable. Because BFS takes O(V + E) time per query, processing Q queries requires O(Q \cdot (V + E)) time, which is too slow for large inputs.

When to apply: Viable only when the number of queries is very small (Q <= 50).

Algorithm

  1. Step 1: Iterate through each query [p, q, limit].
  2. Step 2: Initialize a queue with node p and a visited array of size n.
  3. Step 3: Perform BFS considering only adjacent edges with weight < limit.
  4. Step 4: If node q is reached, mark result for this query as true; otherwise, false upon queue exhaustion.
  5. Step 5: Return the boolean answer array.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <queue>
4
5std::vector<bool> solveBruteForce(int n, const std::vector<std::vector<int>>& edges, const std::vector<std::vector<int>>& queries) {
6 std::vector<std::vector<std::pair<int, int>>> adj(n);
7 for (const auto& e : edges) {
8 adj[e[0]].push_back({e[1], e[2]});
9 adj[e[1]].push_back({e[0], e[2]});
10 }
11
12 std::vector<bool> ans;
13 ans.reserve(queries.size());
14
15 for (const auto& q : queries) {
16 int start = q[0], target = q[1], limit = q[2];
17 std::vector<bool> visited(n, false);
18 std::queue<int> qu;
19
20 qu.push(start);
21 visited[start] = true;
22 bool found = false;
23
24 while (!qu.empty()) {
25 int u = qu.front();
26 qu.pop();
27
28 if (u == target) {
29 found = true;
30 break;
31 }
32
33 for (const auto& edge : adj[u]) {
34 int v = edge.first;
35 int w = edge.second;
36 if (w < limit && !visited[v]) {
37 visited[v] = true;
38 qu.push(v);
39 }
40 }
41 }
42 ans.push_back(found);
43 }
44
45 return ans;
46}
47
48int main() {
49 int n = 3;
50 std::vector<std::vector<int>> edges = {{0, 1, 2}, {1, 2, 4}, {2, 0, 8}};
51 std::vector<std::vector<int>> queries = {{0, 2, 5}, {0, 2, 3}};
52 auto res = solveBruteForce(n, edges, queries);
53 for (bool b : res) std::cout << (b ? "true " : "false ");
54 std::cout << std::endl;
55 return 0;
56}

Time & Space Complexity

  • Time complexity: O(Q * (V + E)) where Q is queries, V is vertices, E is edges
  • Space complexity: O(V + E) for the adjacency list and visited set

2. Minimum Spanning Forest + LCA Binary Lifting

Intuition

Any path between two nodes that minimizes the maximum edge weight lies on the graph's Minimum Spanning Tree (MST) or Forest. 1. Run Kruskal's algorithm to construct an MST with edge weights. 2. If two nodes are in different connected components, they can never be reachable. 3. If they are in the same component, precompute LCA binary lifting tables storing both the 2k-th ancestor and the maximum edge weight on the path to that ancestor. 4. For each query, compute the maximum edge weight on the tree path between p and q in O(log V) time. If this max weight is < limit, answer is true, otherwise false.

When to apply: Excellent when queries must be answered online (cannot be sorted ahead of time) and edge updates are absent.

Algorithm

  1. Step 1: Sort all edges by weight and construct an MST using Kruskal's algorithm.
  2. Step 2: Root each tree component and compute binary lifting table (up[u][k], maxW[u][k]).
  3. Step 3: For each online query [p, q, limit], if p and q belong to different trees, output false.
  4. Step 4: Otherwise, compute the bottleneck max edge on path(p, q) via LCA in O(log V) time.
  5. Step 5: Return true if max edge < limit, else false.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5struct Edge {
6 int u, v, w;
7};
8
9struct DSU {
10 std::vector<int> parent;
11 DSU(int n) : parent(n) {
12 for (int i = 0; i < n; i++) parent[i] = i;
13 }
14 int find(int i) {
15 return parent[i] == i ? i : parent[i] = find(parent[i]);
16 }
17 bool unite(int i, int j) {
18 int rootI = find(i), rootJ = find(j);
19 if (rootI != rootJ) {
20 parent[rootI] = rootJ;
21 return true;
22 }
23 return false;
24 }
25};
26
27void dfs(int u, int p, int w, int d, const std::vector<std::vector<std::pair<int, int>>>& adj,
28 std::vector<std::vector<int>>& up, std::vector<std::vector<int>>& maxW,
29 std::vector<int>& depth, std::vector<int>& comp, int compId) {
30 comp[u] = compId;
31 depth[u] = d;
32 up[u][0] = p;
33 maxW[u][0] = w;
34 for (int i = 1; i < 20; ++i) {
35 up[u][i] = up[up[u][i - 1]][i - 1];
36 maxW[u][i] = std::max(maxW[u][i - 1], maxW[up[u][i - 1]][i - 1]);
37 }
38 for (const auto& edge : adj[u]) {
39 int v = edge.first;
40 if (v != p) {
41 dfs(v, u, edge.second, d + 1, adj, up, maxW, depth, comp, compId);
42 }
43 }
44}
45
46int queryMaxEdge(int u, int v, const std::vector<std::vector<int>>& up,
47 const std::vector<std::vector<int>>& maxW, const std::vector<int>& depth) {
48 int maxEdge = 0;
49 if (depth[u] < depth[v]) std::swap(u, v);
50 for (int i = 19; i >= 0; --i) {
51 if (depth[u] - (1 << i) >= depth[v]) {
52 maxEdge = std::max(maxEdge, maxW[u][i]);
53 u = up[u][i];
54 }
55 }
56 if (u == v) return maxEdge;
57 for (int i = 19; i >= 0; --i) {
58 if (up[u][i] != up[v][i]) {
59 maxEdge = std::max({maxEdge, maxW[u][i], maxW[v][i]});
60 u = up[u][i];
61 v = up[v][i];
62 }
63 }
64 return std::max({maxEdge, maxW[u][0], maxW[v][0]});
65}
66
67std::vector<bool> solveLCA(int n, std::vector<std::vector<int>>& edges, const std::vector<std::vector<int>>& queries) {
68 std::vector<Edge> edgeList;
69 for (const auto& e : edges) edgeList.push_back({e[0], e[1], e[2]});
70 std::sort(edgeList.begin(), edgeList.end(), [](const Edge& a, const Edge& b) { return a.w < b.w; });
71
72 DSU dsu(n);
73 std::vector<std::vector<std::pair<int, int>>> mst(n);
74 for (const auto& e : edgeList) {
75 if (dsu.unite(e.u, e.v)) {
76 mst[e.u].push_back({e.v, e.w});
77 mst[e.v].push_back({e.u, e.w});
78 }
79 }
80
81 std::vector<std::vector<int>> up(n, std::vector<int>(20, 0));
82 std::vector<std::vector<int>> maxW(n, std::vector<int>(20, 0));
83 std::vector<int> depth(n, 0), comp(n, -1);
84
85 for (int i = 0; i < n; ++i) {
86 if (comp[i] == -1) {
87 dfs(i, i, 0, 0, mst, up, maxW, depth, comp, i);
88 }
89 }
90
91 std::vector<bool> ans;
92 ans.reserve(queries.size());
93 for (const auto& q : queries) {
94 int u = q[0], v = q[1], limit = q[2];
95 if (comp[u] != comp[v]) {
96 ans.push_back(false);
97 } else {
98 ans.push_back(queryMaxEdge(u, v, up, maxW, depth) < limit);
99 }
100 }
101 return ans;
102}
103
104int main() {
105 int n = 3;
106 std::vector<std::vector<int>> edges = {{0, 1, 2}, {1, 2, 4}, {2, 0, 8}};
107 std::vector<std::vector<int>> queries = {{0, 2, 5}, {0, 2, 3}};
108 auto res = solveLCA(n, edges, queries);
109 for (bool b : res) std::cout << (b ? "true " : "false ");
110 std::cout << std::endl;
111 return 0;
112}

Time & Space Complexity

  • Time complexity: O(E log E + V log V + Q log V) time
  • Space complexity: O(V log V + E) auxiliary space for binary lifting tables

3. Offline Queries + Sorted Edges with DSU

Intuition

Because we can answer queries in any order, sorting edges and queries by weight/limit transforms the problem: 1. Sort edges in ascending order of weight: e_1, e_2, \dots. 2. Attach original index to queries and sort queries by limit in ascending order. 3. Maintain a single DSU instance over all N vertices. 4. Maintain an edge pointer edgeIdx. For each query [p, q, limit]: - While edges[edgeIdx].weight < limit, union the endpoints into the DSU and advance edgeIdx. - Now, the DSU contains exactly all edges available under the query limit. - Simply test if find(p) == find(q) and store the boolean answer at the query's original index. 5. Because every edge is processed at most once, total time is dominated by sorting, achieving optimal O(E log E + Q log Q).

When to apply: The industry standard approach when queries are known in advance (offline) and the condition is a monotonically increasing threshold.

Algorithm

  1. Step 1: Sort edges in ascending order of edge weights.
  2. Step 2: Create indexed queries [p, q, limit, originalIndex] and sort them ascending by limit.
  3. Step 3: Initialize a DSU with path compression and rank of size n.
  4. Step 4: Maintain edge pointer edgeIdx = 0 and loop over sorted queries.
  5. Step 5: While edgeIdx < edges.length and edges[edgeIdx].weight < limit, union endpoints and advance edgeIdx.
  6. Step 6: Set ans[originalIndex] = (find(p) == find(q)).
  7. Step 7: Return the final boolean answers array.

Interactive trace

2 of 2 questions left today
Step 1 / 2
Trace timeline50% explored
Current operationSTEP 1 OF 2
Sorted queries by limit: Query 1 [0, 2, limit=3] is processed first, then Query 0 [0, 2, limit=5]
Visual state
Values and pointers at this exact step
pointers
S
0
1
2
0
1
↑ edgeIdx
2
Check / comparison
Edges with weight < 3: edge (0, 1, weight=2)
Decision / next transition
Union nodes 0 and 1. Check find(0) == find(2) -> False. ans[1] = false.
Why this step matters

Sorted queries by limit: Query 1 [0, 2, limit=3] is processed first, then Query 0 [0, 2, limit=5].

Step 1 / 2
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <numeric>
4#include <algorithm>
5
6struct DSU {
7 std::vector<int> parent, rank;
8 DSU(int n) : parent(n), rank(n, 0) {
9 std::iota(parent.begin(), parent.end(), 0);
10 }
11 int find(int i) {
12 return parent[i] == i ? i : parent[i] = find(parent[i]);
13 }
14 void unite(int i, int j) {
15 int rootI = find(i), rootJ = find(j);
16 if (rootI != rootJ) {
17 if (rank[rootI] < rank[rootJ]) std::swap(rootI, rootJ);
18 parent[rootJ] = rootI;
19 if (rank[rootI] == rank[rootJ]) rank[rootI]++;
20 }
21 }
22 bool connected(int i, int j) {
23 return find(i) == find(j);
24 }
25};
26
27std::vector<bool> distanceLimitedPathsExist(int n, std::vector<std::vector<int>>& edges, std::vector<std::vector<int>>& queries) {
28 std::sort(edges.begin(), edges.end(), [](const auto& a, const auto& b) {
29 return a[2] < b[2];
30 });
31
32 int qSize = queries.size();
33 std::vector<int> qIdx(qSize);
34 std::iota(qIdx.begin(), qIdx.end(), 0);
35 std::sort(qIdx.begin(), qIdx.end(), [&](int a, int b) {
36 return queries[a][2] < queries[b][2];
37 });
38
39 DSU dsu(n);
40 std::vector<bool> ans(qSize);
41 int edgeIdx = 0;
42 int edgeCount = edges.size();
43
44 for (int idx : qIdx) {
45 int u = queries[idx][0];
46 int v = queries[idx][1];
47 int limit = queries[idx][2];
48
49 while (edgeIdx < edgeCount && edges[edgeIdx][2] < limit) {
50 dsu.unite(edges[edgeIdx][0], edges[edgeIdx][1]);
51 edgeIdx++;
52 }
53
54 ans[idx] = dsu.connected(u, v);
55 }
56
57 return ans;
58}
59
60int main() {
61 int n = 3;
62 std::vector<std::vector<int>> edges = {{0, 1, 2}, {1, 2, 4}, {2, 0, 8}};
63 std::vector<std::vector<int>> queries = {{0, 2, 5}, {0, 2, 3}};
64 auto res = distanceLimitedPathsExist(n, edges, queries);
65 for (bool b : res) std::cout << (b ? "true " : "false ");
66 std::cout << std::endl;
67 return 0;
68}

Time & Space Complexity

  • Time complexity: O(E log E + Q log Q + (E + Q) * α(V))
  • Space complexity: O(V + Q) auxiliary space for DSU parent/rank and answer array

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Per-Query Breadth-First Search (BFS)O(Q * (V + E)) where Q is queries, V is vertices, E is edgesO(V + E) for the adjacency list and visited setFor each query, perform a BFS traversal traversing only edges with weight strictly less than limit.O(Q * (V + E)) where Q is queries, V is vertices, E is edges
2.Minimum Spanning Forest + LCA Binary LiftingO(E log E + V log V + Q log V) timeO(V log V + E) auxiliary space for binary lifting tablesBuild a Minimum Spanning Tree (MST) using Kruskal's algorithm, then find the bottleneck maximum edge weight on the path between p and q using LCA binary lifting.O(E log E + V log V + Q log V) time
3.Offline Queries + Sorted Edges with DSUOptimalO(E log E + Q log Q + (E + Q) * α(V))O(V + Q) auxiliary space for DSU parent/rank and answer arraySort edges by weight and queries by limit ascending. Add edges with weight < limit incrementally into a DSU, answering queries directly.O(E log E + Q log Q + (E + Q) * α(V))

Common Pitfalls & Crucial Edge Cases

Path compression during DSU with rollback

Path compression destroys original tree depths, making exact pointer rollback impossible. In rollback DSU, use union by size/rank only.

Forgetting to track original query indices

Sorting queries changes their order; results must be stored at query.originalIndex.

Re-initializing DSU for every query

Rebuilding the DSU per query takes O(Q * E), which times out. Monotonic pointer sweep takes O(E log E + Q log Q).

Crucial Edge Cases to Validate:

  • Queries with threshold smaller than all edge weights — No edges are activated; nodes are only connected to themselves.
  • Queries with threshold larger than all edge weights — Graph is fully connected; all components merged.
  • Disconnected graph components — Queries between separate components return false.
  • Query between a node and itself — A node is always connected to itself.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Explain the monotonic sweep paradigm: 'Instead of answering queries as they arrive, we sort queries and data by the same monotonic dimension.'
  2. Discuss why standard DSU is faster than Dijkstra or BFS for batch reachability.
  3. Mention classic interview problems using this pattern: 'Checking Existence of Edge Length Limited Paths' and 'Make Lexicographically Smallest Array'.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the key advantage of processing queries offline when combined with Disjoint Set Union (DSU)?

2.What is the time complexity of DSU with path compression and union by rank?

3.If queries require edge deletions or non-monotonic thresholds, what technique is required?

Back to DSA Sheet