[Java/C++] Clean Code - 7 lines


  • 3
    1. this problem require us first to identify the possible rectangles, then check their 4 corners for validity into count.
    2. for each non-0 cell (i0,j0) in the grid, we can use (i0,j0) as the top-left corner,
    3. then for each cell (i,j) where i > i0 & j > j0 in the bottom-right region of (i,j), as indicated in the graph below, we can use (i,j) as the bottom-right conner.
    4. to save time, if (i,j) is 0, there is no need to do the step 2;

    Java

    class Solution {
        public int countCornerRectangles(int[][] grid) {
            int m = grid.length, n = grid[0].length, cnts = 0;
            for (int i0 = 0; i0 < m; i0++)
                for (int j0 = 0; j0 < n; j0++)
                    for (int i = i0 + 1; i < m && grid[i0][j0] != 0; i++)
                        for (int j = j0 + 1; j < n && grid[i][j0] != 0; j++)
                            cnts += grid[i][j] * grid[i0][j];
            return cnts;
        }
    }
    

    C++

    class Solution {
    public:
        int countCornerRectangles(vector<vector<int>>& grid) {
            int m = grid.size(), n = grid[0].size(), cnt = 0;
            for (int i0 = 0; i0 < m; i0++)
                for (int j0 = 0; j0 < n; j0++)
                    for (int i = i0 + 1; i < m && grid[i0][j0]; i++)
                        for (int j = j0 + 1; j < n && grid[i][j0]; j++)
                            cnt += grid[i][j] && grid[i0][j];
            return cnt;
        }
    };
    

  • 0
    T

    @alexander said in [Java/C++] Clean Code - 7 lines:

    grid[i][j0]

    can you please explain in 4th for loop, whats the reasonf or grid[i][j0] ? and similary why we need grid[i0][j] in count


  • 0

    @terminator123456 for (int j = j0 + 1; j < n && grid[i][j0]; j++) is to make sure the loop does not execute when grid[i][j0] == 0 (which is the top-right corner).

    cnt += grid[i][j] && grid[i0][j]; is the same as
    cnt += grid[i][j] && grid[i0][j] ? 1 : 0;


  • 1
    T

    thanks Alexander


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.