Java O(mn) time, O(m) space. 28ms


  • 7

    thought is very simple, we can easily count how many times B occurs in each row. But how can we know if this col has existing B?
    for example, input is
    W B B B
    B W W W
    W W W B
    W W W B
    we can maintain an array calls colArray[], which is used to record how many times the B occurs in each column. Then solution is simple

    public class Solution {
        public int findLonelyPixel(char[][] picture) {
            if (picture == null || picture.length == 0 || picture[0].length == 0) return 0;
    
            int[] colArray = new int[picture[0].length];
            for (int i = 0; i < picture.length; i++) {
                for (int j = 0; j < picture[0].length; j++) {
                    if (picture[i][j] == 'B') colArray[j]++;
                }
            }
    
            int ret = 0;
            for (int i = 0; i < picture.length; i++) {
                int count = 0, pos = 0;
                for (int j = 0; j < picture[0].length; j++) {
                    if (picture[i][j] == 'B') {
                        count++;
                        pos = j;
                    }
                }
                if (count == 1 && colArray[pos] == 1) ret++;
            }
            return ret;
        }
    }
    

  • 1
    C

    @lusoul Nice, saves from an extra array to store how many black pixels are in each row, used in the other O(m+n) solutions.


  • 0

    @chokobo Yes, my first attempt is directly use an colArray[] to record if B occurs in previous row, but I found it doesn't work. Then try to use total amount it occurs, then works.


Log in to reply
 

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