Posts tagged as “shortest path”

花花酱 LeetCode 2662. Minimum Cost of a Path With Special Roads

By zxi on April 30, 2023

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] = [x1_i, y1_i, x2_i, y2_i, cost_i] indicates that the i^th special road can take you from (x1_i, y1_i) to (x2_i, y2_i) with a cost equal to cost_i. 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: The optimal path from (1,1) to (4,5) is the following:
- (1,1) -> (1,2). This move has a cost of |1 - 1| + |2 - 1| = 1.
- (1,2) -> (3,3). This move uses the first special edge, the cost is 2.
- (3,3) -> (3,4). This move has a cost of |3 - 3| + |4 - 3| = 1.
- (3,4) -> (4,5). This move uses the second special edge, the cost is 1.
So the total cost is 1 + 2 + 1 + 1 = 5.
It can be shown that we cannot achieve a smaller total cost than 5.

Example 2:

Input: start = [3,2], target = [5,7], specialRoads = [[3,2,3,4,4],[3,3,5,5,5],[3,4,5,6,6]]
Output: 7
Explanation: It is optimal to not use any special edges and go directly from the starting to the ending position with a cost |5 - 3| + |7 - 2| = 7.

Constraints:

start.length == target.length == 2
1 <= startX <= targetX <= 10⁵
1 <= startY <= targetY <= 10⁵
1 <= specialRoads.length <= 200
specialRoads[i].length == 5
startX <= x1_i, x2_i <= targetX
startY <= y1_i, y2_i <= targetY
1 <= cost_i <= 10⁵

Solution: Dijkstra

Create a node for each point in special edges as well as start and target.
Add edges for special roads (note it’s directional)
Add edges for each pair of node with default cost, i.e. |x1-x2| + |y1-y2|
Run Dijkstra’s algorithm

Time complexity: O(n²logn)
Space complexity: O(n²)

C++

// Author: Huahua

class Solution {

public:

int minimumCost(vector<int>& start, vector<int>& target, vector<vector<int>>& specialRoads) {

unordered_map<long, int> ids;

vector<pair<int, int>> pos;

auto getId = [&](int x, int y) {

const auto key = ((unsigned long)x << 32) | y;

if (ids.count(key)) return ids[key];

const int id = ids.size();

ids[key] = id;

pos.emplace_back(x, y);

return id;

};

const int s = getId(start[0], start[1]);

const int t = getId(target[0], target[1]);

vector<vector<pair<int, int>>> g;

auto addEdge = [&](int x1, int y1, int x2, int y2, int c = INT_MAX) {

int n1 = getId(x1, y1);

int n2 = getId(x2, y2);

if (n1 == n2) return;

while (g.size() <= max(n1, n2)) g.push_back({});

int cost = min(c, abs(x1 - x2) + abs(y1 - y2));

g[n1].emplace_back(cost, n2);

// directional for special edge

if (c == INT_MAX) g[n2].emplace_back(cost, n1);

};

for (const auto& r : specialRoads)

addEdge(r[0], r[1], r[2], r[3], r[4]);

for (int i = 0; i < pos.size(); ++i)

for (int j = i + 1; j < pos.size(); ++j)

addEdge(pos[i].first, pos[i].second,

pos[j].first, pos[j].second);

vector<int> dist(ids.size(), INT_MAX);

dist[s] = 0;

priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> q;

q.emplace(0, s);

while (!q.empty()) {

auto [d, u] = q.top(); q.pop();

if (d > dist[u]) continue;

if (u == t) return d;

for (auto [c, v] : g[u])

if (d + c < dist[v])

q.emplace(dist[v] = d + c, v);

}

return -1;

}

};

花花酱 LeetCode 2642. Design Graph With Shortest Path Calculator

By zxi on April 29, 2023

There is a directed weighted graph that consists of n nodes numbered from 0 to n - 1. The edges of the graph are initially represented by the given array edges where edges[i] = [from_i, to_i, edgeCost_i] meaning that there is an edge from from_i to to_i with the cost edgeCost_i.

Implement the Graph class:

Graph(int n, int[][] edges) initializes the object with n nodes and the given edges.
addEdge(int[] edge) adds an edge to the list of edges where edge = [from, to, edgeCost]. It is guaranteed that there is no edge between the two nodes before adding this one.
int shortestPath(int node1, int node2) returns the minimum cost of a path from node1 to node2. If no path exists, return -1. The cost of a path is the sum of the costs of the edges in the path.

Example 1:

Input
["Graph", "shortestPath", "shortestPath", "addEdge", "shortestPath"]
[[4, [[0, 2, 5], [0, 1, 2], [1, 2, 1], [3, 0, 3]]], [3, 2], [0, 3], [[1, 3, 4]], [0, 3]]
Output
[null, 6, -1, null, 6]

Explanation

Graph g = new Graph(4, [[0, 2, 5], [0, 1, 2], [1, 2, 1], [3, 0, 3]]); g.shortestPath(3, 2); // return 6. The shortest path from 3 to 2 in the first diagram above is 3 -> 0 -> 1 -> 2 with a total cost of 3 + 2 + 1 = 6.
g.shortestPath(0, 3); // return -1. There is no path from 0 to 3. 
g.addEdge([1, 3, 4]); // We add an edge from node 1 to node 3, and we get the second diagram above. 
g.shortestPath(0, 3); // return 6. The shortest path from 0 to 3 now is 0 -> 1 -> 3 with a total cost of 2 + 4 = 6.

Constraints:

1 <= n <= 100
0 <= edges.length <= n * (n - 1)
edges[i].length == edge.length == 3
0 <= from_i, to_i, from, to, node1, node2 <= n - 1
1 <= edgeCost_i, edgeCost <= 10⁶
There are no repeated edges and no self-loops in the graph at any point.
At most 100 calls will be made for addEdge.
At most 100 calls will be made for shortestPath.

Solution 1: Floyd-Washall

Time complexity:
Init O(n³)
addEdge O(n²)
shortestPath O(1)

Space complexity: O(1)

C++

// Author: Huahua

class Graph {

public:

Graph(int n, vector<vector<int>>& edges):

n_(n),

d_(n, vector<long>(n, 1e18)) {

for (int i = 0; i < n; ++i)

d_[i][i] = 0;

for (const vector<int>& e : edges)

d_[e[0]][e[1]] = e[2];

for (int k = 0; k < n; ++k)

for (int i = 0; i < n; ++i)

for (int j = 0; j < n; ++j)

d_[i][j] = min(d_[i][j], d_[i][k] + d_[k][j]);

}

void addEdge(vector<int> edge) {

for (int i = 0; i < n_; ++i)

for (int j = 0; j < n_; ++j)

d_[i][j] = min(d_[i][j], d_[i][edge[0]] + edge[2] + d_[edge[1]][j]);

}

int shortestPath(int node1, int node2) {

return d_[node1][node2] >= 1e18 ? -1 : d_[node1][node2];

}

private:

int n_;

vector<vector<long>> d_;

};

Solution 2: Dijkstra

Time complexity:
Init: O(|E|) ~ O(n²)
AddEdge: O(1)
ShortestPath: O(|V|*log(|E|)) ~ O(n*logn)

Space complexity: O(E|) ~ O(n²)

C++

// Author: Huahua

class Graph {

public:

Graph(int n, vector<vector<int>>& edges): n_(n), g_(n) {

for (const auto& e : edges)

g_[e[0]].emplace_back(e[1], e[2]);

}

void addEdge(vector<int> edge) {

g_[edge[0]].emplace_back(edge[1], edge[2]);

}

int shortestPath(int node1, int node2) {

vector<int> dist(n_, INT_MAX);

dist[node1] = 0;

priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> q;

q.emplace(0, node1);

while (!q.empty()) {

const auto [d, u] = q.top(); q.pop();

if (u == node2) return d;

for (const auto& [v, c] : g_[u])

if (dist[u] + c < dist[v]) {

dist[v] = dist[u] + c;

q.emplace(dist[v], v);

}

return -1;

}

private:

int n_;

vector<vector<pair<int, int>>> g_;

};

花花酱 LeetCode 2146. K Highest Ranked Items Within a Price Range

By zxi on February 3, 2022

You are given a 0-indexed 2D integer array grid of size m x n that represents a map of the items in a shop. The integers in the grid represent the following:

0 represents a wall that you cannot pass through.
1 represents an empty cell that you can freely move to and from.
All other positive integers represent the price of an item in that cell. You may also freely move to and from these item cells.

It takes 1 step to travel between adjacent grid cells.

You are also given integer arrays pricing and start where pricing = [low, high] and start = [row, col] indicates that you start at the position (row, col) and are interested only in items with a price in the range of [low, high] (inclusive). You are further given an integer k.

You are interested in the positions of the k highest-ranked items whose prices are within the given price range. The rank is determined by the first of these criteria that is different:

Distance, defined as the length of the shortest path from the start (shorter distance has a higher rank).
Price (lower price has a higher rank, but it must be in the price range).
The row number (smaller row number has a higher rank).
The column number (smaller column number has a higher rank).

Return the k highest-ranked items within the price range sorted by their rank (highest to lowest). If there are fewer than k reachable items within the price range, return all of them.

Example 1:

Input: grid = [[1,2,0,1],[1,3,0,1],[0,2,5,1]], pricing = [2,5], start = [0,0], k = 3
Output: [[0,1],[1,1],[2,1]]
Explanation: You start at (0,0).
With a price range of [2,5], we can take items from (0,1), (1,1), (2,1) and (2,2).
The ranks of these items are:
- (0,1) with distance 1
- (1,1) with distance 2
- (2,1) with distance 3
- (2,2) with distance 4
Thus, the 3 highest ranked items in the price range are (0,1), (1,1), and (2,1).

Example 2:

Input: grid = [[1,2,0,1],[1,3,3,1],[0,2,5,1]], pricing = [2,3], start = [2,3], k = 2
Output: [[2,1],[1,2]]
Explanation: You start at (2,3).
With a price range of [2,3], we can take items from (0,1), (1,1), (1,2) and (2,1).
The ranks of these items are:
- (2,1) with distance 2, price 2
- (1,2) with distance 2, price 3
- (1,1) with distance 3
- (0,1) with distance 4
Thus, the 2 highest ranked items in the price range are (2,1) and (1,2).

Example 3:

Input: grid = [[1,1,1],[0,0,1],[2,3,4]], pricing = [2,3], start = [0,0], k = 3
Output: [[2,1],[2,0]]
Explanation: You start at (0,0).
With a price range of [2,3], we can take items from (2,0) and (2,1). 
The ranks of these items are: 
- (2,1) with distance 5
- (2,0) with distance 6
Thus, the 2 highest ranked items in the price range are (2,1) and (2,0). 
Note that k = 3 but there are only 2 reachable items within the price range.

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 10⁵
1 <= m * n <= 10⁵
0 <= grid[i][j] <= 10⁵
pricing.length == 2
2 <= low <= high <= 10⁵
start.length == 2
0 <= row <= m - 1
0 <= col <= n - 1
grid[row][col] > 0
1 <= k <= m * n

Solution: BFS + Sorting

Use BFS to collect reachable cells and sort afterwards.

Time complexity: O(mn + KlogK) where K = # of reachable cells.

Space complexity: O(mn)

C++

// Author: Huahua

class Solution {

public:

vector<vector<int>> highestRankedKItems(vector<vector<int>>& grid, vector<int>& pricing, vector<int>& start, int k) {

const int m = grid.size();

const int n = grid[0].size();

const vector<int> dirs{1, 0, -1, 0, 1};

vector<vector<int>> seen(m, vector<int>(n));

seen[start[0]][start[1]] = 1;

vector<vector<int>> cells;

queue<array<int, 3>> q;

q.push({start[0], start[1], 0});

while (!q.empty()) {

auto [y, x, d] = q.front(); q.pop();

if (grid[y][x] >= pricing[0] && grid[y][x] <= pricing[1])

cells.push_back({d, grid[y][x], y, x});

for (int i = 0; i < 4; ++i) {

const int tx = x + dirs[i];

const int ty = y + dirs[i + 1];

if (tx < 0 || tx >= n || ty < 0 || ty >= m

|| !grid[ty][tx] || seen[ty][tx]++) continue;

q.push({ty, tx, d + 1});

}

sort(begin(cells), end(cells), less<vector<int>>());

vector<vector<int>> ans;

for (int i = 0; i < min(k, (int)(cells.size())); ++i)

ans.push_back({cells[i][2], cells[i][3]});

return ans;

}

};

花花酱 LeetCode 1926. Nearest Exit from Entrance in Maze

By zxi on December 30, 2021

You are given an m x n matrix maze (0-indexed) with empty cells (represented as '.') and walls (represented as '+'). You are also given the entrance of the maze, where entrance = [entrance_row, entrance_col] denotes the row and column of the cell you are initially standing at.

In one step, you can move one cell up, down, left, or right. You cannot step into a cell with a wall, and you cannot step outside the maze. Your goal is to find the nearest exit from the entrance. An exit is defined as an empty cell that is at the border of the maze. The entrance does not count as an exit.

Return the number of steps in the shortest path from the entrance to the nearest exit, or -1 if no such path exists.

Example 1:

Input: maze = [["+","+",".","+"],[".",".",".","+"],["+","+","+","."]], entrance = [1,2]
Output: 1
Explanation: There are 3 exits in this maze at [1,0], [0,2], and [2,3].
Initially, you are at the entrance cell [1,2].
- You can reach [1,0] by moving 2 steps left.
- You can reach [0,2] by moving 1 step up.
It is impossible to reach [2,3] from the entrance.
Thus, the nearest exit is [0,2], which is 1 step away.

Example 2:

Input: maze = [["+","+","+"],[".",".","."],["+","+","+"]], entrance = [1,0]
Output: 2
Explanation: There is 1 exit in this maze at [1,2].
[1,0] does not count as an exit since it is the entrance cell.
Initially, you are at the entrance cell [1,0].
- You can reach [1,2] by moving 2 steps right.
Thus, the nearest exit is [1,2], which is 2 steps away.

Example 3:

Input: maze = [[".","+"]], entrance = [0,0]
Output: -1
Explanation: There are no exits in this maze.

Constraints:

maze.length == m
maze[i].length == n
1 <= m, n <= 100
maze[i][j] is either '.' or '+'.
entrance.length == 2
0 <= entrance_row < m
0 <= entrance_col < n
entrance will always be an empty cell.

Solution: BFS

Use BFS to find the shortest path. We can re-use the board for visited array.

Time complexity: O(m*n)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {

const int m = maze.size();

const int n = maze[0].size();

const vector<int> dirs{0, -1, 0, 1, 0};

queue<pair<int, int>> q;

q.emplace(entrance[1], entrance[0]);

for (int steps = 0; !q.empty(); ++steps) {

for (int s = q.size(); s; --s) {

const auto [x, y] = q.front(); q.pop();

if (x == 0 || x == n - 1 || y == 0 || y == m - 1)

if (x != entrance[1] || y != entrance[0])

return steps;

for (int i = 0; i < 4; ++i) {

const int tx = x + dirs[i];

const int ty = y + dirs[i + 1];

if (tx < 0 || tx >= n || ty < 0 || ty >= m || maze[ty][tx] != '.') continue;

maze[ty][tx] = '*';

q.emplace(tx, ty);

}

return -1;

}

};

花花酱 LeetCode 2096. Step-By-Step Directions From a Binary Tree Node to Another

By zxi on December 5, 2021

You are given the root of a binary tree with n nodes. Each node is uniquely assigned a value from 1 to n. You are also given an integer startValue representing the value of the start node s, and a different integer destValue representing the value of the destination node t.

Find the shortest path starting from node s and ending at node t. Generate step-by-step directions of such path as a string consisting of only the uppercase letters 'L', 'R', and 'U'. Each letter indicates a specific direction:

'L' means to go from a node to its left child node.
'R' means to go from a node to its right child node.
'U' means to go from a node to its parent node.

Return the step-by-step directions of the shortest path from node s to node t.

Example 1:

Input: root = [5,1,2,3,null,6,4], startValue = 3, destValue = 6
Output: "UURL"
Explanation: The shortest path is: 3 → 1 → 5 → 2 → 6.

Example 2:

Input: root = [2,1], startValue = 2, destValue = 1
Output: "L"
Explanation: The shortest path is: 2 → 1.

Constraints:

The number of nodes in the tree is n.
2 <= n <= 10⁵
1 <= Node.val <= n
All the values in the tree are unique.
1 <= startValue, destValue <= n
startValue != destValue

Solution: Lowest common ancestor

It’s no hard to see that the shortest path is from the start node to the lowest common ancestor (LCA) of (start, end), then to the end node. The key is to find the LCA while finding paths from root to two nodes.

We can use recursion to find/build a path from root to a target node.
The common prefix of these two paths is the path from root to the LCA that we need to remove from the shortest path.
e.g.
root to start “LLRLR”
root to dest “LLLR”
common prefix is “LL”, after removing, it becomes:
LCA to start “RLR”
LCA to dest “LR”
Final path becomes “UUU” + “LR” = “UUULR”

The final step is to replace the L/R with U for the start path since we are moving up and then concatenate with the target path.

Time complexity: O(n)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

string getDirections(TreeNode* root, int startValue, int destValue) {

string startPath;

string destPath;

buildPath(root, startValue, startPath);

buildPath(root, destValue, destPath);

// Remove common suffix (shared path from root to LCA)

while (!startPath.empty() && !destPath.empty()

&& startPath.back() == destPath.back()) {

startPath.pop_back();

destPath.pop_back();

}

reverse(begin(destPath), end(destPath));

return string(startPath.size(), 'U') + destPath;

}

private:

bool buildPath(TreeNode* root, int t, string& path) {

if (!root) return false;

if (root->val == t) return true;

if (buildPath(root->left, t, path)) {

path.push_back('L');

return true;

} else if (buildPath(root->right, t, path)) {

path.push_back('R');

return true;

}

return false;

}

};