Algorithm: Leetcode Contest 387

3070. Count Submatrices with Top-Left Element and Sum Less Than k

Solution

class Solution {
    public int countSubmatrices(int[][] grid, int k) {
        
        // fill the first column
        for(int i = 1; i < grid.length; i++) {
            grid[i][0] = grid[i][0] + grid[i - 1][0]; 
        }
        // fill the first row
        for(int i = 1; i < grid[0].length; i++) {
            grid[0][i] = grid[0][i] + grid[0][i - 1]; 
        }
        // fill other cells, depends on its above and left metrics
        
        for(int i = 1; i < grid.length; i++) {
            for(int j = 1; j < grid[0].length; j++) {
                grid[i][j] = grid[i-1][j] + grid[i][j-1] - grid[i-1][j-1] + grid[i][j];
            }
        }
        // re-check the sum metrics, count the number 
        
        int res = 0;
        
        for(int i = 0; i < grid.length; i++) {
            for(int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] <= k) {
                    res++;
                }
            }
        }
        
        return res;
    }
}

Retro

1. the calculation of each cell really need some careful thinking

3071. Minimum Operations to Write the Letter Y on a Grid

Solution

class Solution {
    public int minimumOperationsToWriteY(int[][] grid) {
        Set<int[]> pairs = new HashSet<>(){
            {
                add(new int[]{0, 1});
                add(new int[]{0, 2});
                add(new int[]{1, 0});
                add(new int[]{1, 2});
                add(new int[]{2, 0});
                add(new int[]{2, 1});
            }
        };
        
        int min = Integer.MAX_VALUE;
        int temp = 0;
        for(int[] pair: pairs) {
            temp = getOps(pair, grid);
            if (temp < min) {
                min = temp;
            }
        }
        
        return min;
    }
    
    private int getOps(int[] pair, int[][] grid) {
        int ops = 0;
        for(int i = 0; i < grid.length; i++) {
            for(int j = 0; j < grid[0].length; j++) {
                if (isY(i, j, grid.length)) {
                    if (grid[i][j] != pair[0]) {
                        ops++;
                    }
                } else {
                    if (grid[i][j] != pair[1]) {
                        ops++;
                    }
                }
            }
        }
        
        return ops;
    }
    
    private boolean isY(int row, int col, int n) {
        int middle = (n - 1) / 2;
        
        if (row < middle) {
            return col == row || col == n - 1 - row;
        } else {
            return col == middle;
        }
    }
}

Retro

Another solution of “min/max” problem: brute force