C++ Coding Exercise – Triangle – Leetcode Online Judge – O(n) Dynamic Programming Optimisation

This puzzle is from Leetcode Online Judge and this may appear quite often during interviews.

This puzzle asks you to find the minimal sum for a number triangle.

Leetcode Online Judge – Triangle

You can walk from top down or bottom up, which doesn’t make much difference since the sum is the same. The task description suggests that a O(n) space solution exists.

If we walk from top to the bottom, at the end, when we reach the bottom, we will have n numbers and we need to find the minimal among these numbers. Instead, if you walk from the bottom upwards, at the top, we will have only 1 number, which is the answer. Therefore, the second approach is better.

At the row n, every position comes possibly from two paths, both are at row n+1, therefore, we can use only one array to store the ‘latest’ minimals and repeatedly update the answers.

The dynamically programming (DP) algorithm is suitable for this kind of puzzles. The most important characteristics of DP is that the final solutions are also the solutions to the sub problems.

If f(n, m) denotes the solution for row n and column m then the following applies:

f(n, m) = N(n, m) + Min( f(n + 1, m), f(n + 1, m + 1) ) and N(n, m) represents the number at row n column m.

From the above equation, we also know that f(n, ) depends on the input of f(n + 1, ) only and that is the clue that we can reduce O(n²) space to O(n)

The C++ solution gets accepted within 40ms on Leetcode online judge.

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

class Solution {
public:
    int minimumTotal(vector<vector<int> > &triangle) {
        int r = triangle.size();
        int *ans = new int[r];
        for (int i = 0; i < r; i ++) {
            ans[i] = triangle[r - 1][i]; // initialization with the bottom row
        }
        for (int i = r - 2; i >= 0; i --) {
            for (int j = 0; j < r; j ++) {
                ans[j] = triangle[i][j] + (ans[j] < ans[j + 1] ? ans[j] : ans[j + 1]);
            }
        }
        return ans[0];
    }
};

class Solution {
public:
    int minimumTotal(vector<vector<int> > &triangle) {
        int r = triangle.size();
        int *ans = new int[r];
        for (int i = 0; i < r; i ++) {
            ans[i] = triangle[r - 1][i]; // initialization with the bottom row
        }
        for (int i = r - 2; i >= 0; i --) {
            for (int j = 0; j < r; j ++) {
                ans[j] = triangle[i][j] + (ans[j] < ans[j + 1] ? ans[j] : ans[j + 1]);
            }
        }
        return ans[0];
    }
};

The algorithm complexity is O(n²) (quadric).

–EOF (The Ultimate Computing & Technology Blog) —