LeetCode 2662 - Minimum Cost of a Path With Special Roads

LeetCode Problem 2662

Difficulty: 🟡 Medium
Topics: Array, Graph Theory, Heap (Priority Queue), Shortest Path

Solution

Problem Understanding

The problem asks us to find the minimum cost to move from a starting point start = [startX, startY] to a target point target = [targetX, targetY] in a 2D plane. The movement in the plane has two options: moving directly from one point to another using the Manhattan distance cost |x2 - x1| + |y2 - y1|, or taking special roads that connect specific points at a fixed cost. Each special road is one-directional and can be used multiple times.

The input consists of the starting coordinates, the target coordinates, and a list of special roads. The expected output is the minimum total cost to reach the target from the start. Constraints indicate that coordinates are bounded up to 10^5, and the number of special roads is relatively small (≤ 200), which suggests we can leverage graph-based algorithms without running into performance issues.

Important edge cases include situations where using special roads is not optimal, roads that go backward (from higher coordinates to lower ones), and cases where multiple special roads connect overlapping points.

Approaches

A brute-force approach would try every combination of moves and special roads to compute all possible paths from start to target. While correct in principle, this approach is infeasible because the 2D space is enormous (10^5 x 10^5), and enumerating all paths would result in an exponential number of possibilities.

The key observation is that the problem can be treated as a shortest-path problem in a graph where nodes are the points involved: start, target, and all endpoints of special roads. The edges are either direct Manhattan moves or special roads. By restricting the nodes to these points, the problem size reduces drastically. We can then apply Dijkstra’s algorithm to compute the minimum cost efficiently.

Algorithm Walkthrough

1. Identify all relevant nodes: the start, the target, and all start and end points of special roads. This reduces the infinite 2D plane to a finite set of nodes.
2. Initialize a distance dictionary dist mapping each node to its minimum known cost. Set the start node’s cost to 0 and all others to infinity.
3. Use a priority queue to implement Dijkstra’s algorithm. Push the start node with cost 0 into the queue.
4. While the queue is not empty, pop the node with the smallest current cost. If this node is the target, return the cost immediately.
5. For each neighboring node (all other nodes):

• Compute the Manhattan distance as a candidate edge if moving normally.
• Check all special roads starting from the current node. If a road exists, consider its fixed cost to the road's endpoint.

6. If the total cost to a neighbor via the current node is smaller than its current dist, update dist and push it into the priority queue.
7. Continue until the target node is reached, ensuring that we have always propagated the minimum cost path first due to Dijkstra’s properties.

Why it works: The key invariant is that Dijkstra’s algorithm guarantees the first time a node is popped from the priority queue, its recorded distance is the minimum. By only considering relevant nodes and both Manhattan moves and special roads as edges, we ensure we explore all optimal paths efficiently.

Python Solution

from typing import List, Tuple
import heapq

class Solution:
    def minimumCost(self, start: List[int], target: List[int], specialRoads: List[List[int]]) -> int:
        points = [tuple(start), tuple(target)]
        for x1, y1, x2, y2, _ in specialRoads:
            points.append((x1, y1))
            points.append((x2, y2))
        
        points = list(set(points))  # unique points
        dist = {point: float('inf') for point in points}
        dist[tuple(start)] = 0
        heap = [(0, tuple(start))]
        
        while heap:
            cost, node = heapq.heappop(heap)
            if node == tuple(target):
                return cost
            if cost > dist[node]:
                continue
            for next_node in points:
                if next_node == node:
                    continue
                normal_cost = abs(next_node[0] - node[0]) + abs(next_node[1] - node[1])
                if cost + normal_cost < dist[next_node]:
                    dist[next_node] = cost + normal_cost
                    heapq.heappush(heap, (dist[next_node], next_node))
            for x1, y1, x2, y2, road_cost in specialRoads:
                if (x1, y1) == node:
                    next_node = (x2, y2)
                    if cost + road_cost < dist[next_node]:
                        dist[next_node] = cost + road_cost
                        heapq.heappush(heap, (dist[next_node], next_node))
        return dist[tuple(target)]

Explanation: We first collect all points relevant to the problem to form a manageable graph. The dist dictionary keeps track of the minimum cost to reach each point. The priority queue ensures that nodes with smaller costs are processed first, consistent with Dijkstra’s algorithm. For each node, we consider normal Manhattan moves and special roads as potential edges.

Go Solution

package main

import (
    "container/heap"
    "math"
)

type Point struct {
    x, y int
}

type Item struct {
    point Point
    cost  int
}

type PriorityQueue []Item

func (pq PriorityQueue) Len() int { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool { return pq[i].cost < pq[j].cost }
func (pq PriorityQueue) Swap(i, j int) { pq[i], pq[j] = pq[j], pq[i] }
func (pq *PriorityQueue) Push(x any) { *pq = append(*pq, x.(Item)) }
func (pq *PriorityQueue) Pop() any {
    old := *pq
    n := len(old)
    item := old[n-1]
    *pq = old[0 : n-1]
    return item
}

func minimumCost(start []int, target []int, specialRoads [][]int) int {
    pointsMap := map[Point]bool{}
    startPoint := Point{start[0], start[1]}
    targetPoint := Point{target[0], target[1]}
    pointsMap[startPoint] = true
    pointsMap[targetPoint] = true
    for _, road := range specialRoads {
        pointsMap[Point{road[0], road[1]}] = true
        pointsMap[Point{road[2], road[3]}] = true
    }

    points := make([]Point, 0, len(pointsMap))
    for p := range pointsMap { points = append(points, p) }

    dist := map[Point]int{}
    for _, p := range points { dist[p] = math.MaxInt64 }
    dist[startPoint] = 0

    pq := &PriorityQueue{}
    heap.Init(pq)
    heap.Push(pq, Item{startPoint, 0})

    for pq.Len() > 0 {
        item := heap.Pop(pq).(Item)
        node, cost := item.point, item.cost
        if node == targetPoint { return cost }
        if cost > dist[node] { continue }
        for _, next := range points {
            if next == node { continue }
            normalCost := abs(next.x-node.x) + abs(next.y-node.y)
            if cost+normalCost < dist[next] {
                dist[next] = cost + normalCost
                heap.Push(pq, Item{next, dist[next]})
            }
        }
        for _, road := range specialRoads {
            if Point{road[0], road[1]} == node {
                next := Point{road[2], road[3]}
                if cost+road[4] < dist[next] {
                    dist[next] = cost + road[4]
                    heap.Push(pq, Item{next, dist[next]})
                }
            }
        }
    }
    return dist[targetPoint]
}

func abs(a int) int {
    if a < 0 { return -a }
    return a
}

Go-specific notes: Go requires a custom priority queue using container/heap. Points are defined as structs, and we maintain a map for distances. The rest of the logic mirrors the Python solution.

Worked Examples

Example 1: start=[1,1], target=[4,5], specialRoads=[[1,2,3,3,2],[3,4,4,5,1]]