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)$