Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/531.html

531. Lonely Pixel I

Level

Medium

Description

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

Solution

For each row, store the column indices in the row where the pixels are black. For each column, store the row indices in the column where the pixels are black.

Loop over each row. If a row contains exactly one pixel that is black, then obtain the column index of the black pixel. If the column contains exactly one pixel that is black, then the pixel is a lonely pixel. Count the number of lonely pixels and return.

  • class Solution {
    public int findLonelyPixel(char[][] picture) {
        if (picture == null || picture.length == 0 || picture[0].length == 0)
            return 0;
        Map<Integer, List<Integer>> rowMap = new HashMap<Integer, List<Integer>>();
        Map<Integer, List<Integer>> columnMap = new HashMap<Integer, List<Integer>>();
        int rows = picture.length, columns = picture[0].length;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                if (picture[i][j] == 'B') {
                    List<Integer> rowList = rowMap.getOrDefault(i, new ArrayList<Integer>());
                    List<Integer> columnList = columnMap.getOrDefault(j, new ArrayList<Integer>());
                    rowList.add(j);
                    columnList.add(i);
                    rowMap.put(i, rowList);
                    columnMap.put(j, columnList);
                }
            }
        }
        int lonelyPixels = 0;
        for (int i = 0; i < rows; i++) {
            List<Integer> rowList = rowMap.getOrDefault(i, new ArrayList<Integer>());
            if (rowList.size() == 1) {
                int column = rowList.get(0);
                List<Integer> columnList = columnMap.getOrDefault(column, new ArrayList<Integer>());
                if (columnList.size() == 1)
                    lonelyPixels++;
            }
        }
        return lonelyPixels;
    }
}

  • Todo

  • class Solution:
    def findLonelyPixel(self, picture: List[List[str]]) -> int:
        m, n = len(picture), len(picture[0])
        rows, cols = [0] * m, [0] * n
        for i in range(m):
            for j in range(n):
                if picture[i][j] == 'B':
                    rows[i] += 1
                    cols[j] += 1
        res = 0
        for i in range(m):
            if rows[i] == 1:
                for j in range(n):
                    if picture[i][j] == 'B' and cols[j] == 1:
                        res += 1
                        break
        return res

############

from collections import defaultdict

class Solution(object):
  
  def findLonelyPixel(self, picture):

      col = defaultdict(int)
      row = defaultdict(int)

      for i, r in enumerate(picture):
        for j, pixel in enumerate(r):
          if pixel == "B":
            row[i] += 1
            col[j] += 1

      return sum(
          1 for i, r in enumerate(picture) 
          for j, pixel in enumerate(r) 
          if col[j] == row[i] == 1 and pixel == 'B'
      )

All Problems

All Solutions