Minimum Cost to Reach Destination in Time
Asked at Databricks
Problem
You are given a weighted directed graph with n nodes and m edges. Each edge has a travel time and a cost. You start at node 0 with a certain amount of money and must reach node n-1 within a given time limit. Find the minimum cost to reach the destination, or return -1 if impossible.
Asked At
| Company | Difficulty | |
|---|---|---|
| Databricks | HARD | View all Databricks questions → |
How to Think About It
Brute force: enumerate all paths from node 0 to node n-1, check if each fits within the time constraint, and track minimum cost.
Notice that both time and money are constraints. A state must capture (node, time_used) to decide cost.
Use Dijkstra-like BFS where the priority is cost, and the state is (cost, node, time_used).
At each state, explore all outgoing edges. If moving to a neighbor stays within the time limit and offers a cheaper cost for that (node, time) pair, push it into the priority queue.
Maintain a 2D array dist[node][time] storing the minimum cost to reach each node at each time. The answer is the minimum of dist[n-1][t] for all t <= timeLimit.
Optimal Approach
Model the problem as a shortest path in a state space where each state is (node, time_used). Use a priority queue sorted by cost. For each state, explore all outgoing edges. If moving to a neighbor via an edge with cost c and travel time t_new stays within the time limit and improves dist[neighbor][time_used + t_new], update and push. The answer is the minimum cost across all time slots at node n-1. This is essentially Dijkstra on an expanded graph where time is an additional dimension.
What Trips People Up in Real Interviews
Clarify whether the graph can have negative costs (usually no). Ask about the range of timeLimit and n.
State the brute force approach first, then explain why DP or Dijkstra is needed.
Explain the state definition clearly: dist[node][time] = minimum cost.
Walk through a small example step by step before coding.
Discuss the time complexity: O(timeLimit * (n + m) * log(timeLimit * n)).
Solution Code
import heapq
def minCostToReachDestination(n, edges, timeLimit, maxCost):
graph = [[] for _ in range(n)]
for u, v, cost, time in edges:
graph[u].append((v, cost, time))
INF = float('inf')
dist = [[INF] * (timeLimit + 1) for _ in range(n)]
dist[0][0] = 0
pq = [(0, 0, 0)]
while pq:
d, u, t = heapq.heappop(pq)
if d > dist[u][t]:
continue
if u == n - 1:
return d
for v, cost, travel_time in graph[u]:
nt = t + travel_time
if nt <= timeLimit and d + cost < dist[v][nt]:
dist[v][nt] = d + cost
heapq.heappush(pq, (d + cost, v, nt))
return -1Frequently Asked Questions
What is the Minimum Cost to Reach Destination in Time problem?
You are given a weighted directed graph with n nodes and m edges. Each edge has a travel time and a cost. You start at node 0 with a certain amount of money and must reach node n-1 within a given time limit. Find the minimum cost to reach the destination, or return -1 if impossible.
How do you solve Minimum Cost to Reach Destination in Time?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Minimum Cost to Reach Destination in Time?
Minimum Cost to Reach Destination in Time is asked at Databricks. It is a hard difficulty problem.
What are common mistakes on Minimum Cost to Reach Destination in Time?
- Clarify whether the graph can have negative costs (usually no). Ask about the range of timeLimit and n.
- State the brute force approach first, then explain why DP or Dijkstra is needed.
- Explain the state definition clearly: dist[node][time] = minimum cost.
- Walk through a small example step by step before coding.
- Discuss the time complexity: O(timeLimit * (n + m) * log(timeLimit * n)).