Reference: LeetCode
Difficulty: Medium

Problem

Given a matrix of integers A with R rows and C columns, find the maximum score of a path starting at [0, 0] and ending at [R-1, C-1].

The score of a path is the minimum value in that path. For example, the value of the path 8 → 4 → 5 → 9 is 4.

A path moves some number of times from one visited cell to any neighbouring unvisited cell in one of the 4 cardinal directions (north, east, west, south).

Note:

  • 1 <= R, C <= 100
  • 0 <= A[i][j] <= 10^9

Example:

1
2
3
4
5
6
7
8
Input: [[5,4,5],[1,2,6],[7,4,6]]
Output: 4

Input: [[2,2,1,2,2,2],[1,2,2,2,1,2]]
Output: 2

Input: [[3,4,6,3,4],[0,2,1,1,7],[8,8,3,2,7],[3,2,4,9,8],[4,1,2,0,0],[4,6,5,4,3]]
Output: 3

Analysis

Backtracking

Here is the code of backtracking Time Limit Exceeded.

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
public int maximumMinimumPath(int[][] A) {
if (A == null || A.length == 0 || A[0] == null || A[0].length == 0) {
return 0;
}
int row = A.length;
int col = A[0].length;
boolean[][] visited = new boolean[row][col];
return backtracking(0, 0, Integer.MAX_VALUE, visited, A);
}

private int backtracking(int r, int c, int score, boolean[][] visited, int[][] A) {
// Assume A has at least one element
int row = A.length;
int col = A[0].length;
if (r == row - 1 && c == col - 1) {
return Math.min(A[r][c], score);
}

// consider current value
score = Math.min(A[r][c], score);
visited[r][c] = true;

// 4 directions
int up = Integer.MIN_VALUE;
if (r - 1 >= 0 && !visited[r - 1][c]) { // up
up = backtracking(r - 1, c, score, visited, A);
}
int down = Integer.MIN_VALUE;
if (r + 1 <= row - 1 && !visited[r + 1][c]) {
down = backtracking(r + 1, c, score, visited, A);
}
int left = Integer.MIN_VALUE;
if (c - 1 >= 0 && !visited[r][c - 1]) {
left = backtracking(r, c - 1, score, visited, A);
}
int right = Integer.MIN_VALUE;
if (c + 1 <= col - 1 && !visited[r][c + 1]) {
right = backtracking(r, c + 1, score, visited, A);
}

// reset
visited[r][c] = false;

int m1 = Math.max(up, down);
int m2 = Math.max(left, right);
return Math.max(m1, m2);
}

Time: $O(4^{RC})$
Space: $O(RC)$

Priority Queue

Use a max heap. Consider the following example.

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

pq.add(6)
pq.remove() -> 6
pq.add(8, 7) // add all 6's unvisited neighbors 7 and 8
pq.remove() -> 8
pq.add(2, 5) // add all 8's unvisited neighbors 2 and 5
pq.remove() -> 7
pq.add(7) // add all 7's unvisited neighbors 7
...
Result:
6
7
7 7 6 score = 6

Notice that in the above example it stops expanding at 5 -> 4 since there is a better way to go.

Note:

  • Learn how to write the comparator.
  • Learn how to manage four-direction traversal.
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
public int maximumMinimumPath(int[][] A) {
if (A == null || A.length == 0 || A[0] == null || A[0].length == 0) {
return 0;
}
int row = A.length, col = A[0].length;
// Comparator
PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> { // max heap
return A[o2[0]][o2[1]] - A[o1[0]][o1[1]];
});
// Init
int[][] dir = new int[][] { {0, 1}, {0, -1}, {1, 0}, {-1, 0} };
boolean[][] visited = new boolean[row][col];
int score = Integer.MAX_VALUE; // must be updated if A is not empty
pq.add(new int[] { 0, 0 });
// PQ
while (pq.size() > 0) {
int[] p = pq.remove();
visited[p[0]][p[1]] = true;
score = Math.min(score, A[p[0]][p[1]]);
// check if reach the end point
if (p[0] == row - 1 && p[1] == col - 1) {
break;
}
// 4 directions
for (int[] d : dir) {
int r = p[0] + d[0];
int c = p[1] + d[1];
if (r >= 0 && r <= row - 1 && c >= 0 && c <= col - 1 && !visited[r][c]) {
pq.add(new int[] { r, c });
}
}
}
return score;
}

Time: $O(RC \log{(RC)})$
Space: $O(RC)$

Two-Direction Version

Given a matrix with r rows and c columns, find the maximum score of a path starting at [0, 0] and ending at [r - 1, c - 1]. The score of a path is the minimum value in that path. For example, the score of the path 8 → 4 → 5 → 9 is 4.

Don’t include the first or final entry. You can only move either down or right at any point in time.

Playground: https://leetcode.com/playground/sbkFjCbE

DP

Define: dp[i][j] is the max score from [0][0] to [i][j]
Recurrence: dp[i][j] = max( min(dp[i-1][j], grid[i][j]), min(dp[i][j-1]), grid[i][j] )

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// "static void main" must be defined in a public class.
public class Main {
public static void main(String[] args) {
int[][] grid1 = new int[][] { {5, 1}, {4, 5} }; // 4
int[][] grid2 = new int[][] { {5, 1, 7}, {4, 8, 5} }; // 4
int[][] grid3 = new int[][] { {1, 9, 9}, {9, 9, 9}, {9, 9, 9} }; // 1
int[][] grid4 = new int[][] { {10, 7, 3}, {12, 11, 9}, {1, 2, 8} }; // 8
int[][] grid5 = new int[][] { {20, 20, 3}, {20, 3, 20}, {3, 20, 20} }; // 3
System.out.println("grid1: Expected: 4, Actual: " + maxScore2D(grid1));
System.out.println("grid2: Expected: 4, Actual: " + maxScore2D(grid2));
System.out.println("grid3: Expected: 1, Actual: " + maxScore2D(grid3));
System.out.println("grid4: Expected: 8, Actual: " + maxScore2D(grid4));
System.out.println("grid5: Expected: 3, Actual: " + maxScore2D(grid5));
}

DP (2D)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// DP (2D)
private static int maxScore2D(int[][] grid) {
// Assume there is at least one element
int r = grid.length, c = grid[0].length;
int[][] dp = new int[r][c];
// Init
dp[0][0] = Integer.MAX_VALUE; // first entry is not considered
for (int i = 1; i < r; ++i) dp[i][0] = Math.min(dp[i - 1][0], grid[i][0]);
for (int j = 1; j < c; ++j) dp[0][j] = Math.min(dp[0][j - 1], grid[0][j]);
// DP
for (int i = 1; i < r; ++i) { // row by row
for (int j = 1; j < c; ++j) {
if (i == r - 1 && j == c - 1) {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); // last entry is not considered
} else {
int score1 = Math.min(dp[i][j - 1], grid[i][j]); // left
int score2 = Math.min(dp[i - 1][j], grid[i][j]); // up
dp[i][j] = Math.max(score1, score2);
}
}
}
return dp[r - 1][c - 1];
}

Time: $O(rc)$
Space: $O(rc)$

DP (1D)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// DP (One Row or Column)
private static int maxScore1D(int[][] grid) {
// Assume there is at least one element
int r = grid.length, c = grid[0].length;
int[] dp = new int[c];
// Init
dp[0] = Integer.MAX_VALUE; // first entry is not considered
for (int j = 1; j < c; ++j) dp[j] = Math.min(dp[j - 1], grid[0][j]);
// DP (for each row)
for (int i = 1; i < r; ++i) {
// update the first element in each row
dp[0] = Math.min(dp[0], grid[i][0]);
for (int j = 1; j < c; ++j) {
if (i == r - 1 && j == c - 1) {
dp[j] = Math.max(dp[j - 1], dp[j]); // last entry is not considered
} else {
int score1 = Math.min(dp[j - 1], grid[i][j]); // left dp[i][j-1]
int score2 = Math.min(dp[j], grid[i][j]); // up dp[i-1][j]
dp[j] = Math.max(score1, score2);
}
}
}
return dp[c - 1];
}

Time: $O(rc)$
Space: $O(r)$ or $O(c)$


Comment