Checking Existence of Edge Length Limited Paths II

Hard

Asked by:

5 views

Topics:

GraphsDynamic ProgrammingGreedy Algorithms

An undirected graph of n nodes is defined by the integer n. You are given a 2D integer array edges where each edges[i] = [u_i, v_i, w_i] indicates that there is an undirected edge between nodes u_i and v_i with weight w_i.

You are also given a 2D integer array queries where each queries[j] = [p_j, q_j, limit_j] asks if there is a path between nodes p_j and q_j such that each edge on the path has a weight strictly less than limit_j.

Return a boolean array answer where answer[j] is true if there is a path between p_j and q_j such that each edge on the path has a weight strictly less than limit_j, and false otherwise.

Since it is possible that multiple edges connect two nodes, you may assume that each edge has a unique weight.

Note:

0 <= n <= 10⁵
1 <= edges.length <= 10⁵
edges[i].length == 3
0 <= u_i, v_i < n
u_i != v_i
1 <= w_i <= 10⁹
1 <= queries.length <= 10⁵
queries[j].length == 3
0 <= p_j, q_j < n
p_j != q_j
1 <= limit_j <= 10⁹

Example 1:

Input: n = 3, edges = [[0,1,2],[1,2,4],[2,0,8],[1,0,16]], queries = [[0,1,2],[0,2,5]]
Output: [false,true]
Explanation: The first query asks if a path exists between 0 and 1 with all edges strictly less than 2. While the edge 0->1 has a weight less than 2, there are no paths between 0 and 1 where all edges are strictly less than 2. Therefore, the first query is false.
The second query asks if a path exists between 0 and 2 with all edges strictly less than 5. The path 0->1->2 has edges with weights 2 and 4, which are both strictly less than 5. Therefore, the second query is true.

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: The first query asks if a path exists between 0 and 4 with all edges strictly less than 14. The path 0->1->2->3->4 has edges with weights 10, 5, 9, and 13, which are all strictly less than 14. Therefore, the first query is true.
The second query asks if a path exists between 1 and 4 with all edges strictly less than 13. The path 1->2->3->4 has edges with weights 5, 9, and 13, which are not all strictly less than 13. Therefore, the second query is false.

Try coding it in LeetCode

Checking Existence of Edge Length Limited Paths II

Hard

Asked by:

5 views

Topics:

GraphsDynamic ProgrammingGreedy Algorithms

An undirected graph of n nodes is defined by the integer n. You are given a 2D integer array edges where each edges[i] = [u_i, v_i, w_i] indicates that there is an undirected edge between nodes u_i and v_i with weight w_i.

You are also given a 2D integer array queries where each queries[j] = [p_j, q_j, limit_j] asks if there is a path between nodes p_j and q_j such that each edge on the path has a weight strictly less than limit_j.

Return a boolean array answer where answer[j] is true if there is a path between p_j and q_j such that each edge on the path has a weight strictly less than limit_j, and false otherwise.

Since it is possible that multiple edges connect two nodes, you may assume that each edge has a unique weight.

Note:

0 <= n <= 10⁵
1 <= edges.length <= 10⁵
edges[i].length == 3
0 <= u_i, v_i < n
u_i != v_i
1 <= w_i <= 10⁹
1 <= queries.length <= 10⁵
queries[j].length == 3
0 <= p_j, q_j < n
p_j != q_j
1 <= limit_j <= 10⁹

Example 1:

Input: n = 3, edges = [[0,1,2],[1,2,4],[2,0,8],[1,0,16]], queries = [[0,1,2],[0,2,5]]
Output: [false,true]
Explanation: The first query asks if a path exists between 0 and 1 with all edges strictly less than 2. While the edge 0->1 has a weight less than 2, there are no paths between 0 and 1 where all edges are strictly less than 2. Therefore, the first query is false.
The second query asks if a path exists between 0 and 2 with all edges strictly less than 5. The path 0->1->2 has edges with weights 2 and 4, which are both strictly less than 5. Therefore, the second query is true.

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: The first query asks if a path exists between 0 and 4 with all edges strictly less than 14. The path 0->1->2->3->4 has edges with weights 10, 5, 9, and 13, which are all strictly less than 14. Therefore, the first query is true.
The second query asks if a path exists between 1 and 4 with all edges strictly less than 13. The path 1->2->3->4 has edges with weights 5, 9, and 13, which are not all strictly less than 13. Therefore, the second query is false.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible ranges for the node values (u, v) and edge lengths (weight) in the `edgeList`?
Can there be multiple edges between the same pair of nodes in the initial graph, or are we guaranteed a simple graph?
For a given query (p, q, max_weight), is it possible that p and q are the same node?
What should I return if no path exists between nodes p and q with a total weight less than or equal to the given limit `max_weight`?
What is the maximum number of nodes (n) in the graph, and what is the maximum number of queries in the `queries` list? This will help me reason about potential memory and time complexity considerations.

Brute Force Solution

Approach

The goal is to find a path between two locations where every road on that path has a length less than a given limit. The brute force method involves trying absolutely every possible route between the two locations and checking if it meets the length requirement.

Here's how the algorithm would work step-by-step:

Start at the starting location.
Consider all possible roads you can take from that starting location.
For each of those roads, check if its length is less than the given limit.
If it is, move to the location at the end of that road and remember the length of that road.
From that new location, again consider all possible roads you can take.
Again, for each of those roads, check if its length is less than the limit.
If it is, add its length to the total path length you've accumulated so far and move to the location at the end of that road.
Keep repeating this process, exploring every possible combination of roads until you either reach the destination location or run out of roads to take that are shorter than the limit.
If you reach the destination, check if the total length of the path you took is less than the limit. If so, you found a valid path. If not or if you never reached the destination, then that path does not work.
Repeat all the previous steps, starting back at the beginning but trying a different combination of roads each time, until you have tried every single possible route between the starting and ending locations.
If, after trying every single possible route, you found at least one path that satisfies the length limit, then a path exists. Otherwise, no such path exists.

Code Implementation

def check_existence_edge_length_limited_paths_ii_brute_force(number_of_nodes, edge_list, queries):
    answer = []
    for start_node, end_node, length_limit in queries:
        found_path = False
        
        # Iterate through all possible paths to find a valid one
        def depth_first_search(current_node, visited, current_path_length):
            nonlocal found_path
            if current_node == end_node:
                found_path = True
                return
            
            visited[current_node] = True

            # Explore all the adjacent nodes of current node
            for neighbor_one, neighbor_two, edge_weight in edge_list:
                if neighbor_one == current_node:
                    neighbor = neighbor_two
                elif neighbor_two == current_node:
                    neighbor = neighbor_one
                else:
                    continue
                    
                if not visited[neighbor] and edge_weight < length_limit:

                    # Recursive step
                    depth_first_search(neighbor, visited.copy(), current_path_length + edge_weight)

        visited = [False] * number_of_nodes
        depth_first_search(start_node, visited, 0)
        answer.append(found_path)
    return answer

Big(O) Analysis

Time Complexity

O(V^V) – The algorithm explores all possible paths between two nodes in a graph with V vertices. In the worst-case scenario, it might visit each vertex multiple times along different paths. Because it's brute force and considers every path and a path can visit every node, the number of paths could grow exponentially with the number of vertices (V). Considering all possible combinations leads to a complexity that is at least exponential, but since paths can contain every vertice multiple times, the number of paths could rise to V^V.

Space Complexity

O(N^V) – The described brute force solution explores all possible paths between the start and end locations. In the worst-case scenario, it might implicitly store a stack or queue of paths being explored. Each path can potentially visit all vertices (locations) V in the graph, and there could be an exponential number of such paths depending on the edge density which depends on the number of vertices (N=V), leading to an exponential space usage in the number of vertices. Therefore, the auxiliary space is proportional to the number of possible paths, which can grow up to O(N^V) in the worst-case, where V is the number of vertices, and N is the number of edges.

Optimal Solution

Approach

This problem is about finding if you can travel between cities with roads that have certain length limits. The most efficient way to solve this involves pre-processing the road information and then efficiently checking if a path exists for each travel request, rather than re-calculating paths every time.

Here's how the algorithm would work step-by-step:

First, organize all possible trips by their allowed road length limit, from smallest to largest. Also, organize the road information by road length, from smallest to largest.
Now, go through the trips one by one in the order of their road length limit. As you go, add roads to a 'network' of roads in order of length, but only roads whose length is less than the current trip's length limit.
For each trip, check if there is a path between the starting city and the destination city in the 'network' of roads that you have built so far. You can use a fast search technique to do this.
Because the roads and trips were processed in order of increasing length, the network will always contain all the roads relevant to each trip when it's being checked. You don't need to recalculate the network from scratch each time.

Code Implementation

class Solution:
    def distanceLimitedPathsExist(
        self, number_of_nodes: int, edge_list: list[list[int]], queries: list[list[int]]
    ) -> list[bool]:
        parent_nodes = list(range(number_of_nodes))

        def find(node_index: int) -> int:
            if parent_nodes[node_index] != node_index:
                parent_nodes[node_index] = find(parent_nodes[node_index])
            return parent_nodes[node_index]

        def union(node_index_1: int, node_index_2: int):
            root_1 = find(node_index_1)
            root_2 = find(node_index_2)
            if root_1 != root_2:
                parent_nodes[root_1] = root_2

        # Add query index to keep track of original order
        indexed_queries = [query + [index] for index, query in enumerate(queries)]
        indexed_queries.sort(key=lambda x: x[2])

        edge_list.sort(key=lambda x: x[2])

        results = [False] * len(queries)
        edge_index = 0

        # Iterate through queries in increasing order of limit
        for start_node, end_node, length_limit, query_index in indexed_queries:

            # Add edges smaller than current query limit
            while edge_index < len(edge_list) and edge_list[edge_index][2] < length_limit:
                node_1, node_2, _ = edge_list[edge_index]
                union(node_1, node_2)
                edge_index += 1

            # Check if path exists between start and end node
            results[query_index] = find(start_node) == find(end_node)

        return results

Big(O) Analysis

Time Complexity

O(m log m + q log q + q α(n)) – Let m be the number of edges, q be the number of queries (trips), and n be the number of cities. Sorting the edges takes O(m log m) time, and sorting the queries takes O(q log q) time. For each query, we add edges to the disjoint set union (DSU) data structure until the edge weight is greater than the query's limit, and check for connectivity using the find operation. The amortized cost of each find operation is nearly constant, represented by α(n), the inverse Ackermann function. Since we perform the find operation for each query, and potentially iterate through many edges for each query depending on query limits, the find operations contribute approximately O(q α(n)) to the total runtime. Therefore, the dominant terms give us a total time complexity of O(m log m + q log q + q α(n)).

Space Complexity

O(N + Q) – The solution uses a Union-Find data structure (or similar) to maintain the 'network' of roads, which in the worst case, could store all N roads as nodes/edges. Additionally, the algorithm stores the answers to Q queries where Q is the number of trips. Therefore, the space complexity is dominated by the Union-Find data structure and the storage for the query results. Thus the space used is O(N + Q) where N is the number of roads and Q is the number of trips.

Edge Cases

Case	How to Handle
Null or empty graph (n=0) and empty edge list/queries	Return an empty boolean array immediately if the graph has no nodes and there are no edges or queries.
Graph with one node (n=1) and non-empty edge list/queries	If there's one node, a path exists only if the source and destination are the same node, and the query length is non-negative.
All edge lengths are the same, but shorter than some query lengths	The algorithm should correctly identify paths not exceeding the query length, even with uniform edge weights.
Edge list contains duplicate edges (same u, v) with different lengths	The solution should pick the shortest edge between any two nodes if duplicates are provided, otherwise the longest edge could disconnect the components.
Very large graph (n close to limit) with many queries (q close to limit)	Kruskal's algorithm with DSU needs to be implemented efficiently to avoid exceeding time and space constraints given a large number of nodes and queries.
Edge weights are large integers nearing the maximum integer value	Ensure calculations (especially comparisons) do not lead to integer overflow; use 64-bit integers if needed.
Queries with source and destination nodes being the same.	A path always exists between the same node, so return true if query length is non-negative and false otherwise.
Graph is disconnected and queries ask about nodes in different components.	The algorithm should return false for such queries since no path exists between disconnected components regardless of edge length limits.