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 }