Maximum Trailing Zeros in a Cornered Path LeetCode solution in Java

1
class Solution {
2
  public int maxTrailingZeros(int[][] grid) {
3
    int m = grid.length;
4
    int n = grid[0].length;
5
    int[][] two = new int[m][n];
6
    int[][] five = new int[m][n];
7
    for (int i = 0; i < m; ++i) {
8
      for (int j = 0; j < n; ++j) {
9
        two[i][j] = getFactorNum(grid[i][j], 2);
10
        five[i][j] = getFactorNum(grid[i][j], 5);
11
      }
12
    }
13

14
    int[][] left2 = new int[m][n];
15
    int[][] left5 = new int[m][n];
16
    for (int i = 0; i < m; ++i) {
17
      int sum2 = 0;
18
      int sum5 = 0;
19
      for (int j = 0; j < n; ++j) {
20
        sum2 += two[i][j];
21
        sum5 += five[i][j];
22
        left2[i][j] = sum2;
23
        left5[i][j] = sum5;
24
      }
25
    }
26

27
    int[][] right2 = new int[m][n];
28
    int[][] right5 = new int[m][n];
29
    for (int i = 0; i < m; ++i) {
30
      int sum2 = 0;
31
      int sum5 = 0;
32
      for (int j = n - 1; j >= 0; --j) {
33
        sum2 += two[i][j];
34
        sum5 += five[i][j];
35
        right2[i][j] = sum2;
36
        right5[i][j] = sum5;
37
      }
38
    }
39

40
    int[][] up2 = new int[m][n];
41
    int[][] up5 = new int[m][n];
42
    for (int j = 0; j < n; ++j) {
43
      int sum2 = 0;
44
      int sum5 = 0;
45
      for (int i = 0; i < m; ++i) {
46
        sum2 += two[i][j];
47
        sum5 += five[i][j];
48
        up2[i][j] = sum2;
49
        up5[i][j] = sum5;
50
      }
51
    }
52

53
    int[][] down2 = new int[m][n];
54
    int[][] down5 = new int[m][n];
55
    for (int j = 0; j < n; ++j) {
56
      int sum2 = 0;
57
      int sum5 = 0;
58
      for (int i = m - 1; i >= 0; --i) {
59
        sum2 += two[i][j];
60
        sum5 += five[i][j];
61
        down2[i][j] = sum2;
62
        down5[i][j] = sum5;
63
      }
64
    }
65

66
    int res = 0;
67
    for (int i = 0; i < m; ++i) {
68
      for (int j = 0; j < n; ++j) {
69
        // left-up
70
        if (i != 0 || j != 0) {
71
          int cur =
72
              Math.min(left2[i][j] + up2[i][j] - two[i][j], left5[i][j] + up5[i][j] - five[i][j]);
73
          res = Math.max(res, cur);
74
        }
75

76
        // up-right
77
        if (i != 0 || j != n - 1) {
78
          int cur =
79
              Math.min(right2[i][j] + up2[i][j] - two[i][j], right5[i][j] + up5[i][j] - five[i][j]);
80
          res = Math.max(res, cur);
81
        }
82

83
        // right-down
84
        if (i != m - 1 || j != n - 1) {
85
          int cur =
86
              Math.min(
87
                  right2[i][j] + down2[i][j] - two[i][j], right5[i][j] + down5[i][j] - five[i][j]);
88
          res = Math.max(res, cur);
89
        }
90

91
        // down-left
92
        if (i != m - 1 || j != 0) {
93
          int cur =
94
              Math.min(
95
                  left2[i][j] + down2[i][j] - two[i][j], left5[i][j] + down5[i][j] - five[i][j]);
96
          res = Math.max(res, cur);
97
        }
98
      }
99
    }
100
    return res;
101
  }
102

103
  private int getFactorNum(int input, int factor) {
104
    int res = 0;
105
    while (input != 0 && input % factor == 0) {
106
      ++res;
107
      input /= factor;
108
    }
109
    return res;
110
  }
111
}