533. Lonely Pixel II

MediumArrayHash TableMatrix
Leetcode Link

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
  1. 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)
  1. 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]
  1. 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
  1. 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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

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
  1. 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.

  2. 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]]
  1. 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.

  1. 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

1from collections import defaultdict
2
3class Solution:
4    def findBlackPixel(self, picture: List[List[str]], target: int) -> int:
5        # Get the dimensions of the picture.
6        num_rows, num_cols = len(picture), len(picture[0])
7
8        # Initialize counts for rows and columns.
9        row_black_counts = [0] * num_rows
10        col_index_mapping = defaultdict(list)
11
12        # Populate row and column data structures with the counts of black pixels.
13        for row in range(num_rows):
14            for col in range(num_cols):
15                if picture[row][col] == 'B':
16                    row_black_counts[row] += 1
17                    col_index_mapping[col].append(row)
18
19        # Initialize and construct a 2D array to track if rows are identical.
20        are_identical = [[False] * num_rows for _ in range(num_rows)]
21        for row_1 in range(num_rows):
22            for row_2 in range(row_1, num_rows):
23                if row_1 == row_2:
24                    are_identical[row_1][row_2] = True
25                else:
26                    are_identical[row_1][row_2] = all(picture[row_1][col] == picture[row_2][col] for col in range(num_cols))
27                # Mirror the value as the relation is symmetric.
28                are_identical[row_2][row_1] = are_identical[row_1][row_2]
29
30        # Variable to count the number of target black pixels.
31        black_pixel_count = 0
32      
33        # Loop through each row and column to find the black pixels as per the given conditions.
34        for row in range(num_rows):
35            if row_black_counts[row] == target:
36                for col in range(num_cols):
37                    # Check if the current column has the target number of 'B's and all corresponding rows are identical.
38                    if len(col_index_mapping[col]) == target and all(are_identical[row][other_row] for other_row in col_index_mapping[col]):
39                        black_pixel_count += 1
40
41        # Return the final count of black pixels that meet the criteria.
42        return black_pixel_count
43
1class Solution {
2    public int findBlackPixel(char[][] picture, int target) {
3        // dimensions of the picture
4        int rowCount = picture.length;
5        int colCount = picture[0].length;
6
7        // array to count black pixels in each row
8        int[] blackPixelsInRow = new int[rowCount];
9        // map to store list of rows for each black pixel column
10        Map<Integer, List<Integer>> blackPixelsInColumn = new HashMap<>();
11
12        // fill the counts for rows and columns
13        for (int i = 0; i < rowCount; ++i) {
14            for (int j = 0; j < colCount; ++j) {
15                if (picture[i][j] == 'B') {
16                    blackPixelsInRow[i]++;
17                    blackPixelsInColumn.computeIfAbsent(j, k -> new ArrayList<>()).add(i);
18                }
19            }
20        }
21
22        // array to memoize if rows are identical
23        boolean[][] identicalRows = new boolean[rowCount][rowCount];
24        for (int i = 0; i < rowCount; ++i) {
25            for (int k = i; k < rowCount; ++k) {
26                identicalRows[i][k] = i == k || areRowsIdentical(picture[i], picture[k]);
27                identicalRows[k][i] = identicalRows[i][k]; // symmetric, so we copy the value
28            }
29        }
30
31        // count the number of black pixels that meet the condition
32        int result = 0;
33        for (int i = 0; i < rowCount; ++i) {
34            if (blackPixelsInRow[i] == target) {
35                for (int j = 0; j < colCount; ++j) {
36                    List<Integer> col = blackPixelsInColumn.get(j);
37                    if (col != null && col.size() == target) {
38                        boolean columnsAreIdentical = true;
39                        for (int k : col) {
40                            columnsAreIdentical = columnsAreIdentical && identicalRows[i][k];
41                        }
42                        if (columnsAreIdentical) {
43                            result++;
44                        }
45                    }
46                }
47            }
48        }
49        return result;
50    }
51
52    // Helper method to check if two rows are identical
53    private boolean areRowsIdentical(char[] row1, char[] row2) {
54        int n = row1.length;
55        for (int j = 0; j < n; ++j) {
56            if (row1[j] != row2[j]) {
57                return false;
58            }
59        }
60        return true;
61    }
62}
63
1class Solution {
2public:
3    int findBlackPixel(vector<vector<char>>& picture, int target) {
4        int numRows = picture.size(), numCols = picture[0].size();
5        vector<int> blackPixelsPerRow(numRows);
6        unordered_map<int, vector<int>> rowsWithBlackPixelInCol;
7
8        // Count the number of black pixels per row and record the rows that have black pixels for each column
9        for (int i = 0; i < numRows; ++i) {
10            for (int j = 0; j < numCols; ++j) {
11                if (picture[i][j] == 'B') {
12                    ++blackPixelsPerRow[i];
13                    rowsWithBlackPixelInCol[j].push_back(i);
14                }
15            }
16        }
17
18        // Create a table to check if two rows are equal to each other
19        vector<vector<bool>> areRowsEqual(numRows, vector<bool>(numRows, false));
20        for (int i = 0; i < numRows; ++i) {
21            for (int k = i; k < numRows; ++k) {
22                areRowsEqual[i][k] = (i == k) || areAllElementsEqual(picture[i], picture[k]);
23                areRowsEqual[k][i] = areRowsEqual[i][k]; // Symmetry, saves future computations
24            }
25        }
26
27        int result = 0;
28        // Iterate through all the rows and columns to find the black pixels
29        for (int i = 0; i < numRows; ++i) {
30            if (blackPixelsPerRow[i] == target) {
31                for (int j = 0; j < numCols; ++j) {
32                    if (rowsWithBlackPixelInCol[j].size() == target) {
33                        bool isValidPixel = true;
34                        // Check if all rows for this column have black pixels and are identical
35                        for (int k : rowsWithBlackPixelInCol[j]) {
36                            isValidPixel &= areRowsEqual[i][k];
37                        }
38                        if (isValidPixel) ++result;
39                    }
40                }
41            }
42        }
43        return result;
44    }
45
46    // Helper function to check if all elements in two rows are equal
47    bool areAllElementsEqual(vector<char>& row1, vector<char>& row2) {
48        int numCols = row1.size();
49        for (int j = 0; j < numCols; ++j) {
50            if (row1[j] != row2[j]) return false;
51        }
52        return true;
53    }
54};
55
1// Define types for clarity
2type CharMatrix = Array<Array<char>>;
3type IntVector = number[];
4
5// Equivalent of 'int numRows';
6let numRows: number;
7
8// Equivalent of 'int numCols';
9let numCols: number;
10
11// This function finds the number of 'lonely' black pixels, which are indicated by 'B'
12function findBlackPixel(picture: CharMatrix, target: number): number {
13    numRows = picture.length;
14    numCols = picture[0].length;
15    // Equivalent of 'vector<int> blackPixelsPerRow(numRows);'
16    let blackPixelsPerRow: IntVector = new Array(numRows).fill(0);
17  
18    // Equivalent of 'unordered_map<int, vector<int>>'
19    // Stores columns mapping to their rows that contain a black pixel
20    let rowsWithBlackPixelInCol: Map<number, IntVector> = new Map();
21
22    // Count the number of black pixels per row and record the rows that have black pixels for each column
23    for (let i = 0; i < numRows; ++i) {
24        for (let j = 0; j < numCols; ++j) {
25            if (picture[i][j] === 'B') {
26                blackPixelsPerRow[i]++;
27                if (!rowsWithBlackPixelInCol.has(j)) {
28                    rowsWithBlackPixelInCol.set(j, []);
29                }
30                rowsWithBlackPixelInCol.get(j).push(i);
31            }
32        }
33    }
34
35    // Create a table to check if two rows are equal to each other
36    let areRowsEqual: boolean[][] = [];
37
38    for (let i = 0; i < numRows; ++i) {
39        areRowsEqual[i] = [];
40        for (let k = 0; k < numRows; ++k) {
41            areRowsEqual[i][k] = (i === k) || areAllElementsEqual(picture[i], picture[k]);
42            areRowsEqual[k][i] = areRowsEqual[i][k]; // Symmetry, saves future computations
43        }
44    }
45
46    let result: number = 0;
47    // Iterate through all the rows and columns to find the black pixels
48    for (let i = 0; i < numRows; ++i) {
49        if (blackPixelsPerRow[i] === target) {
50            for (let j = 0; j < numCols; ++j) {
51                let rowsWithBlackPixel = rowsWithBlackPixelInCol.get(j);
52                if (rowsWithBlackPixel && rowsWithBlackPixel.length === target) {
53                    let isValidPixel: boolean = true;
54                    // Check if all rows for this column have black pixels and are identical
55                    rowsWithBlackPixel.forEach(k => {
56                        isValidPixel = isValidPixel && areRowsEqual[i][k];
57                    });
58                    if (isValidPixel) result++;
59                }
60            }
61        }
62    }
63    return result;
64}
65
66// Helper function to check if all elements in two rows are equal
67function areAllElementsEqual(row1: char[], row2: char[]): boolean {
68    let numCols: number = row1.length;
69    for (let j = 0; j < numCols; ++j) {
70        if (row1[j] !== row2[j]) return false;
71    }
72    return true;
73}
74

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.


Fast Track Your Learning with Our Quick Skills Quiz:

Which one best describes the time complexity of the following code?

1int factorial(int n) {
2  if (n < 0) {
3    return -1;
4  } else if (n == 0) {
5    return 1;
6  } else {
7    return n * factorial(n - 1);
8  }
9}

Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Tired of the LeetCode Grind?

Our structured approach teaches you the patterns behind problems, so you can confidently solve any challenge. Get started now to land your dream tech job.

Get Started

🪄