Minimum Cost of a Path With Special Roads - Solution & Explanation
Problem Statement
You are given an array start where start = [startX, startY] represents your initial position (startX, startY) in a 2D space. You are also given the array target where target = [targetX, targetY] represents your target position (targetX, targetY).
The cost of going from a position (x1, y1) to any other position in the space (x2, y2) is |x2 - x1| + |y2 - y1|.
There are also some special roads. You are given a 2D array specialRoads where specialRoads[i] = [x1i, y1i, x2i, y2i, costi] indicates that the ith special road goes in one direction from (x1i, y1i) to (x2i, y2i) with a cost equal to costi. You can use each special road any number of times.
Return the minimum cost required to go from (startX, startY) to (targetX, targetY).
Example 1:
Input: start = [1,1], target = [4,5], specialRoads = [[1,2,3,3,2],[3,4,4,5,1]]
Output: 5
Explanation:
- (1,1) to (1,2) with a cost of |1 - 1| + |2 - 1| = 1.
- (1,2) to (3,3). Use
specialRoads[0]with the cost 2. - (3,3) to (3,4) with a cost of |3 - 3| + |4 - 3| = 1.
- (3,4) to (4,5). Use
specialRoads[1]with the cost 1.
So the total cost is 1 + 2 + 1 + 1 = 5.
Example 2:
Input: start = [3,2], target = [5,7], specialRoads = [[5,7,3,2,1],[3,2,3,4,4],[3,3,5,5,5],[3,4,5,6,6]]
Output: 7
Explanation:
It is optimal not to use any special edges and go directly from the starting to the ending position with a cost |5 - 3| + |7 - 2| = 7.
Note that the specialRoads[0] is directed from (5,7) to (3,2).
Example 3:
Input: start = [1,1], target = [10,4], specialRoads = [[4,2,1,1,3],[1,2,7,4,4],[10,3,6,1,2],[6,1,1,2,3]]
Output: 8
Explanation:
- (1,1) to (1,2) with a cost of |1 - 1| + |2 - 1| = 1.
- (1,2) to (7,4). Use
specialRoads[1]with the cost 4. - (7,4) to (10,4) with a cost of |10 - 7| + |4 - 4| = 3.
Constraints:
start.length == target.length == 21 <= startX <= targetX <= 1051 <= startY <= targetY <= 1051 <= specialRoads.length <= 200specialRoads[i].length == 5startX <= x1i, x2i <= targetXstartY <= y1i, y2i <= targetY1 <= costi <= 105
Approach Overview
Problem Overview: You start at a coordinate on a 2D grid and need the minimum cost to reach a target. Moving normally costs the Manhattan distance between points, but some special roads let you travel between two coordinates with a custom cost. The goal is to combine normal movement and special roads to minimize total travel cost.
Approach 1: Dijkstra's Algorithm (O(n log n) time, O(n) space)
Treat the problem as a graph shortest path problem. Each relevant coordinate becomes a node: the start position and the start/end points of every special road. From any node, you can move to another coordinate using Manhattan distance, or take a special road with its given cost. Use Dijkstra’s algorithm with a heap (priority queue) to always expand the currently cheapest reachable position. The key insight is that you do not need to explore every grid cell—only the special road endpoints. Each relaxation step compares the cost of normal movement versus the cost of using a special road. This approach efficiently computes the optimal route while avoiding the huge state space of the entire grid.
Approach 2: Bellman-Ford Algorithm (O(n^2) time, O(n) space)
Model the same coordinate set as a weighted graph and run the shortest path relaxation process using Bellman-Ford. Initialize the distance to each special road endpoint as the Manhattan distance from the start. Then repeatedly relax all edges: traveling normally between endpoints or taking a special road edge. After enough iterations, the distances converge to the minimum possible costs. Bellman-Ford works well because edge weights can be arbitrary but remain non-negative in this problem. The downside is performance—every iteration scans all edges, which increases runtime compared to Dijkstra’s priority-driven exploration.
Recommended for interviews: Dijkstra’s algorithm is the expected solution. It shows you recognize the hidden graph structure and can combine Manhattan distance with weighted edges efficiently. Bellman-Ford demonstrates understanding of general shortest-path relaxation but is rarely chosen unless negative edges exist. Interviewers usually want to see the priority queue–based optimization.
Approach 1: Approach 1: Dijkstra's Algorithm
This approach uses Dijkstra's Algorithm, which is suitable for finding the shortest path in a graph with non-negative weights. Consider each unique position as a node, with bi-directional edges between any two nodes representing the cost to travel between them, either directly or through special roads.
Start at the initial position and explore the reachable positions using both direct Manhattan distance and special roads. Maintain a priority queue (min-heap) to always extend the least costly path available. The algorithm terminates when the target position is reached with the minimum cost.
This solution initializes a priority queue with the starting position at cost zero and iterates through all paths, either direct or via special roads, continuously extending the shortest available path. Once it dequeues the target position from the queue, the accumulated cost is the answer.
Code
Python
JavaScript
Complexity
Time Complexity: O((N + M) * log(N + M)), where N is the number of special roads, and M is the number of possible positions considered.
Space Complexity: O(N + M), due to the priority queue and visited set.
Approach 2: Approach 2: Bellman-Ford Algorithm
The Bellman-Ford algorithm is another valid approach for solving the shortest path problem in a graph with directional edges and no negative weight cycles. Unlike Dijkstra's, this approach systematically updates all paths for a given number of iterations, ensuring the shortest path puts special roads and direct routes on equal footing.
We'll iterate over each node and relax edges associated with both direct movement and special roads. Given the scope of this problem, Bellman-Ford is computationally heavier but provides valuable comparative insights.
This solution uses the Bellman-Ford technique where edges of both traditional and special paths are added. The edge relaxation process ensures iteratively updating the shortest path until no further improvements can be achieved. The final distance derived for the target position will yield the lowest traversal cost.
Complexity
Time Complexity: O(N * M), where N is the number of edges (special roads + direct path), and M is the maximum number of nodes (positions of interest).
Space Complexity: O(N), predominantly due to storing edges and maintaining distance information.
Approach 3: Dijkstra
We can find that for each coordinate (x, y) we visit, suppose the minimum cost from the start point to (x, y) is d. If we choose to move directly to (targetX, targetY), then the total cost is d + |x - targetX| + |y - targetY|. If we choose to go through a special path (x_1, y_1) \rightarrow (x_2, y_2), then we need to spend |x - x_1| + |y - y_1| + cost to move from (x, y) to (x_2, y_2).
Therefore, we can use Dijkstra algorithm to find the minimum cost from the start point to all points, and then choose the smallest one from them.
We define a priority queue q, each element in the queue is a triple (d, x, y), which means that the minimum cost from the start point to (x, y) is d. Initially, we add (0, startX, startY) to the queue.
In each step, we take out the first element (d, x, y) in the queue, at this time we can update the answer, that is ans = min(ans, d + dist(x, y, targetX, targetY)). Then we enumerate all special paths (x_1, y_1) \rightarrow (x_2, y_2) and add (d + dist(x, y, x_1, y_1) + cost, x_2, y_2) to the queue.
Finally, when the queue is empty, we can get the answer.
The time complexity is O(n^2 times log n), and the space complexity is O(n^2). Where n is the number of special paths.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach 1: Dijkstra's Algorithm | Time Complexity: O((N + M) * log(N + M)), where N is the number of special roads, and M is the number of possible positions considered. |
| Approach 2: Bellman-Ford Algorithm | Time Complexity: O(N * M), where N is the number of edges (special roads + direct path), and M is the maximum number of nodes (positions of interest). |
| Dijkstra | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dijkstra's Algorithm with Priority Queue | O(n log n) | O(n) | Best general solution for non-negative weighted graphs and optimal interview answer |
| Bellman-Ford Algorithm | O(n^2) | O(n) | Useful when implementing generic edge relaxation or when negative edges could exist |
Video Solution
花花酱 LeetCode 2662. Minimum Cost of a Path With Special Roads - 刷题找工作 EP411 • Hua Hua • 3,170 views views
Watch 8 more video solutions →Frequently Asked Questions
Is Minimum Cost of a Path With Special Roads easy or hard?
Minimum Cost of a Path With Special Roads Python/Java solution
How to solve Minimum Cost of a Path With Special Roads in O(n log n)?
What is the best approach for Minimum Cost of a Path With Special Roads?
Is Minimum Cost of a Path With Special Roads asked at Google/Amazon/Meta?
What data structure is used in Minimum Cost of a Path With Special Roads?
What is the time complexity of Minimum Cost of a Path With Special Roads?
Ready to solve this problem?
Practice Minimum Cost of a Path With Special Roads with our built-in code editor and test cases.
Practice on FleetCode