I was given a question similar to https://leetcode.com/problems/shortest-path-in-a-grid-with-obstacles-elimination/, elaborated below.
You are given an m x n integer matrix grid where each cell is either 0 (empty), 1 (obstacle) or 2 (stone).
You can move up, down, left, or right. However you can't go into an obstable cell but you can go into a cell with a stone, which cost you 1 health point.
Initially you have X health points and you are at cell (pi, pj). You need to walk to cell (qi, qj) and have at least 1 health point when you reach there.
Return -1 if is not possible.Since I have worked on the similar question before, I came up with my solution quickly, as below. Also I mentioned both the time complexity and the space complexity are O(num_of_rows * num_of_cols * X).
The interviewer didn't look pleased but subsequently asked if the time complexity of this implementation is the same as that of a DFS approach. I mentioned that DFS would be another complexity since in BFS we just need to reach every state <row, col, health_point> for only once but in DFS we might have to reach every state for multiple times. I didn't give the time complexity for DFS because I wasn't very confident about it although I felt it should be O(4^(num_of_rows * num_of_cols)), so I just said it would be different.
We've spent a lot of time discussing this time complexity thing but didn't reach a consensus. The interviewer then asked me to propose some improvements to improve the time complexity.
int minSteps(vector<vector<int>>& grid, int X, pair<int, int> start, pair<int, int> end) {
if (X == 0) {
return -1;
}
if (start == end) {
return 0;
}
int n = grid.size();
int m = grid[0].size();
queue<tuple<int, int, int>> q;
vector<vector<vector<int>>> steps(n, vector<vector<int>>(m, vector<int>(X + 1, -1)));
steps[start.first][start.second][X] = 0;
q.emplace(start.first, start.second, X);
while (!q.empty()) {
auto [r, c, hp] = q.front();
q.pop();
for (auto [dr, dc] : VALID_MOVES) {
int next_r = r + dr;
int next_c = c + dc;
if (next_r > n - 1 || next_r < 0 || next_c > m - 1 || next_c < 0)
{
continue;
}
if (grid[next_r][next_c] == 1) {
continue;
}
int nxt_hp = grid[next_r][next_c] == 2 ? hp - 1 : hp;
if (nxt_hp == 0)
{
continue;
}
if (steps[next_r][next_c][nxt_hp] != -1) {
continue;
}
steps[next_r][next_c][nxt_hp] = steps[r][c][hp] + 1;
q.emplace(next_r, next_c, nxt_hp);
}
}
const vector<int> &end_steps = steps[end.first][end.second];
int ans = -1;
for (int i = 1; i <= X; i++) {
if (end_steps[i] == -1) {
continue;
}
ans = ans == -1 ? end_steps[i] : min(ans, end_steps[i]);
}
return ans;
}After some time, I came up with this improved implementation which basically added an early termination logic, as below. I mentioned that this improved implementation would run a bit faster but doesn't necessarily improve the time complexity since it would cost more or less the same time as the first implementation does in the worst case.
However the interviewer was still frowning and claimed that this apparently resulted in a better time complexity. We couldn't convince each other evetually and the time was up.
int minSteps(vector<vector<int>>& grid, int X, pair<int, int> start, pair<int, int> end) {
if (X == 0) {
return -1;
}
if (start == end) {
return 0;
}
int n = grid.size();
int m = grid[0].size();
queue<tuple<int, int, int>> q;
vector<vector<vector<int>>> steps(n, vector<vector<int>>(m, vector<int>(X + 1, -1)));
steps[start.first][start.second][X] = 0;
q.emplace(start.first, start.second, X);
while (!q.empty()) {
auto [r, c, hp] = q.front();
q.pop();
for (auto [dr, dc] : VALID_MOVES) {
int next_r = r + dr;
int next_c = c + dc;
if (next_r > n - 1 || next_r < 0 || next_c > m - 1 || next_c < 0)
{
continue;
}
if (grid[next_r][next_c] == 1) {
continue;
}
int nxt_hp = grid[next_r][next_c] == 2 ? hp - 1 : hp;
if (nxt_hp == 0)
{
continue;
}
if (steps[next_r][next_c][nxt_hp] != -1) {
continue;
}
steps[next_r][next_c][nxt_hp] = steps[r][c][hp] + 1;
if (next_r == end.first && next_c == end.second) {
return steps[r][c][hp] + 1;
}
q.emplace(next_r, next_c, nxt_hp);
}
}
return -1;
}What do you guys think? Is there actually a solution which leads to a better time complexity than O(num_of_rows * num_of_cols * X)?