Daily DSA: Consistent Relative Positions (Medium)
Problem Statement
You are given an integer n, representing n landmarks indexed from 0 to n - 1 along a straight East-West road.
You are also given a 2D integer array relations, where relations[i] = [u, v, d]. Each entry represents an observation claiming that landmark v is located exactly d units to the East of landmark u (i.e., pos(v) - pos(u) == d). Note that d can be positive, negative, or zero.
We process the relations sequentially in the given order:
- If an observation does not contradict any previously accepted observations, it is considered valid and is accepted.
- If an observation contradicts any previously accepted observations, it is considered invalid and is discarded.
Return a boolean array ans of length equal to relations.length, where ans[i] is true if relations[i] is accepted, or false if it is rejected.
Examples
Example 1:
Input: n = 4, relations = [[0, 1, 10], [1, 2, 5], [0, 2, 15], [0, 2, 20]]
Output: [true, true, true, false]
Explanation:
- [0, 1, 10]: Sets pos(1) - pos(0) = 10. Valid.
- [1, 2, 5]: Sets pos(2) - pos(1) = 5. Now pos(2) - pos(0) = 15. Valid.
- [0, 2, 15]: Observation claims pos(2) - pos(0) = 15, which matches our existing deductions. Valid.
- [0, 2, 20]: Observation claims pos(2) - pos(0) = 20, contradicting pos(2) - pos(0) = 15. Invalid.
Example 2:
Input: n = 3, relations = [[0, 1, 4], [0, 0, 5], [1, 0, -4]]
Output: [true, false, true]
Explanation:
- [0, 1, 4]: Sets pos(1) - pos(0) = 4. Valid.
- [0, 0, 5]: Claims pos(0) - pos(0) = 5 != 0. Invalid.
- [1, 0, -4]: Claims pos(0) - pos(1) = -4, which is equivalent to pos(1) - pos(0) = 4. Valid.
Example 3:
Input: n = 4, relations = [[0, 1, 3], [2, 3, 4], [1, 2, -2], [0, 3, 5]]
Output: [true, true, true, true]
Explanation:
- [0, 1, 3]: pos(1) - pos(0) = 3.
- [2, 3, 4]: pos(3) - pos(2) = 4.
- [1, 2, -2]: Connects the two components. Now pos(3) - pos(0) = (pos(1) - pos(0)) + (pos(2) - pos(1)) + (pos(3) - pos(2)) = 3 + (-2) + 4 = 5.
- [0, 3, 5]: Matches pos(3) - pos(0) = 5. Valid.
Constraints
1 <= n <= 10^51 <= relations.length <= 10^5relations[i].length == 30 <= u, v < n-10^9 <= d <= 10^9
Approach
This problem can be modeled as maintaining relative offsets in connected components, which is best solved using a Disjoint Set Union (DSU) with Potential (Weighted DSU).
Key Idea
In a standard DSU, each element points to a parent, eventually leading to a representative root. In a weighted DSU, we also maintain a dist[x] array representing the relative displacement from parent[x] to x: pos(x) - pos(parent[x]) = dist[x].
-
Path Compression with Offset Accumulation: When querying
find(x), we recursively find the root ofparent[x]. As the recursion unwinds, we updatedist[x] += dist[parent[x]]and redirectparent[x] = root. After path compression,dist[x]directly representspos(x) - pos(root). -
Evaluating an Observation
(u, v, d):- Find the roots of
uandv:rootU = find(u)androotV = find(v). - Case 1:
rootU == rootVBoth nodes already belong to the same component, so their relative position is fixed. The known displacement ispos(v) - pos(u) = dist[v] - dist[u].- If
dist[v] - dist[u] == d, the observation is consistent and accepted (true). - Otherwise, it is a contradiction and rejected (
false).
- If
- Case 2:
rootU != rootVThe two components are not yet connected, so no contradiction is possible. The relation is accepted (true). We merge the components by settingparent[rootV] = rootU. To finddist[rootV](displacement ofrootVrelative torootU), we use the relation: \(pos(v) - pos(u) = d\) \((pos(rootV) + dist[v]) - (pos(rootU) + dist[u]) = d\) \(pos(rootV) - pos(rootU) = d + dist[u] - dist[v]\) Thus, we assigndist[rootV] = d + dist[u] - dist[v].
- Find the roots of
Precision Note
Distances can accumulate across multiple additions, potentially exceeding standard 32-bit integers. We use 64-bit integers (long long in C++) for all distance offsets.
C++ Implementation
#include <vector>
using namespace std;
class Solution {
struct WeightedDSU {
vector<int> parent;
vector<long long> dist; // dist[i] = pos(i) - pos(parent[i])
WeightedDSU(int n) {
parent.resize(n);
dist.assign(n, 0LL);
for (int i = 0; i < n; ++i) {
parent[i] = i;
}
}
int find(int i) {
if (parent[i] == i) {
return i;
}
int originalParent = parent[i];
parent[i] = find(parent[i]);
dist[i] += dist[originalParent];
return parent[i];
}
bool addRelation(int u, int v, long long d) {
int rootU = find(u);
int rootV = find(v);
if (rootU == rootV) {
// Both are in the same component, check consistency
return (dist[v] - dist[u]) == d;
}
// Merge rootV into rootU
parent[rootV] = rootU;
dist[rootV] = d + dist[u] - dist[v];
return true;
}
};
public:
vector<bool> validateRelations(int n, vector<vector<int>>& relations) {
WeightedDSU dsu(n);
int m = relations.size();
vector<bool> ans(m);
for (int i = 0; i < m; ++i) {
int u = relations[i][0];
int v = relations[i][1];
long long d = relations[i][2];
ans[i] = dsu.addRelation(u, v, d);
}
return ans;
}
};
Complexity Analysis
- Time Complexity: $\mathcal{O}((N + M) \log N)$ or $\mathcal{O}((N + M) \alpha(N))$ nearly linear time, where $N$ is the number of landmarks and $M$ is the number of relations. Path compression keeps tree depth minimal.
- Space Complexity: $\mathcal{O}(N)$ auxiliary space for storing the
parentanddistarrays in the DSU, plus $\mathcal{O}(M)$ for the output array.