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


  • 23

    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!


  • 9
    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?


  • 1
    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.


  • 0
    D

    @Avidiax Thinking maybe 'D' is enough to judge, instead of 'V'


  • 1
    F

    Add some conditions to avoid unnecessary check.

    class Solution {
        public int findLonelyPixel(char[][] picture) {
            int m = picture.length, n = picture[0].length;
            int[] row = new int[m];
            int[] col = new int[n];
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (picture[i][j] == 'B') {
                        row[i]++;
                        col[j]++;
                    }
                }
            }
            int res = 0;
            for (int i = 0; i < m; i++) {
                // Only if the current row has only 1 black, we will step into it.
                if (row[i] != 1) {
                    continue;
                }
                for (int j = 0; j < n; j++) {
                    // Since this row only has 1 black, after we met it, we can break and search next row.
                    if (picture[i][j] == 'B') {
                        if (col[j] == 1) {
                            res++;
                        }
                        break;
                    }
                }
            }
            return res;
        }
    }
    

Log in to reply
 

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