Problem Statement in English

You’re given a network of n nodes, represented as a directed graph with edges, where each edge has an associated cost. Each node can either be online or offline, represented by the boolean array online. You are also given an integer k, which represents the maximum total cost you can incur while traversing the network.

You start at node 0 and want to reach node n-1. You can only traverse edges that lead to online nodes (or the destination node n-1). Your task is to find the maximum possible minimum edge cost along any valid path from node 0 to node n-1 such that the total cost of the path does not exceed k. If no such path exists, return -1.

You cannot traverse through offline nodes, except for the destination node n-1. It is guaranteed that there is at least one path from node 0 to node n-1, and that both nodes 0 and n-1 are online.

Approach

To solve this problem we use the following approach: we guess a minimum edge cost and check if there exists a valid path from node 0 to node n-1 such that all edges in the path have a cost greater than or equal to the guessed value and the total cost of the path does not exceed k. Since the question wants the maximum possible minimum edge cost, we can use binary search over the unique edge costs to find the answer.

We thus break this into 2 parts:

  1. Binary Search: We will perform a binary search over the unique edge costs to find the maximum possible minimum edge cost that allows a valid path from node 0 to node n-1.

  2. DFS Check: For each guessed minimum edge cost, we will perform a depth-first search (DFS) to check if there exists a valid path from node 0 to node n-1 such that all edges in the path have a cost greater than or equal to the guessed value and the total cost of the path does not exceed k. We will also use memoization to optimize our DFS.

And we’re done!

Solution in Python


class Solution:
    def findMaxPathScore(self, edges: List[List[int]], online: List[bool], k: int) -> int:
        n = len(online)
        
        # Build the adjacency list
        adj = defaultdict(list)
        unique_costs = set()
        for u, v, cost in edges:
            adj[u].append((v, cost))
            unique_costs.add(cost)
            
        # Possible scores sorted for binary search
        possible_scores = sorted(list(unique_costs))
        
        # Helper function to check if a valid path exists with a minimum edge cost >= target_score
        def can_reach(target_score: int) -> bool:
            # memo[u] will store the minimum path cost from u to n-1
            memo = {}
            
            def dfs(u):
                if u == n - 1:
                    return 0
                if u in memo:
                    return memo[u]
                
                min_cost = float('inf')
                for v, cost in adj[u]:
                    # Condition 1: Edge cost must be at least target_score
                    # Condition 2: Intermediate node must be online (or destination)
                    if cost >= target_score and (online[v] or v == n - 1):
                        min_cost = min(min_cost, cost + dfs(v))
                        
                memo[u] = min_cost
                return min_cost

            return dfs(0) <= k

        # Binary search over the possible scores
        low, high = 0, len(possible_scores) - 1
        ans = -1
        
        while low <= high:
            mid = (low + high) // 2
            if can_reach(possible_scores[mid]):
                ans = possible_scores[mid]  # Try to find a larger minimum edge cost
                low = mid + 1
            else:
                high = mid - 1
                
        return ans

Complexity

  • Time: $O((V + E) \log C)$

    • $V$ is the number of nodes, $E$ is the number of edges, and $C$ is the number of unique edge costs.

  • Space: $O(V + E)$

    • Since we store the adjacency list and memoization dictionary.

Mistakes I Made

I had to look this up :(

And we are done.