Solve an interesting problem by using DP, BFS and Dijkstra

LC 1824. Minimum Sideway Jumps

Why this problem is interesting to me

• This is the first problem I can use DP, BFS and Dijkstra to solve
• This is the first problem that I can use Deque (replace the Priority queue) to implement the Dijkstra to achieve O(V) complexity (recall the regular complexity of Dijkstra is O((V+E)log V).

DP

We can use DP to solve this problem. The state transitions can be found in the following image.

State transitions. The first path has 0 extra costs, the rest two paths have an extra cost of 1 for each.

Code

usually we use i for row and j for column. In this case, we flip it and use i as the first layer loop which is in the column direction.

int f[500010][3];
const int INF = 0x3f3f3f3f;
class Solution {
public:
    int minSideJumps(vector<int>& b) {
        memset(f, 0x3f, sizeof f);
        f[0][1] = 0;
        f[0][0] = f[0][2] = 1;
        const int n = b.size();
        for (int i = 1; i < n; ++i) {
            for (int j = 0; j < 3; ++j) {
                // when obstacle, continue
                if (b[i] == j + 1) continue;
                for (int k = 0; k < 3; ++k) {
                    int cost = 0;
                    // if the path contain side jump, set cost to 1.
                    if (k != j) cost = 1;
                    // if the corresponding path has obstacle, continue
                    if (b[i] == k + 1) continue;
                    f[i][j] = min(f[i][j], f[i-1][k] + cost);
                }
            }
        }
        return *min_element(f[n-1], f[n-1] + 3);
    }
};

run time

Runtime: 288 ms, faster than 80.65% of C++ online submissions for Minimum Sideway Jumps.
Memory Usage: 193.9 MB, less than 56.93% of C++ online submissions for Minimum Sideway Jumps.

BFS

We can use BFS to find the shortest path if every edge’s cost is equal. In this case, the cost can only be 0 and 1, we can still use BFS to achieve our goal: finding the shortest path.

Recall the regular BFS

1. this_level {node1, node2…}, depth = d
2. next_level = {neighbor of node for node in this_level if neighbor is not visited}, depth++

Of course, you can use queue, the idea is the same.

For this problem, let’s do slightly modification

1. this_level {node1, node2…}, depth = d
2. Add all zero cost reachable nodes to this_level as the cost is zero, it will not introduce extra cost. We look right for each node, and add valid nodes to this_level.
3. next_level = {neighbor of node for node in this_level if neighbor is not visited}, depth++

Code

const int N = 500010;
int visited[N][3];
class Solution {
public:
    int minSideJumps(vector<int>& b) {
        memset(visited, 0, sizeof(visited));
        const int n = b.size();
        vector<pair<int, int>> this_level;
        this_level.emplace_back(0, 1);
        visited[0][1] = 1;
        int depth = 0;
        while (true) {
            int len = this_level.size();
            // For each element, see whether can jump to the right as this has 0 cost. If so, put it in the current level.
            for (int idx = 0; idx < len; idx++) {
                auto [i, j] = this_level[idx];
                while (i + 1 < n && !visited[i+1][j] && b[i+1] != j +1) {
                    if (i + 1 == n -1) return depth;
                    visited[i+1][j] = 1;
                    this_level.emplace_back(i+1, j);
                    i++;
                }
            }
            vector<pair<int, int>>next_level;
            // check whether it can have a side jump. If so, put in next level.
            for (auto& [i, j] : this_level) {
                for (int k = 0; k < 3; ++k) {
                    if (k != j && b[i] != k + 1 && !visited[i][k]){
                        visited[i][k] = 1;
                        next_level.emplace_back(i, k);
                    }
                }
            }
            this_level = next_level;
            depth++;
        }
        return 0;
    }
};

run time

Runtime: 708 ms, faster than 19.90% of C++ online submissions for Minimum Sideway Jumps.
Memory Usage: 284 MB, less than 13.61% of C++ online submissions for Minimum Sideway Jumps.

Naive Dijkstra by using priority queue

We can naively apply the dijkstra algorithm. Dijkstra algorithm has the complexity of O((V + E)log V). We still can get the code AC.

Code

typedef pair<int, int> PII;
const int N = 500010<<2;
int dist[N];
class Solution {
public:
    int minSideJumps(vector<int>& b) {
        const int n = b.size();
        // set dist as INF
        memset(dist, 0x3f, sizeof(dist));
        // use (i<<2) + j to encode i and j.
        dist[1] = 0;
        priority_queue<PII, vector<PII>, greater<PII>> pq;
        pq.emplace(0, 1);
        while (!pq.empty()){
            auto [d, u] = pq.top(); pq.pop();
            if (d > dist[u]) continue;
            auto i = u>>2, j = u&3;
            for (int k = 0; k < 3; k++) {
                // go right
                if (j == k && i + 1 < n && b[i+1] != k + 1) {
                    auto v = ((i+1)<<2) + k;
                    if (dist[u] >= dist[v]) continue;
                    dist[v] = dist[u];
                    pq.emplace(dist[v], v);
                } 
                if (j != k && b[i] != k + 1) {
                    auto v = (i<<2) + k;
                    if (dist[u] + 1 >= dist[v]) continue;
                    dist[v] = dist[u] + 1;
                    pq.emplace(dist[v], v);
                }
            }
       }
       return min(dist[(n-1)<<2], min(dist[((n-1)<<2) + 1], dist[((n-1)<<2) + 2]));
    }
};

Run time

Runtime: 664 ms, faster than 22.43% of C++ online submissions forMinimum Sideway Jumps.
Memory Usage: 195.9 MB, less than 54.88% of C++ online submissions for Minimum Sideway Jumps.

Improved Dijkstra by using Deque.

This is essentially a special case of the Dijkstra algorithm. We only have 2 cost values, 0 or 1. We put 0 at the beginning and 1 at the end, which is essential a priority queue as:

Priority queue is popping the node with smallest cost. The smallest cost + an edge with 0 cost is still the smallest cost node. It can be push_front of the queue.

For this code, as we are using the deque and each node is put into the deque only one time, the complexity is O(V) where V is 3*n.

Code

typedef pair<int, int> PII;
const int N = 500010<<2;
int dist[N];
class Solution {
public:
    int minSideJumps(vector<int>& b) {
        const int n = b.size();
        // set dist as INF
        memset(dist, 0x3f, sizeof(dist));
        // use (i<<2) + j to encode i and j.
        dist[1] = 0;
        deque<PII> dq;
        dq.emplace_front(0, 1);
        while (!dq.empty()){
            auto [d, u] = dq.front(); dq.pop_front();
            if (d > dist[u]) continue;
            auto i = u>>2, j = u&3;
            for (int k = 0; k < 3; k++) {
                // go right
                if (j == k && i + 1 < n && b[i+1] != k + 1) {
                    auto v = ((i+1)<<2) + k;
                    if (dist[u] >= dist[v]) continue;
                    dist[v] = dist[u];
                    dq.emplace_front(dist[v], v);
                } 
                if (j != k && b[i] != k + 1) {
                    auto v = (i<<2) + k;
                    if (dist[u] + 1 >= dist[v]) continue;
                    dist[v] = dist[u] + 1;
                    dq.emplace_back(dist[v], v);
                }
            }
       }
       return min(dist[(n-1)<<2], min(dist[((n-1)<<2) + 1], dist[((n-1)<<2) + 2]));
    }
};

runtime, this is faster as it has the complexity of O(V)

Runtime: 448 ms, faster than 44.93% of C++ online submissions forMinimum Sideway Jumps.
Memory Usage: 244 MB, less than 37.14% of C++ online submissions for Minimum Sideway Jumps.

Top Down DP

We can also solve this problem by using top down DP. Here I am using python and we must use the list instead of dictionary for memo to get rid of TLE.

sys.setrecursionlimit(10**8)
class Solution:
    def minSideJumps(self, obstacles: List[int]) -> int:
        n = len(obstacles)
        memo = [[-1]*3 for _ in range(n)]
        def dp(i, j):
            if memo[i][j] != -1:
                return memo[i][j]
            if i == n-1:
                return 0
            if obstacles[i] == j + 1:
                return float('inf')
            ret = float('inf')
            for dj in range(3):
                if dj == j and obstacles[i + 1] != dj + 1:
                    ret = min(ret, dp(i + 1, dj))
                if dj != j and obstacles[i] != dj + 1:
                    ret = min(ret, dp(i + 1, dj) + 1)
            memo[i][j] = ret
            return ret
       
        return dp(0, 1)