Java only one pass of O(mn) solution, 2 arrays of O(m+n) space.


  • 0

    Very similar to DP approach, we store the "current" results in a row-length array after scanning a row.
    For example,
    first row : WWBWW
    we have [0,0,1,0,0] since 3rd column has only one "B"
    2nd row : BWWWW
    we have [1,0,1,0,0] since 1st column has only one "B"
    3rd row : WWWBB
    we have [1,0,1,0,0] no chages since the number of "B" in this row is more than 1
    4th row : WWWWB
    we have [1,0,1,0,0] no chages since the number of "B" in the last column is more than 1
    5th row : BWWWB
    we have [0,0,1,0,0] since the number of "B" in the first column is more than 1
    So, the final result is the total of this array.
    In fact, we can calculate the total when adding or removing a number from this array.

    public class Solution {
        public int findLonelyPixel(char[][] picture) {
            int ret=0;
            int[] rowHasOne = new int[picture.length];
            int[] colCount = new int[picture[0].length];
            for (int i=0; i< picture.length; i++){
                int rowCount = 0, lastBlk = -1;
                for (int j=0; j< picture[0].length; j++){
                    if (picture[i][j]=='B') {
                        rowCount++;
                        lastBlk = j;
                        if (++colCount[j] > 1) {
                            ret -= rowHasOne[j];
                            rowHasOne[j] = 0;
                        }
                    }
                    if (j==picture[0].length-1 && rowCount==1 && colCount[lastBlk]==1){
                        rowHasOne[lastBlk]++;
                        ret++;
                    }
                }
            }
            return ret;
        }
    }
    

Log in to reply
 

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