Count Lonely Pixel Ii In C++

The issue tackled in the Count Lonely Pixel II challenge involves identifying individual black pixels ('B') within a two-dimensional character grid. Within this grid, there are two distinct types of pixels: black ('B') and white ('W'). A black pixel is considered solitary if it satisfies two criteria:

• ✅ It exists as the sole black pixel within its respective row.
• ✅ It exists as the sole black pixel within its corresponding column.

The objective is to calculate the overall count of isolated black pixels within the grid.

Input Example

For example, consider the following grid:

B W W W
W B W W
W W B W

In this matrix:

• ✅ Every black pixel ('B') is unique within its row and column, making all three black pixels isolated.

Steps to Solve the Problem

To efficiently address this issue, adhere to the following instructions provided:

Step 1: Count Black Pixels in Rows and Columns

Initially, calculate the total number of black pixels in every row and column. This data is crucial for promptly identifying isolated black pixels.

For example, in the grid:

B W W W
W B W W
W W B W

Row counts:

• ✅ Row 0: 1 black pixel.
• ✅ Row 1: 1 black pixel.
• ✅ Row 2: 1 black pixel.

Column counts:

• ✅ Column 0: 1 black pixel.
• ✅ Column 1: 1 black pixel.
• ✅ Column 2: 1 black pixel.
• ✅ Column 3: 0 black pixels.

Step 2: Check Each Black Pixel

For each black pixel within the grid:

• ✅ Verify if it stands as the sole black pixel in its respective row.
• ✅ Examine if it stands as the sole black pixel in its respective column.

If both criteria are met, then it qualifies as an isolated pixel.

Approach 1: Simple Approach

Program:

#include <iostream>
#include <vector>
using namespace std;
int countLonelyPixels(vector<vector<char>>& grid) {
    int rows = grid.size();
    int cols = grid[0].size();
    vector<int> rowCount(rows, 0); // Counts of 'B' in each row
    vector<int> colCount(cols, 0); // Counts of 'B' in each column
    // Step 1: Count black pixels in rows and columns
    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < cols; ++j) {
            if (grid[i][j] == 'B') {
                rowCount[i]++;
                colCount[j]++;
            }
        }
    }
    // Step 2: Check for lonely pixels
    int lonelyCount = 0;
    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < cols; ++j) {
            if (grid[i][j] == 'B' && rowCount[i] == 1 && colCount[j] == 1) {
                lonelyCount++;
            }
        }
    }
    return lonelyCount;
}
int main() {
    vector<vector<char>> grid = {
        {'B', 'W', 'W', 'W'},
        {'W', 'B', 'W', 'W'},
        {'W', 'W', 'B', 'W'}
    };    
    cout << "Number of Lonely Pixels: " << countLonelyPixels(grid) << endl;
    return 0;
}

Output:

Number of Lonely Pixels: 3

1. Understanding the Input

The input consists of a 2D grid or matrix containing characters 'B' and 'W':

The character 'B' denotes a black pixel.

The character 'W' signifies a white pixel.

We strive to determine the count of isolated black pixels ('B'). A black pixel is considered isolated if:

• ✅ It stands alone as the sole black pixel within its row.
• ✅ It stands alone as the sole black pixel within its column.

For example:

B W W W
W B W W
W W B W

Here, each black pixel stands alone as the sole 'B' in both its row and column.

2. How to Approach the Problem

To find the lonely black pixels, we need to:

• ✅ Count the number of black pixels in each row.
• ✅ Count the number of black pixels in each column.
• ✅ Check for each 'B' in the grid:
• ✅ If its row has only 1 'B'.
• ✅ If its column has only 1 'B'.

If both conditions are true, that pixel is lonely, and we count it.

3. Step-by-Step Explanation of the Code

Step 1: Counting Black Pixels

We establish two lists (or arrays):

• ✅ rowCount is designated to hold the count of 'B' in every row.
• ✅ colCount is designated to record the count of 'B' in each column.

We proceed to iterate over the complete grid, examining each cell individually:

In case the current cell holds the value 'B', we increment the count associated with the respective row and column.

For example, if the grid is:

B W W W
W B W W
W W B W

After counting:

rowCount changes to [1, 1, 1] as every row contains exactly 1 'B'.

colCount becomes [1, 1, 1, 0] because:

• ✅ Column 0 has 1 'B'.
• ✅ Column 1 has 1 'B'.
• ✅ Column 2 has 1 'B'.
• ✅ Column 3 has no 'B'.

Step 2: Checking Each Pixel

Next, we iterate through the grid once more. For every cell:

If the letter 'B' is present:

• ✅ Verify its corresponding row in the rowCount variable.
• ✅ Validate its respective column in the colCount variable.

If both the row and column counts are 1, it means this 'B' is lonely.

For example:

The initial 'B' in the top-left corner feels isolated due to the following reasons:

• ✅ rowCount[0] equals 1, indicating there is just a single black pixel in its row.
• ✅ colCount[0] equals 1, showing there is only one black pixel in its column.

Similarly, the other black pixels are lonely too.

Step 3: Counting Lonely Pixels

When encountering an isolated pixel, we increment a counter named lonelyCount. Upon completion of this process, the counter reflects the overall count of solitary black pixels within the grid.

4. Efficiency

This solution is efficient because:

• ✅ It goes through the grid only twice: Once to calculate row and column counts. A second time to check for lonely pixels.
• ✅ It uses two arrays (rowCount and colCount) to keep track of counts, which saves time compared to recalculating counts repeatedly.
• ✅ Once to calculate row and column counts.
• ✅ A second time to check for lonely pixels.

5. Example Walkthrough

Let’s revisit the grid:

B W W W
W B W W
W W B W

Step 1 (Calculate Black Pixel Counts):

• ✅ rowCount = [1, 1, 1] (indicating one black pixel in each row).
• ✅ colCount = [1, 1, 1, 0] (showing that columns 0, 1, and 2 contain one black pixel each, while column 3 has none).

Step 2 (Check for Lonely Pixels):

First 'B' at (0, 0):

• ✅ rowCount[0] = 1 (only one 'B' in row 0).
• ✅ colCount[0] = 1 (only one 'B' in column 0).
• ✅ It’s lonely.

Second 'B' at (1, 1):

• ✅ rowCount[1] = 1 (only one 'B' in row 1).
• ✅ colCount[1] = 1 (only one 'B' in column 1).
• ✅ It’s lonely.

Third 'B' at (2, 2):

• ✅ rowCount[2] = 1 (only one 'B' in row 2).
• ✅ colCount[2] = 1 (only one 'B' in column 2).
• ✅ It’s lonely.

Step 3 involves calculating the number of isolated pixels in the image.

• ✅ The total count of lonely pixels equals 3.

6. Final Output

For the provided sample grid, there are a total of 3 isolated black pixels.

Approach 2: Using Maps for Row and Column Tracking

Instead of utilizing static arrays for rowCount and colCount, we have the option to employ hash maps to dynamically monitor the quantities of black pixels in rows and columns. This strategy proves particularly beneficial when the grid has sparsity or when the grid's dimensions are extensive.

Program:

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
int countLonelyPixels(vector<vector<char>>& grid) {
    unordered_map<int, int> rowCount; // Map to count 'B' in each row
    unordered_map<int, int> colCount; // Map to count 'B' in each column
    vector<pair<int, int>> blackPixels; // To store the positions of all 'B'
    int rows = grid.size();
    int cols = grid[0].size();
    // Step 1: Count 'B' in rows and columns, and store positions of 'B'
    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < cols; ++j) {
            if (grid[i][j] == 'B') {
                rowCount[i]++;
                colCount[j]++;
                blackPixels.emplace_back(i, j); // Save the position of this 'B'
            }
        }
    }
    // Step 2: Check each stored position for loneliness
    int lonelyCount = 0;
    for (auto& pos : blackPixels) {
        int row = pos.first;
        int col = pos.second;
        if (rowCount[row] == 1 && colCount[col] == 1) {
            lonelyCount++; // This 'B' is lonely
        }
    }
    return lonelyCount;
}
int main() {
    vector<vector<char>> grid = {
        {'B', 'W', 'W', 'W'},
        {'W', 'B', 'W', 'W'},
        {'W', 'W', 'B', 'W'}
    };
    cout << "Number of Lonely Pixels: " << countLonelyPixels(grid) << endl;
    return 0;
}

Output:

Number of Lonely Pixels: 3

Explanation:

Data Structures Utilized:

• ✅ A pair of hash tables (rowCount and colCount) are maintained to monitor the quantity of black pixels ('B') in individual rows and columns.
• ✅ Furthermore, a collection (blackPixels) is employed to retain the coordinates of every black pixel.

First Pass Through the Grid:

• ✅ The code scans the grid row by row.
• ✅ Each time a 'B' is found:
• ✅ Increase the count for that row in rowCount.
• ✅ Increase the count for that column in colCount.
• ✅ Save the position (row, column) in blackPixels.

Second Pass Using blackPixels:

• ✅ For every position stored in blackPixels:
• ✅ Check the corresponding row count in rowCount.
• ✅ Check the corresponding column count in colCount.
• ✅ If both counts are 1, it means this black pixel is lonely.

Count Solitary Pixels:

Increment a counter (lonelyCount) for every isolated black pixel identified during the second iteration.

• ✅ The ultimate result of solitaryCount indicates the overall count of isolated black pixels within the grid.

Example Walkthrough

For the grid:

B W W W
W B W W
W W B W

• ✅ After the first pass: rowCount: {0: 1, 1: 1, 2: 1}. colCount: {0: 1, 1: 1, 2: 1}. blackPixels: [(0, 0), (1, 1), (2, 2)].
• ✅ In the second pass: (0, 0) has rowCount[0] = 1 and colCount[0] = 1 → Lonely. (1, 1) has rowCount[1] = 1 and colCount[1] = 1 → Lonely. (2, 2) has rowCount[2] = 1 and colCount[2] = 1 → Lonely.
• ✅ Final lonelyCount = 3.
• ✅ rowCount: {0: 1, 1: 1, 2: 1}.
• ✅ colCount: {0: 1, 1: 1, 2: 1}.
• ✅ blackPixels: [(0, 0), (1, 1), (2, 2)].
• ✅ (0, 0) has rowCount[0] = 1 and colCount[0] = 1 → Lonely.
• ✅ (1, 1) has rowCount[1] = 1 and colCount[1] = 1 → Lonely.
• ✅ (2, 2) has rowCount[2] = 1 and colCount[2] = 1 → Lonely.

Complexity Analysis:

Time Complexity:

First Iteration: With a time complexity of O(m×n), this process scans through each cell in the grid to tally the number of black pixels and store their coordinates.

Second Iteration: O(k)

• ✅ Iterates through every black pixel within the blackPixels collection, with k representing the quantity of black pixels.

Total: O(m×n), as k≤m×n.

Space Complexity:

Row and Column Maps: O(m+n), for storing counts.

Black Pixel Positions: O(k).

Total: O(m+n+k).

Approach 3: Row and Column Iteration Without Additional Data Structures

Instead of relying on maps or arrays to keep track of counts, we can compute the counts on-the-fly while traversing the grid. This method eliminates the need for additional storage to store row and column counts.

Program:

#include <iostream>
#include <vector>
using namespace std;
int countLonelyPixels(vector<vector<char>>& grid) {
    int rows = grid.size();
    int cols = grid[0].size();
    int lonelyCount = 0;
    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < cols; ++j) {
            if (grid[i][j] == 'B') {
                // Count black pixels in the current row
                int rowBlackCount = 0;
                for (int k = 0; k < cols; ++k) {
                    if (grid[i][k] == 'B') rowBlackCount++;
                }  
                // Count black pixels in the current column
                int colBlackCount = 0;
                for (int k = 0; k < rows; ++k) {
                    if (grid[k][j] == 'B') colBlackCount++;
                }
                // Check if this pixel is lonely
                if (rowBlackCount == 1 && colBlackCount == 1) {
                    lonelyCount++;
                }
            }
        }
    }
    return lonelyCount;
}
int main() {
    vector<vector<char>> grid = {
        {'B', 'W', 'W', 'W'},
        {'W', 'B', 'W', 'W'},
        {'W', 'W', 'B', 'W'}
    };
    cout << "Number of Lonely Pixels: " << countLonelyPixels(grid) << endl;
    return 0;
}

Output:

Number of Lonely Pixels: 3

Explanation:

Grid Navigation:

When traversing the grid, the application iterates through each cell systematically, progressing from one row to the next and then from one column to the following one. During this process, each cell is inspected to determine if its content corresponds to 'B' denoting a black pixel. If the content does not match 'B', the program proceeds to examine the subsequent cell.

Counting Black Pixels in the Row:

• ✅ Once a black pixel is found at a specific position (i, j), the program counts all the black pixels in that row.
• ✅ It does this by iterating through all the columns of that row while keeping a counter (rowBlackCount).
• ✅ If the number of black pixels in that row is more than 1, the current black pixel cannot be lonely, so further checks for that pixel are skipped.

Counting Black Pixels in the Column:

• ✅ If the row count is exactly 1, the program then counts all the black pixels in the column of the current position (i, j).
• ✅ It iterates through all the rows of that column while keeping another counter (colBlackCount).
• ✅ If the column count is more than 1, the current black pixel cannot be lonely, so it is not included in the final count.

Checking Loneliness:

• ✅ A black pixel is considered lonely if:
• ✅ The total number of black pixels in its row is exactly 1.
• ✅ The total number of black pixels in its column is exactly 1.
• ✅ If both conditions are met, the program increments the counter for lonely black pixels (lonelyCount).

Final Tally:

• ✅ Upon inspecting each cell within the grid, the software tallies up the total number of isolated black pixels.
• ✅ The outcome of this calculation is then displayed as the final count.

Example Walkthrough:

Given the grid:

B W W W
W B W W
W W B W

Step 1: Start at (0, 0):

• ✅ 'B' found.
• ✅ Count black pixels in row 0: 1 black pixel ('B').
• ✅ Count black pixels in column 0: 1 black pixel ('B').
• ✅ Both counts are 1 → Lonely pixel found.

Move to position (0, 1) in the grid.

Skip the cell if the letter 'W' is encountered.

Step 3: Continue to (1, 1):

• ✅ 'B' found.
• ✅ Count black pixels in row 1: 1 black pixel ('B').
• ✅ Count black pixels in column 1: 1 black pixel ('B').
• ✅ Both counts are 1 → Lonely pixel found.

Step 4: Continue to (2, 2):

• ✅ 'B' found.
• ✅ Count black pixels in row 2: 1 black pixel ('B').
• ✅ Count black pixels in column 2: 1 black pixel ('B').
• ✅ Both counts are 1 → Lonely pixel found.

Final Count:

• ✅ Lonely pixels = 3.

Complexity analysis:

Outer Iterations:

• ✅ Iterate through each cell within the grid → O(m×n).

Counting the Number of Black Pixels in a Row:

To determine the quantity of black pixels in a row, the time complexity is O(n) for each black pixel.

Column Enumeration for Every Black Pixel:

• ✅ Iterate through each column to tally black pixels → O(m) for each black pixel.

Total Duration:

• ✅ In the scenario of having k black pixels, the time complexity is O(k×(m+n)).
• ✅ In the worst-case scenario where k equals m×n, the time complexity becomes O(m×n×(m+n)).

Space Complexity:

Additional Memory Allocation:

No supplementary data structures → Constant O(1) extra space.

Grid Storage:

• ✅ Grid is already provided → O(m×n).

Advantages:

Some benefits of utilizing the Count Lonely Pixel II in C++ include:

Simplicity:

• ✅ The method is straightforward to comprehend and execute as it sequentially traverses the grid and tallies the pixels in real-time without intricate data structures.

The algorithm operates with constant O(1) extra space, indicating that it doesn't necessitate extra arrays or hashmaps to track row and column counts. It solely relies on a small number of variables for tallying purposes.

No Sorting:

• ✅ In contrast to certain alternative techniques, this method does not necessitate arranging data or intricate algorithms, simplifying the process for grids of modest to moderate sizes.

Disadvantages:

The Count Lonely Pixel II in C++ has various drawbacks, including:

The algorithm iterates through black pixels within the row and column multiple times for each individual black pixel, resulting in redundant computations that are unnecessary.

When dealing with extensive grids, this method may experience sluggish performance due to excessive validation checks carried out for every individual pixel.