LeetCode 531 - Lonely Pixel I

https://www.nowtoshare.com/en/Article/Index/20483

Given a picture consisting of black and white pixels, find the number of black lonely pixels.

The picture is represented by a 2D char array consisting of 'B' and 'W', which means black and white pixels respectively.

A black lonely pixel is character 'B' that located at a specific position where the same row and same column don't have any other black pixels.

Example:

Input: 
[['W', 'W', 'B'],
 ['W', 'B', 'W'],
 ['B', 'W', 'W']]

Output: 3
Explanation: All the three 'B's are black lonely pixels.

Note:

1. The range of width and height of the input 2D array is [1,500].

X.

O(nm) Time, O(1) Space Solution:

The hack here is to mutate the first row and first column of the given matrix to store the counts of items in the row/column.

W + 1 = X --> one item in the row/column
B + 1 = C --> one item in the row/column, and the first row is the black pixel
W + 2 = Y --> two items in the row/column
W - 1 = V --> this prevents wrap-around past W if there are more than 255 black pixels in a row/column

The same idea as "Design Tic-Tac-Toe".

public int findLonelyPixel(char[][] picture) {
    int n = picture.length, m = picture[0].length;
    
    int firstRowCount = 0;
    for (int i=0;i<n;i++) 
        for (int j=0;j<m;j++) 
            if (picture[i][j] == 'B') {   
                if (picture[0][j] < 'Y' && picture[0][j] != 'V') picture[0][j]++;
                if (i == 0) firstRowCount++;
                else if (picture[i][0] < 'Y' && picture[i][0] != 'V') picture[i][0]++;
            }

    int count = 0;
    for (int i=0;i<n;i++) 
        for (int j=0;j<m;j++) 
            if (picture[i][j] < 'W' && (picture[0][j] == 'C' || picture[0][j] == 'X')) { 
                if (i == 0) count += firstRowCount == 1 ? 1 : 0;
                else if (picture[i][0] == 'C' || picture[i][0] == 'X') count++;
            }
                
    return count;
}

X. One pass solution
https://blog.csdn.net/lcharon/article/details/60597972

扫描，对于B的点，行计数+1，列计数如果为0，就记录行数，如果大于0，就取负。
结果对列计数为正的进行统计，计算其中行计数为1的点即可(来自某个不愿透露姓名的展的教学)

    int findLonelyPixel(vector<vector<char>>& picture) {

        vector<int> row(picture.size(), 0), col(picture[0].size(), 0);

        int result = 0;

        for (int i = 0; i < picture.size(); ++i){

            for (int j = 0; j < picture[0].size(); ++j){

                if (picture[i][j] == 'B'){

                    ++row[i];

                    if (col[j] == 0){

                        col[j] = i + 1;

                    }

                    else{

                        col[j] = -1;

                    }

                }

            }

        }

        for (int i = 0; i < col.size(); ++i){

            if (col[i] > 0){

                if (row[col[i] - 1] == 1){

                    ++result;

                }

            }

        }

        return result;   

    }

https://www.godwinls.com/archives/119
public int findLonelyPixel(char[][] picture) {
    int m = picture.length, n = picture[0].length;
    int[] row = new int[m];
    int[] col = new int[n];
    int res = 0;
    for(int i = 0; i < m; i ++){
        for(int j = 0; j < n; j ++){
            if(picture[i][j] == 'B'){
                col[j]++;
                if(row[i] == 0) row[i] = j + 1;// give a offset so we can deal with the j=0 situation
                                               // you can change to j+ any offset.
                else row[i] = -1;
            }
        }
    }
    for(int r : row){
        if(r > 0 && col[r - 1] == 1) res++; // remove the offset
    }
 
    return res;
}

X.
https://www.godwinls.com/archives/119
https://discuss.leetcode.com/topic/81680/java-o-nm-time-with-o-n-m-space-and-o-1-space-solutions
first traverse record how many ‘B’ in each col and each row, second traverse when we find a ‘B’ check whether row[i]==1 && col[j]==1.
Time complexity O(mn), Space complexity O(m+n);

O(nm) Time, O(n+m) Space Solution:

public int findLonelyPixel(char[][] picture) {
    int n = picture.length, m = picture[0].length;
    
    int[] rowCount = new int[n], colCount = new int[m];
    for (int i=0;i<n;i++) 
        for (int j=0;j<m;j++) 
            if (picture[i][j] == 'B') { rowCount[i]++; colCount[j]++; }

    int count = 0;
    for (int i=0;i<n;i++) 
        for (int j=0;j<m;j++) 
            if (picture[i][j] == 'B' && rowCount[i] == 1 && colCount[j] == 1) count++;
                
    return count;
}

X.
O(mn) time, O(m)
we can also use a min(m,n) space just record the col ‘B’s/row ‘B’s, then during the second traverse for each row/col, use two variables: count and pos, when we find a ‘B’, update count and pos, then after we finish this row/col, we check whether count==1 && col[last]/row[last]==1, if so, result++; this reduce our space complexity to min(m,n)+2, which is O(min(m,n));
https://discuss.leetcode.com/topic/81703/java-o-mn-time-o-m-space-28ms

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 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;
    }

X. https://eugenejw.github.io/2017/07/leetcode-531

    def findLonelyPixel(self, picture):
        """
        :type picture: List[List[str]]
        :rtype: int
        """
        ret = 0
        row = [0] * len(picture[0])
        col = [0] * len(picture)
        for i in xrange(len(picture)):
            for j in xrange(len(picture[0])):
                if picture[i][j] == 'B':
                    row[j] += 1
                    col[i] += 1
                    
        for i in xrange(len(picture)):
            if col[i] == 1:
                for j in xrange(len(picture[0])):
                    if picture[i][j] == 'B':
                        if row[j] == 1:
                            ret += 1
        return ret

https://www.jianshu.com/p/1a55970e2ebc

    public int findLonelyPixel(char[][] picture) {
        int n = picture.length, m = picture[0].length;

        int[] rowCount = new int[n], colCount = new int[m];
        for (int i=0;i<n;i++) {
            for (int j=0;j<m;j++) { 
                if (picture[i][j] == 'B') { 
                    rowCount[i]++; colCount[j]++; 
                }
            }
        }

        int count = 0;
        for (int i=0;i<n;i++) {
            for (int j=0;j<m;j++) { 
                if (picture[i][j] == 'B' && rowCount[i] == 1 && colCount[j] == 1) count++;
            }
        }

        return count;
    }

http://blog.csdn.net/qq_27262609/article/details/60571980

1.     public int findLonelyPixel(char[][] picture) {  
2.         int count=0;  
3.         HashMap<Integer,Integer> row =new HashMap<>();  
4.         HashMap<Integer,Integer> column =new HashMap<>();  
5.         for(int i=0;i<picture.length;i++){  
6.             for(int j=0;j<picture[0].length;j++){  
7.                 if(picture[i][j]=='B'){  
8.                     if(row.containsKey(i)){  
9.                         row.put(i,row.get(i)+1);  
10.                     }else{  
11.                         row.put(i,1);  
12.                     }  
13.                     if(column.containsKey(j)){  
14.                         column.put(j,column.get(j)+1);  
15.                     }else{  
16.                         column.put(j,1);   
17.                     }  
18.                 }  
19.             }  
20.         }  
21.         for(int i=0;i<picture.length;i++){  
22.             for(int j=0;j<picture[0].length;j++){  
23.                 if(picture[i][j]=='B'&&row.containsKey(i)&&row.get(i)==1&&column.containsKey(j)&&column.get(j)==1){  
24.                     count++;  
25.                 }  
26.             }  
27.         }  
28.         return count;  
29.     }  

X. DFS for fun
https://www.cnblogs.com/lightwindy/p/9666798.html

public int findLonelyPixel(char[][] picture) {
    int numLone = 0;
    for (int row = 0; row < picture.length; row++) {
        for (int col = 0; col < picture[row].length; col++) {
            if (picture[row][col] == 'W') {
                continue;
            }
            if (dfs(picture, row - 1, col, new int[] {-1, 0}) && dfs(picture, row + 1, col, new int[] {1, 0})
             && dfs(picture, row, col - 1, new int[] {0, -1}) && dfs(picture, row, col + 1, new int[] {0, 1})) {
                numLone++;
            }
        }
    }
    return numLone;
}

// use dfs to find if current pixel is lonely
private boolean dfs(char[][] picture, int row, int col, int[] increase) {
    // base case
    if (row < 0 || row >= picture.length || col < 0 || col >= picture[0].length) {
        return true;
    } else if (picture[row][col] == 'B') {
        return false;
    }
    // recursion
    return dfs(picture, row + increase[0], col + increase[1], increase);
}