Java O(nm) time with O(n+m) Space and O(1) Space Solutions


  • 18

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

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

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

  • 2
    K

    Nice and clean code. But for the O(1) solution, there is a corner case where there are exactly 22 B's in one row, in which the first column will become 'X'.

    Here's the input:
    ["WWWWWWWWWWWWWWWWWWWWWWWWW","BWBBBBBBBBBBBBBBBBBBBBBWW"]

    Answer: 21
    Expected: 0


  • 1

    @kaiwen789 Hey, thanks for pointing this corner case out! I have updated solution accordingly.


  • 0
    K

    @compton_scatter Nice work!


  • 0

    Great O(1) solution. I think this question is very similar to set matrix zeros


  • 0
    S

    Why we use 'Y', 'V', 'C', anyone knows? Thanks!


  • 8
    A

    @SuperHero007

    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


  • 0
    Y

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


  • 0
    J

    how to solve this problem with DFS?


  • 0
    G

    @JagdishHiremath I have the same idea as you: how to use DFS. But my code is very ugly. Some suggestion please, thx.

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

    ''


  • 0
    D
    This post is deleted!

  • 0
    F

    Here is my one pass code, using hashmap. The idea is the same

        public int findLonelyPixel(char[][] picture) {
            HashMap<Integer,Integer> row2Cnt = new HashMap<>();
            HashMap<Integer,Integer> col2Cnt = new HashMap<>();
            int cnt = 0;
    
            for (int row = 0; row < picture.length; row++) {
                for (int col = 0; col < picture[0].length; col++) {
                    if (picture[row][col] == 'W')
                        continue;
    
                    int rowCnt = row2Cnt.getOrDefault(row,0);
                    int colCnt = row2Cnt.getOrDefault(row,0);
    
                    if (rowCnt == 0 && colCnt == 0) {
                        cnt++;
                    }
    
                    else {
                        if (rowCnt == 1)
                            cnt--;
                        if (colCnt == 1)
                            cnt--;
                    }
    
                    row2Cnt.put(row,rowCnt + 1);
                    col2Cnt.put(col,colCnt + 1);
                }
            }
    
            return cnt;
        }
    
    

  • 0
    F

    @compton_scatter You only need to return the
    Math.min(countRow1, countCol1).
    countRow1 = the number of 1's in rowCount array
    countCol1 = the number of 1's in colCount array

    In this step, it has O(m + n) time rather than another O(nm) to loop through the entire picture array.


Log in to reply
 

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