Skip to content

3148. Maximum Difference Score in a Grid 👍

  • Time: $O(mn)$
  • Space: $O(mn)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
 public:
  int maxScore(vector<vector<int>>& grid) {
    constexpr int kMax = 200'000;
    int ans = -kMax;

    for (int i = 0; i < grid.size(); ++i)
      for (int j = 0; j < grid[0].size(); ++j) {
        const int prevMin = min(i > 0 ? grid[i - 1][j] : kMax,  //
                                j > 0 ? grid[i][j - 1] : kMax);
        ans = max(ans, grid[i][j] - prevMin);
        grid[i][j] = min(grid[i][j], prevMin);
      }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
  public int maxScore(List<List<Integer>> grid) {
    final int kMax = 200_000;
    int ans = -kMax;

    for (int i = 0; i < grid.size(); ++i)
      for (int j = 0; j < grid.get(0).size(); ++j) {
        final int prevMin = Math.min(i > 0 ? grid.get(i - 1).get(j) : kMax, //
                                     j > 0 ? grid.get(i).get(j - 1) : kMax);
        ans = Math.max(ans, grid.get(i).get(j) - prevMin);
        if (prevMin < grid.get(i).get(j))
          grid.get(i).set(j, prevMin);
      }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
  def maxScore(self, grid: list[list[int]]) -> int:
    kMax = 200000
    ans = -kMax

    for i, row in enumerate(grid):
      for j, num in enumerate(row):
        prevMin = min(grid[i - 1][j] if i > 0 else kMax,
                      grid[i][j - 1] if j > 0 else kMax)
        ans = max(ans, num - prevMin)
        grid[i][j] = min(num, prevMin)

    return ans