1697. Checking Existence of Edge Length Limited Paths LeetCode Solution

Last updated: February 24, 2025

In this guide, you will get 1697. Checking Existence of Edge Length Limited Paths LeetCode Solution with the best time and space complexity. The solution to Checking Existence of Edge Length Limited Paths problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Checking Existence of Edge Length Limited Paths solution in C++
Checking Existence of Edge Length Limited Paths solution in Java
Checking Existence of Edge Length Limited Paths solution in Python
Additional Resources

1697. Checking Existence of Edge Length Limited Paths LeetCode Solution image

Problem Statement of Checking Existence of Edge Length Limited Paths

An undirected graph of n nodes is defined by edgeList, where edgeList[i] = [ui, vi, disi] denotes an edge between nodes ui and vi with distance disi. Note that there may be multiple edges between two nodes.
Given an array queries, where queries[j] = [pj, qj, limitj], your task is to determine for each queries[j] whether there is a path between pj and qj such that each edge on the path has a distance strictly less than limitj .
Return a boolean array answer, where answer.length == queries.length and the jth value of answer is true if there is a path for queries[j] is true, and false otherwise.

Example 1:

Input: n = 3, edgeList = [[0,1,2],[1,2,4],[2,0,8],[1,0,16]], queries = [[0,1,2],[0,2,5]]
Output: [false,true]
Explanation: The above figure shows the given graph. Note that there are two overlapping edges between 0 and 1 with distances 2 and 16.
For the first query, between 0 and 1 there is no path where each distance is less than 2, thus we return false for this query.
For the second query, there is a path (0 -> 1 -> 2) of two edges with distances less than 5, thus we return true for this query.

Example 2:

Input: n = 5, edgeList = [[0,1,10],[1,2,5],[2,3,9],[3,4,13]], queries = [[0,4,14],[1,4,13]]
Output: [true,false]
Explanation: The above figure shows the given graph.

Constraints:

2 <= n <= 105
1 <= edgeList.length, queries.length <= 105
edgeList[i].length == 3
queries[j].length == 3
0 <= ui, vi, pj, qj <= n – 1
ui != vi
pj != qj
1 <= disi, limitj <= 109
There may be multiple edges between two nodes.

Complexity Analysis

Time Complexity: O(\texttt{sort}(\texttt{queries}) + \texttt{sort}(\texttt{edgeList}))
Space Complexity: (q + n)

1697. Checking Existence of Edge Length Limited Paths LeetCode Solution in C++

class UnionFind {
 public:
  UnionFind(int n) : id(n), rank(n) {
    iota(id.begin(), id.end(), 0);
  }

  void unionByRank(int u, int v) {
    const int i = find(u);
    const int j = find(v);
    if (i == j)
      return;
    if (rank[i] < rank[j]) {
      id[i] = j;
    } else if (rank[i] > rank[j]) {
      id[j] = i;
    } else {
      id[i] = j;
      ++rank[j];
    }
  }

  int find(int u) {
    return id[u] == u ? u : id[u] = find(id[u]);
  }

 private:
  vector<int> id;
  vector<int> rank;
};

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

    for (int i = 0; i < queries.size(); ++i)
      queries[i].push_back(i);

    ranges::sort(queries, ranges::less{},
                 [](const vector<int>& query) { return query[2]; });
    ranges::sort(edgeList, ranges::less{},
                 [](const vector<int>& edge) { return edge[2]; });

    int i = 0;  // i := edgeList's index
    for (const vector<int>& query : queries) {
      const int p = query[0];
      const int q = query[1];
      const int limit = query[2];
      // Union edges whose distances < limit.
      while (i < edgeList.size() && edgeList[i][2] < limit)
        uf.unionByRank(edgeList[i][0], edgeList[i++][1]);
      if (uf.find(p) == uf.find(q))
        ans[query.back()] = true;
    }

    return ans;
  }
};
/* code provided by PROGIEZ */

1697. Checking Existence of Edge Length Limited Paths LeetCode Solution in Java

class UnionFind {
  public UnionFind(int n) {
    id = new int[n];
    rank = new int[n];
    for (int i = 0; i < n; ++i)
      id[i] = i;
  }

  public void unionByRank(int u, int v) {
    final int i = find(u);
    final int j = find(v);
    if (i == j)
      return;
    if (rank[i] < rank[j]) {
      id[i] = j;
    } else if (rank[i] > rank[j]) {
      id[j] = i;
    } else {
      id[i] = j;
      ++rank[j];
    }
  }

  public int find(int u) {
    return id[u] == u ? u : (id[u] = find(id[u]));
  }

  private int[] id;
  private int[] rank;
}

class Solution {
  public boolean[] distanceLimitedPathsExist(int n, int[][] edgeList, int[][] queries) {
    boolean[] ans = new boolean[queries.length];
    int[][] qs = new int[queries.length][4];
    UnionFind uf = new UnionFind(n);

    for (int i = 0; i < queries.length; ++i) {
      qs[i][0] = queries[i][0];
      qs[i][1] = queries[i][1];
      qs[i][2] = queries[i][2];
      qs[i][3] = i;
    }

    Arrays.sort(qs, (a, b) -> Integer.compare(a[2], b[2]));
    Arrays.sort(edgeList, (a, b) -> Integer.compare(a[2], b[2]));

    int i = 0; // i := edgeList's index
    for (int[] q : qs) {
      // Union edges whose distances < limit (q[2]).
      while (i < edgeList.length && edgeList[i][2] < q[2])
        uf.unionByRank(edgeList[i][0], edgeList[i++][1]);
      if (uf.find(q[0]) == uf.find(q[1]))
        ans[q[3]] = true;
    }

    return ans;
  }
}
// code provided by PROGIEZ

1697. Checking Existence of Edge Length Limited Paths LeetCode Solution in Python

N/A
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents