JAVA O(N*M) time O(M) space solution


  • 0
    H

    public class Solution {

    public int findLonelyPixel(char[][] picture) {
        
        //Algo thinking: only examin 'B'
        //      (1) go throuhg row & col, make decision if this 'B' is lonly
        //      (2) add this col to jumpSet, so we are not gonna consider it anymore
        
        // time = O(N*M), space = O(M)
        
        int n = picture.length;
        int m = picture[0].length;
        
        Set<Integer> jumpCol = new HashSet<>();
        int count = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (picture[i][j] == 'W' || jumpCol.contains(j)) continue;
                if (isLonly(picture, i, j, n, m)) count++;
                jumpCol.add(j);
                break;
            }
        }
        
        return count;
    }
    
    private boolean isLonly(char[][] picture, int x, int y, int n, int m) {
        
        for (int i = 0; i < n; i++) {
            if (picture[i][y] == 'B' && i != x) return false;
        }
        
        for (int j = 0; j < m; j++) {
            if (picture[x][j] == 'B' && j != y) return false;
        }
        
        return true;
    }
    

    }


Log in to reply
 

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