531 Lonely Pixel I

531. Lonely Pixel I

1. Question

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. 1.
    The range of width and height of the input 2D array is [1,500].

2. Implementation

(1) DFS
public class Solution {
public int findLonelyPixel(char[][] picture) {
if (picture == null || picture.length == 0) {
return 0;
}
int m = picture.length, n = picture[0].length;
int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int lonelyPixel = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (picture[i][j] == 'B') {
int count = 0;
for (int[] direction : directions) {
if (!findLonelyPixelByDFS(i, j, picture, direction)) {
break;
}
else {
++count;
}
}
if (count == 4) {
++lonelyPixel;
}
}
}
}
return lonelyPixel;
}
public boolean findLonelyPixelByDFS(int row, int col, char[][] picture, int[] direction) {
row += direction[0];
col += direction[1];
if (row < 0 || row >= picture.length || col < 0 || col >= picture[0].length) {
return true;
}
if (picture[row][col] == 'B') {
return false;
}
return findLonelyPixelByDFS(row, col, picture, direction);
}
}

3. Time & Space Complexity

DFS: 时间复杂度O(mn * Max(m, n)), m为picture的行数, n为picture的列数,分析:最坏的情况是每个pixel都是black,然后我们通过dfs从up, down, left, down四个方向检查该pixel是否lonely,这个过程需要时间O(max(m, n)), 空间复杂度: O(max(m, n))。