Simple java solution with Rule 2 caveat!


  • 1

    Record the number of black pixels per row and col. Once you find a row and col that have N black pixels, you've found something that obeys rule1 and only need to check if it follows rule2, right?

    Not so fast! I discovered (the hard way) that while checking for rule2, all row/col combinations need to again follow rule1. If you fail test case 113, then you've been burned by this (implicit) requirement. Here's a full working solution:

        public int findBlackPixel(char[][] picture, int N) {
            if (picture == null || picture.length == 0 || picture[0].length == 0 || N < 0) return 0;
            
            int m = picture.length, n = picture[0].length;
            int[] rows = new int[m], cols = new int[n];
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (picture[i][j] == 'B') {
                        rows[i]++; cols[j]++;
                    }
                }
            }
            int res = 0;
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (picture[i][j] == 'B' && rows[i] == N && cols[j] == N) {
                        if (obeysRule2(picture, i, j, m, n, rows, cols)) {
                            res++;
                        }
                    }
                }
            }
            return res;
        }
        
        private boolean obeysRule2(char[][] picture, int index, int j, int m, int n, int[] rows, int[] cols) {
            for (int i = 0; i < m; i++) {
                if (i == index) continue;
                if (picture[i][j] == 'B') {
                	if (rows[index] != rows[i]) return false; // violates rule2
                	for (int col = 0; col < n; col++) {
                		if (picture[i][col] != picture[index][col]) return false; // violates rule1
                	}
                }
            }
            return true;
        }
    

  • 0
    L

    Easy to understand, but terrible efficiency


Log in to reply
 

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