Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/533.html
533. Lonely Pixel II
Level
Medium
Description
Given a picture consisting of black and white pixels, and a positive integer N, find the number of black pixels located at some specific row R and column C that align with all the following rules:
- Row R and column C both contain exactly N black pixels.
- For all rows that have a black pixel at column C, they should be exactly the same as row R.
The picture is represented by a 2D char array consisting of ‘B’ and ‘W’, which means black and white pixels respectively.
Example:
Input:
[['W', 'B', 'W', 'B', 'B', 'W'],
['W', 'B', 'W', 'B', 'B', 'W'],
['W', 'B', 'W', 'B', 'B', 'W'],
['W', 'W', 'B', 'W', 'B', 'W']]
N = 3
Output: 6
Explanation: All the bold 'B' are the black pixels we need (all 'B's at column 1 and 3).
0 1 2 3 4 5 column index
0 [['W', 'B', 'W', 'B', 'B', 'W'],
1 ['W', 'B', 'W', 'B', 'B', 'W'],
2 ['W', 'B', 'W', 'B', 'B', 'W'],
3 ['W', 'W', 'B', 'W', 'B', 'W']]
row index
Take 'B' at row R = 0 and column C = 1 as an example:
Rule 1, row R = 0 and column C = 1 both have exactly N = 3 black pixels.
Rule 2, the rows have black pixel at column C = 1 are row 0, row 1 and row 2. They are exactly the same as row R = 0.
Note:
- The range of width and height of the input 2D array is [1,200].
Solution
Since this problem requires the rows should have exactly the same columns that have black pixels, map each row as a string to the count of the row, which means the number of rows that have this content.
Only consider the rows that have counts exactly N
. For each such row, the row should contain exactly N
black pixels, and for each position that is a black pixel, count the number of black pixels in the column. If there are exactly N
black pixels in the column, then add N
to the result. Finally, return the result.
-
class Solution { public int findBlackPixel(char[][] picture, int N) { if (picture == null || picture.length == 0 || picture[0].length == 0) return 0; Map<String, Integer> rowCountMap = new HashMap<String, Integer>(); int rows = picture.length, columns = picture[0].length; for (int i = 0; i < rows; i++) { String row = new String(picture[i]); int count = rowCountMap.getOrDefault(row, 0); count++; rowCountMap.put(row, count); } int pixels = 0; Set<String> rowSet = rowCountMap.keySet(); for (String rowStr : rowSet) { int count = rowCountMap.getOrDefault(rowStr, 0); if (count != N) continue; List<Integer> columnsList = new ArrayList<Integer>(); for (int column = 0; column < columns; column++) { if (rowStr.charAt(column) == 'B') columnsList.add(column); } if (columnsList.size() != N) continue; for (int column : columnsList) { int columnCount = 0; for (int row = 0; row < rows; row++) { if (picture[row][column] == 'B') columnCount++; } if (columnCount == N) pixels += N; } } return pixels; } }
-
class Solution: def findBlackPixel(self, picture: List[List[str]], target: int) -> int: m, n = len(picture), len(picture[0]) rows = [0] * m cols = defaultdict(list) for i in range(m): for j in range(n): if picture[i][j] == 'B': rows[i] += 1 cols[j].append(i) t = [[False] * m for _ in range(m)] for i in range(m): for k in range(i, m): if i == k: t[i][k] = True else: t[i][k] = all([picture[i][j] == picture[k][j] for j in range(n)]) t[k][i] = t[i][k] res = 0 for i in range(m): if rows[i] == target: for j in range(n): if len(cols[j]) == target and all([t[i][k] for k in cols[j]]): res += 1 return res ############ class Solution(object): def findBlackPixel(self, picture, N): """ :type picture: List[List[str]] :type N: int :rtype: int """ rowSign = {} ans = 0 col = {} row = {} for i in range(len(picture)): sign = "".join(picture[i]) rowSign[sign] = rowSign.get(sign, 0) + 1 if sign.count("B") == N else 0 for j in range(len(picture[0])): if picture[i][j] == "B": col[j] = col.get(j, 0) + 1 for key in rowSign: if rowSign[key] == N: for j in range(len(key)): if key[j] == "B" and col.get(j, 0) == N: ans += N return ans
-
class Solution { public: int findBlackPixel(vector<vector<char>>& picture, int target) { int m = picture.size(), n = picture[0].size(); vector<int> rows(m); unordered_map<int, vector<int>> cols; for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { if (picture[i][j] == 'B') { ++rows[i]; cols[j].push_back(i); } } } vector<vector<bool>> t(m, vector<bool>(m, false)); for (int i = 0; i < m; ++i) { for (int k = i; k < m; ++k) { t[i][k] = i == k || all(picture[i], picture[k]); t[k][i] = t[i][k]; } } int res = 0; for (int i = 0; i < m; ++i) { if (rows[i] == target) { for (int j = 0; j < n; ++j) { if (cols[j].size() == target) { bool check = true; for (int k : cols[j]) check = check && t[i][k]; if (check) ++res; } } } } return res; } bool all(vector<char>& row1, vector<char>& row2) { int n = row1.size(); for (int j = 0; j < n; ++j) if (row1[j] != row2[j]) return false; return true; } };
-
func findBlackPixel(picture [][]byte, target int) int { m, n := len(picture), len(picture[0]) rows := make([]int, m) cols := make(map[int][]int) for i := 0; i < m; i++ { for j := 0; j < n; j++ { if picture[i][j] == 'B' { rows[i]++ cols[j] = append(cols[j], i) } } } t := make([][]bool, m) for i := 0; i < m; i++ { t[i] = make([]bool, m) } for i := 0; i < m; i++ { for k := i; k < m; k++ { if i == k { t[i][k] = true } else { t[i][k] = all(picture[i], picture[k]) } t[k][i] = t[i][k] } } res := 0 for i := 0; i < m; i++ { if rows[i] == target { for j := 0; j < n; j++ { col, ok := cols[j] if ok && len(col) == target { check := true for _, k := range col { check = check && t[i][k] } if check { res++ } } } } } return res } func all(row1, row2 []byte) bool { n := len(row1) for i := 0; i < n; i++ { if row1[i] != row2[i] { return false } } return true }