Leetcode 531. Lonely Pixel I

Problem Description

This problem requires us to implement an algorithm that can determine the number of "lonely" black pixels in a given 2D array representing a picture of black and white pixels. Each 'B' character in the array represents a black pixel, while each 'W' character represents a white pixel.

A black pixel is considered "lonely" if it is the only black pixel in its entire row and column. In other words, none of the other elements in the same row or column as a "lonely" pixel are 'B'.

Here's an example to illustrate. If we are given the following 2D array as input:

1
2
3[['W', 'W', 'B'],
4 ['W', 'B', 'W'],
5 ['B', 'W', 'W']]

We should return 3 as output. This is because each 'B' in the array is "lonely". None of the 'B' pixels share a row or column with any other 'B' pixel.

Approach

The solution provided uses two separate passes through the 2D array:

1. The first pass counts how many 'B' pixels are in each row and column. These counts are stored in two separate arrays, rows and cols.

2. The second pass then checks each 'B' pixel to see if it is "lonely". If a 'B' pixel is at row i and column j, it will be lonely if and only if rows[i] and cols[j] are both 1. If this is the case, we increment a counter. The final value of this counter is our answer.

This can be considered a simple example of the "scanline" algorithm -- an algorithm commonly used in computer graphics to render polygons. It involves scanning the image row by row, while keeping some form of running total or count.

Python Solution

1
2python
3class Solution:
4  def findLonelyPixel(self, picture):
5    m, n = len(picture), len(picture[0])
6    ans = 0
7    rows = [0]*m  # rows[i] := # of Bs in row i
8    cols = [0]*n  # cols[j] := # of Bs in column j
9    
10    for i in range(m):
11      for j in range(n):
12        if picture[i][j] == 'B':
13          rows[i] += 1
14          cols[j] += 1
15
16    for i in range(m):
17      if rows[i] == 1:  # Only need to examine rows with exactly 1 'B'
18        for j in range(n):
19          if picture[i][j] == 'B':
20            if cols[j] == 1:
21              ans += 1
22            break
23    return ans

Java Solution

1
2java
3class Solution {
4  public int findLonelyPixel(char[][] picture) {
5    int m = picture.length, n = picture[0].length;
6    int ans = 0;
7    int[] rows = new int[m];  // rows[i] := # of Bs in row i
8    int[] cols = new int[n];  // cols[j] := # of Bs in column j
9
10    for (int i = 0; i < m; ++i)
11      for (int j = 0; j < n; ++j)
12        if (picture[i][j] == 'B') {
13          ++rows[i];
14          ++cols[j];
15        }
16
17    for (int i = 0; i < m; ++i)
18      if (rows[i] == 1)  // Only need to examine rows with exactly 1 'B'
19        for (int j = 0; j < n; ++j)
20          if (picture[i][j] == 'B') {
21            if (cols[j] == 1)
22              ++ans;
23            break;
24          }
25    return ans;
26  }
27}

JavaScript Solution

1
2javascript
3class Solution {
4  findLonelyPixel(picture) {
5    const m = picture.length, n = picture[0].length;
6    let ans = 0;
7    const rows = Array(m).fill(0);  // rows[i] := # of Bs in row i
8    const cols = Array(n).fill(0);  // cols[j] := # of Bs in column j
9
10    for (let i = 0; i < m; ++i)
11      for (let j = 0; j < n; ++j)
12        if (picture[i][j] == 'B') {
13          ++rows[i];
14          ++cols[j];
15        }
16
17    for (let i = 0; i < m; ++i)
18      if (rows[i] == 1)  // Only need to examine rows with exactly 1 'B'
19        for (let j = 0; j < n; ++j)
20          if (picture[i][j] == 'B') {
21            if (cols[j] == 1)
22              ++ans;
23            break;
24          }
25
26    return ans;
27  }
28}

C++ Solution

1
2cpp
3class Solution {
4 public:
5  int findLonelyPixel(vector<vector<char>>& picture) {
6    const int m = picture.size();
7    const int n = picture[0].size();
8    int ans = 0;
9    vector<int> rows(m);  // rows[i] := # of Bs in rows i
10    vector<int> cols(n);  // cols[i] := # of Bs in cols i
11
12    for (int i = 0; i < m; ++i)
13      for (int j = 0; j < n; ++j)
14        if (picture[i][j] == 'B') {
15          ++rows[i];
16          ++cols[j];
17        }
18
19    for (int i = 0; i < m; ++i)
20      if (rows[i] == 1)  // Only have to examine the rows when rows[i] == 1
21        for (int j = 0; j < n; ++j)
22          // After we met the 'B' in this rows, we break and search the next row
23          if (picture[i][j] == 'B') {
24            if (cols[j] == 1)
25              ++ans;
26            break;
27          }
28
29    return ans;
30  }
31};

C# Solution

1
2csharp
3public class Solution {
4    public int FindLonelyPixel(char[][] picture) {
5        int m = picture.Length, n = picture[0].Length;
6        int ans = 0;
7        int[] rows = new int[m];  // rows[i] := # of Bs in row i
8        int[] cols = new int[n];  // cols[j] := # of Bs in column j
9
10        for (int i = 0; i < m; ++i)
11            for (int j = 0; j < n; ++j)
12                if (picture[i][j] == 'B') {
13                    ++rows[i];
14                    ++cols[j];
15                }
16
17        for (int i = 0; i < m; ++i)
18            if (rows[i] == 1)  // Only need to examine rows with exactly 1 'B'
19                for (int j = 0; j < n; ++j)
20                    if (picture[i][j] == 'B') {
21                        if (cols[j] == 1)
22                            ++ans;
23                        break;
24                    }
25        return ans;
26    }
27}

The solutions listed use two separate passes over the 2D array representing the picture. This approach ensures that we only increment our answer counter when we come across a black pixel that is both the single black pixel in its row and in its column.

Although this algorithm involves scanning the entire 2D array twice, it still has a complexity of O(nm), where n is the number of rows and m is the number of columns of the picture. This is because each run through the array still requires visiting each element once - therefore, in the worst case scenario, the number of operations is proportional to the number of elements in the array.

So while this approach may not be the most efficient one available, it is relatively simple and straightforward, while still providing an acceptable time complexity for even larger inputs. Optimizations could certainly be made (for example, by finding a way to remember the locations of the black pixels in the first run and only revisiting these in the second run), but these can increase algorithm complexity, both in terms of implementation and understanding.

In a programming interview scenario, or when tasked with quickly delivering a solution that works correctly, the "two-pass" method used here is a solid choice. After that, if needed and when time permitted, it could always be optimized further for more efficiency. In some cases though, the increase in speed might not even be noticeably different to a user, considering the fast processing speeds of modern computers.

The principle of this approach can also be applied to similar problems where we need to tally up certain characteristics of a grid-based data structure.