533. Lonely Pixel II

Problem Description

In this problem, you are given a two-dimensional grid named picture, represented by an m x n array where each element is either a black pixel ('B') or a white pixel ('W'). Additionally, you are given an integer target. Your task is to return the number of black pixels that are considered "lonely".

A black pixel is defined as "lonely" if it satisfies two conditions:

1. It is located in a row and a column that both contain exactly target number of black pixels.
2. Every other row that has a black pixel in the same column as this one should be identical to the row containing the lonely black pixel.

Intuition

To find the lonely black pixels, we need to:

1. Count the number of black pixels in each row and column.
2. Check if rows with a black pixel in the same column are identical.

The solution follows these steps:

1. Initialize two counters: one for rows and one for columns. For rows, use an array rows with one entry per row. For columns, use a dictionary cols mapping column indices to lists of row indices containing black pixels.
2. Iterate over every pixel in the grid, incrementing the respective row and column counters when a black pixel is found.
3. Create a two-dimensional array t to memoize whether pairs of rows are identical to avoid recomputing this information.
4. Iterate through each row i. If it contains exactly target black pixels, check each column j in that row. If column j also has target black pixels, verify that all rows in cols[j] are identical to row i. If so, each 'B' in this column is a lonely pixel.
5. The overall count of lonely pixels is then incremented for each qualifying black pixel found, and this count is finally returned.

The usage of memoization (in the two-dimensional array t) optimizes the solution by avoiding to repeatedly check if rows are identical throughout the loops, which reduces the time complexity significantly.

Solution Approach

The solution provided leverages arrays, hash tables (specifically a dictionary in Python), and a two-dimensional array (list of lists) for memoization. Here is a detailed walk-through of the implementation:

1. An array rows is created to count the number of black pixels in each row, while a Python dictionary cols is used to store lists of indices for rows that contain a black pixel for each column.

1rows = [0] * m  # m is the number of rows
2cols = defaultdict(list)  # dict to map column index to list of row indices

2. Two nested loops iterate over every element in the picture grid. If a black pixel is encountered ('B'), the count for that row in rows is incremented and the row index is appended to the list for that column in cols.

1for i in range(m):
2    for j in range(n):  # n is the number of columns
3        if picture[i][j] == 'B':
4            rows[i] += 1
5            cols[j].append(i)

3. A two-dimensional boolean array t is initialized to keep track of which rows are identical to others. This array is filled by comparing all pairs of rows. If two rows are identical, their corresponding entry in the array t is set to True.

1t = [[False] * m for _ in range(m)]
2for i in range(m):
3    for k in range(i, m):
4        if i == k:
5            t[i][k] = True
6        else:
7            t[i][k] = all([picture[i][j] == picture[k][j] for j in range(n)])
8        t[k][i] = t[i][k]

4. A variable res is initialized to count the number of lonely black pixels. The outer loop iterates over each row, and the inner loop over each column in that row. For each black pixel at (i, j), it checks:

• Whether its row i contains exactly target black pixels.
• Whether its column j contains exactly target black pixels.
• And if all rows having a black pixel in column j are identical to row i by utilizing the precomputed t array.

If all the conditions are satisfied, the pixel is considered a lonely black pixel, and res is incremented.

1res = 0
2for i in range(m):
3    if rows[i] == target:
4        for j in range(n):
5            if len(cols[j]) == target and all([t[i][k] for k in cols[j]]):
6                res += 1

5. Finally, res, which now holds the count of lonely black pixels, is returned as the solution to the problem.

The key algorithmic patterns used here are:

• Memoization (storing the results of identical row comparisons).
• Hash tables (using dictionaries for efficient look-ups and groupings).
• Array manipulations (working with indices and counters).

By combining these techniques, the solution efficiently computes the number of lonely black pixels in a large grid without the need to repeatedly compare rows or columns.

Example Walkthrough

Let's consider a small example to illustrate the solution approach. Suppose we have the following 3x3 grid named picture with target equal to 2:

1W B W
2B B B
3W B W

1. We first initialize rows to count black pixels in each row and cols to store row indices with a black pixel for each column. For the given picture, this looks like:

1rows = [1, 3, 1]  # there is 1 black pixel in rows 0 and 2, and 3 in row 1
2cols = defaultdict(list, {1: [0, 1, 2]})  # column 1 has a black pixel in all rows

2. We iterate over the grid. The rows and cols after iterating will already be as shown in step one since we have already counted the black pixels.

3. We then initialize a boolean array t to memoize row comparisons:

1t = [[False, False, False],
2     [False, True, False],
3     [False, False, False]]

Through comparions we would find that rows 0 and 2 are identical:

1t = [[True, False, True],
2     [False, True, False],
3     [True, False, True]]

4. We set res to 0 and start iterating through each pixel. For the black pixel at position (0,1):

• Its row has 1 black pixel, which does not match target.
• Its column has 3 black pixels, which does not match target.

None of the conditions are satisfied, so it is not considered lonely.

Next, let's consider the first black pixel at position (1,0):

• Its row has 3 black pixels, which does not match target.
• Therefore, this pixel is not considered, and no further checks are required for this pixel.

Finally, we consider a black pixel at position (2,1):

• Its row has 1 black pixel, which does not match target.
• Its column has 3 black pixels, which does not match target.

This pixel is also not lonely due to the same reasons as the first one.

5. After iterating through all pixels, no lonely black pixels are found. Therefore, res remains 0.

Given these steps, we can see that the result for this example is 0, meaning there are no lonely black pixels according to our target and picture. The approach efficiently checks each pixel's conditions while avoiding redundant row comparisons through memoization.

Solution Implementation

Time and Space Complexity

Time Complexity

The time complexity of the provided code can be broken down:

• Two nested loops over m rows and n columns to fill rows and cols, which takes O(m * n).
• Nested loops to populate the t array, which will take O(m^2 * n) because for each of the O(m^2) row comparisons, it iterates over all n columns.
• The final nested loops have a complexity of O(m * n * target). For each of the m rows, it iterates over all n columns, and for each column, it could iterate up to target times if all conditions are met.

Overall time complexity is dominated by the second step, which gives us O(m^2 * n).

Space Complexity

The space complexity consists of:

• Space taken by rows which is an array of length m, hence O(m).
• Space taken by cols which stores lists of rows where a 'B' was found. Since there could be a 'B' in every position, in the worst case, this is O(m * n).
• Space taken by the t array, which is a 2D array of dimensions m x m, leading to O(m^2).

Therefore, the total space complexity is O(m^2 + m * n), which simplifies to O(m^2) since this is the largest term when m is equal to or larger than n.

Learn more about how to find time and space complexity quickly using problem constraints.