Dynamic Programming Algorithms to Compute the Longest Chain of Blocks

You are given a list blocks where each block contains two integers [start, end] where start < end. You can join two blocks if the end of one is equal to the start of another. Return the length of the longest chain of blocks.

Constraints
n ≤ 100,000 where n is the length of blocks.
Example 1
Input

1 2 3 4 5 6 7

blocks = [     [3, 4],     [4, 5],     [3, 7],     [0, 1],     [1, 3] ]

blocks = [
    [3, 4],
    [4, 5],
    [3, 7],
    [0, 1],
    [1, 3]
]

Output
4
Explanation
We can form the following chain: [0, 1], [1, 3], [3, 4], [4, 5]

Top Down Dynamic Programming Algorithm to Compute Longest Chain

We can preprocess the blocks and index the start in a hash table, so that given a start, we know which blocks start with it. The value of the hash map is the list of endpoints. Then we can perform a Depth First Search Algorithm (DFS) with Memoization (which is essentially a Top-Down Dynamic Programming Algorithm) to follow the blocks and increment the counter/length when we are able to jump to another block.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

int longestChain(vector<vector<int>>& blocks) {
    if (blocks.empty()) return 0;
    unordered_map<int, vector<int>> data;
    for (auto &n: blocks) {
        data[n[0]].push_back(n[1]);
    }
    unordered_map<int, int> memo;
    function<int(int)> dfs = [&](int start) {
        if (!data.count(start)) return 0;
        if (memo.count(start)) return memo[start];
        int ans = 0;
        for (auto &n: data[start]) {
            ans = max(ans, dfs(n) + 1);
        }
        return memo[start] = ans;
    };
    int ans = 0;
    for (auto &[a, b]: data) {
        ans = max(ans, dfs(a));
    }
    return ans;
} 

int longestChain(vector<vector<int>>& blocks) {
    if (blocks.empty()) return 0;
    unordered_map<int, vector<int>> data;
    for (auto &n: blocks) {
        data[n[0]].push_back(n[1]);
    }
    unordered_map<int, int> memo;
    function<int(int)> dfs = [&](int start) {
        if (!data.count(start)) return 0;
        if (memo.count(start)) return memo[start];
        int ans = 0;
        for (auto &n: data[start]) {
            ans = max(ans, dfs(n) + 1);
        }
        return memo[start] = ans;
    };
    int ans = 0;
    for (auto &[a, b]: data) {
        ans = max(ans, dfs(a));
    }
    return ans;
} 

The time complexity is O(N) where N is the number of blocks as maximum each block will be computed once (we have the hash table to store the results). The space complexity is O(N).

Sort and Bottom-Up Dynamic Programming to Compute Longest Chain of Blocks

We can sort the blocks in ascending order, and if two blocks start the same position, we sort their end positions in ascending order for example [3, 5] comes before [3, 6].

Once the blocks are sorted such way, we can go through the blocks and compute the following Dynamic Programming equation:

dp[e] = max(dp[e], dp[s] + 1)

The following implements this algorithm:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

int longestChain(vector<vector<int>>& blocks) {
    if (blocks.empty()) return 0;
    sort(begin(blocks), end(blocks));
    unordered_map<int, int> dp;
    for (auto &n: blocks) {
        auto start = n[0];
        auto end = n[1];
        dp[end] = max(dp[end], dp[start] + 1);
    }
    int ans = 0;
    for (auto &[a, b]: dp) {
        ans = max(b, ans);
    }
    return ans;
} 

int longestChain(vector<vector<int>>& blocks) {
    if (blocks.empty()) return 0;
    sort(begin(blocks), end(blocks));
    unordered_map<int, int> dp;
    for (auto &n: blocks) {
        auto start = n[0];
        auto end = n[1];
        dp[end] = max(dp[end], dp[start] + 1);
    }
    int ans = 0;
    for (auto &[a, b]: dp) {
        ans = max(b, ans);
    }
    return ans;
} 

And, the answer is the maximum value of all dp[e]. The complexity is O(NLogN) as the sorting dominates. The space complexity is O(N) as we are using a hash table to store the DP values.

–EOF (The Ultimate Computing & Technology Blog) —