Edge Length Limited Paths - DSU & Sorting Solution 🔍
IntuitionWhen I first saw this problem, I realized it's asking us to check if two nodes are connected using only edges with weights less than a given limit. Thi
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
When I first saw this problem, I realized it's asking us to check if two nodes are connected using only edges with weights less than a given limit. This naturally led me to think about using a Disjoint Set Union (DSU) data structure, which is perfect for keeping track of connected components in a graph.
Think of it like forming groups of friends - if A is friends with B, and B is friends with C, then A, B, and C are all in the same friend group. Here, we're doing the same with nodes, but only connecting them if the edge weight is less than our limit.

---


# Approach
<!-- Describe your approach to solving the problem. -->
Let's break this down into simple steps:

1. Preparation:

    - Create a DSU to track connected components
    - Add index to queries to remember original order
    - Sort both queries and edges by weight/limit (ascending)


2. Main Logic:

    - For each query in sorted order:
    - Add all edges with weight < query limit to DSU
    - Check if query nodes are in same component



The clever part is sorting queries by limit - this means we only need to process each edge once, and we can reuse the same DSU state for multiple queries.

---


# Complexity

- Time complexity: $$O((E + Q) \log(E + Q))$$ where E is number of edges and Q is number of queries

    - Sorting takes O(E logE) and O(Q logQ)
    - DSU operations are nearly constant time


- Space complexity: $$O(N + Q)$$

    - N for DSU parent array
    - Q for storing query indices


# Code
```cpp []
class DSU {
    vector<int> parent, size;
    int n;
public:
    DSU(int n) {
        this->n = n;
        size.resize(n + 1, 1);
        parent.resize(n + 1, 0);
        iota(begin(parent), end(parent), 0);
    }

    int findParent(int x) {
        return parent[x] = (parent[x] == x) ? x : findParent(parent[x]);
    }

    void Union(int a, int b) {
        a = findParent(a);
        b = findParent(b);
        
        if(a == b) return;

        if(size[a] >= size[b]) {
            parent[b] = a;
            size[a] += size[b];
        } else {
            parent[a] = b;
            size[b] += size[a];
        }
    }
};


class Solution {
public:
    vector<bool> distanceLimitedPathsExist(int n, vector<vector<int>>& edgeList, vector<vector<int>>& queries) { 
        int m = queries.size();
        vector<bool> ans(m, false);

        DSU dsu(n);
        // I am thinking to use 1 dsu, sort the queries on the basis of limit and 
        // sort edgeList also on the basis of distance
        // for each query go till limit and add those nodes in dsu simple
        for(int i = 0; i < m; i++) {
            queries[i].push_back(i);
        }

        sort(begin(queries), end(queries), [&](vector<int>& a, vector<int>& b) {
            return a[2] < b[2]; // increasing order of limit
        });

        sort(begin(edgeList), end(edgeList), [&](vector<int>& a, vector<int>& b) {
            return a[2] < b[2]; // increasing order of distance
        });

        int j = 0;
        for(int i = 0; i < m; i++) {
            int p = queries[i][0], q = queries[i][1], limit = queries[i][2];
            while(j < edgeList.size() && edgeList[j][2] < limit){
                dsu.Union(edgeList[j][0], edgeList[j][1]); // add them to the union
                j++;
            }
            
            if(dsu.findParent(p) == dsu.findParent(q)) ans[queries[i][3]] = true;
        }
        return ans;
    }
};
```
```python []
class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
        
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, a, b):
        pa, pb = self.find(a), self.find(b)
        if pa == pb: return
        
        if self.size[pa] >= self.size[pb]:
            self.parent[pb] = pa
            self.size[pa] += self.size[pb]
        else:
            self.parent[pa] = pb
            self.size[pb] += self.size[pa]

class Solution:
    def distanceLimitedPathsExist(self, n: int, edgeList: List[List[int]], queries: List[List[int]]) -> List[bool]:
        # Add index to queries to remember original order
        for i in range(len(queries)):
            queries[i].append(i)
            
        # Sort edges and queries by weight/limit
        edgeList.sort(key=lambda x: x[2])
        queries.sort(key=lambda x: x[2])
        
        dsu = DSU(n)
        ans = [False] * len(queries)
        j = 0  # pointer for edgeList
        
        # Process each query
        for p, q, limit, original_index in queries:
            # Add all edges with weight < limit
            while j < len(edgeList) and edgeList[j][2] < limit:
                dsu.union(edgeList[j][0], edgeList[j][1])
                j += 1
            
            # Check if nodes are connected
            ans[original_index] = dsu.find(p) == dsu.find(q)
            
        return ans
```
['Union Find', 'Graph', 'Sorting', 'C++', 'Python3']