Leetcode 1937 - Maximum Number of Points with Cost

Subscribe Send me a message home page tags


Problem Description

Link to Problem

You are given an m x n integer matrix points (0-indexed). Starting with 0 points, you want to maximize the number of points you can get from the matrix. To gain points, you must pick one cell in each row. Picking the cell at coordinates (r, c) will add points[r][c] to your score. However, you will lose points if you pick a cell too far from the cell that you picked in the previous row. For every two adjacent rows r and r + 1 (where 0 <= r < m - 1), picking cells at coordinates (r, c1) and (r + 1, c2) will subtract abs(c1 - c2) from your score.

Return the maximum number of points you can achieve.

Analysis

The problem has the structure of "guessing", which is a hint of using dynamic programming techniques. The guess is "which cell should we pick in the first row". Now we need to define the sub problem. Let \(M[i,j]\) denote the best points we can get if we select the cell \((i,j)\) for the matrix \(A[i:, :]\).

sub_problem.png

We can the derive the following recursive relation:

$$ M[i, j] = \max_{k} \left( M[i+1, k] - abs(k-j) \right) + A[i, j] $$

This gives us the following solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
public long maxPoints(int[][] points) {
    int nrows = points.length;
    if (nrows == 0) { return 0;}

    int ncols = points[0].length;

    long[][] M = new long[nrows][ncols];

    for (int i = 0; i < nrows; ++i) {
        for (int j = 0; j < ncols; ++j) {
            M[i][j] = 0;
        }
    }

    // Initialize the last row
    for (int j = 0; j < ncols; ++j) {
        M[nrows - 1][j] = points[nrows - 1][j];
    }

    // Fill in the M table
    for (int i = nrows - 2; i >= 0; --i) {
        for (int j = 0; j < ncols; ++j) {
            long maxValue = 0;

            for (int k = 0; k < ncols; ++k) {
                maxValue = Math.max(maxValue, M[i+1][k] - Math.abs(k - j));
            }

            M[i][j] = maxValue + points[i][j];
        }
    }

    long result = 0;

    for (int j = 0; j < ncols; ++j) {
        result = Math.max(result, M[0][j]);
    }

    return result;
}

Unfortunately, the above solution times out. It has O(m*n*n) time complexity and a quick glance in the discussion channel tells us there is faster solution with O(m*n) time complexity.

The problem is the for loop starting at line 25. The expression at line 26 is a general formula in the sense that it does not leverage anything in the special form of the cost term \(abs(k-j)\).

To get some intuition, let's reduce the size of the problem and only look at two adjacent rows. Let a[] denote the first row and b[] denote the second row. The problem is for each element in the first row, we need to select an element from the second row so that we have the best points.

We can further reduce the problem: we each element in array a, we can only select an element from array b which is on its left side. For example, we can only select cells from the green area in the second row for the blue element in array a.

reduced_problem_1.png

Now let's look at the values in the second row. Imagine v1 is a very large number. For example, if v1 = 1000 and other elements in the second row is 1, then for most of the elements in the first row, select v1 will give the best points. (why v1 is not preferred by all elements in the first row? It depends on the length of the row. For the right-most element in the first row, selecting v1 has the cost equals to the length of the row minus one.)

reduced_problem_2.png

Why is that? v1 is always prefered over v2 because v2 is only 1 unit closer to elements in the first row (remember the elements in the first row needs to be on the right side of the elements in the second row) but the v1 has a much larger value which is enough to compensate the cost.

Now suppose we have v1 - 3 < v4. In this case, v4 should be preferred over v1 by the red elements in the first row.

reduced_problem_3.png

This indicates that a linear scan of the array should give us the results. More specifically, we scan the two arrays from left to right, for each elements in array b, we want to know the groups of elements in array a whose preference is that element. This will give us something like the following:

reduced_problem_4.png

We can then do the same from the right to the left and combine the two resutls for each element in the first row. This gives us the following solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
private void processFromLeft(int n, int[] a, long[] b, long[] output) {
    int k = 0;

    while (k < n) {
        long value = b[k];
        int j = k;

        while ((j < n) && (b[j] <= value - (j-k))) {
            output[j] = Math.max(output[j], a[j] + value - (j - k));
            ++j;
        }

        k = j;

    }
}

private void processFromRight(int n, int[] a, long[] b, long[] output) {
    int k = n - 1;

    while (k > -1) {

        long value = b[k];
        int j = k;

        while ((j > -1) && (b[j] <= value - (k - j))) {
            output[j] = Math.max(output[j], a[j] + value - (k - j));
            --j;
        }

        k = j;
    }
}

public long maxPoints(int[][] points) {
    int nrows = points.length;
    if (nrows == 0) { return 0;}
    int ncols = points[0].length;

    long[] output = new long[ncols];

    for (int j = 0; j < ncols; ++j) {
        output[j] = points[nrows - 1][j];
    }

    for (int i = nrows - 2; i >= 0; --i) {
        long b[] = output.clone();
        this.processFromLeft(ncols, points[i], b, output);
        this.processFromRight(ncols, points[i], b, output);
    }

    long result = 0;

    for (int j = 0; j < ncols; ++j) {
        result = Math.max(result, output[j]);
    }

    return result;

}

Lesson Learned

----- END -----

Welcome to join reddit self-learning community.
Send me a message Subscribe to blog updates

Want some fun stuff?

/static/shopping_demo.png