Vultr DocsLatest Content

Lonely Pixel I

Updated on 03 June, 2025
Lonely Pixel I header image

Problem Statement

In the context of digital imagery composed of pixels represented as a grid of characters 'B' (for black) and 'W' (for white), the task is to count the number of lonely black pixels. A lonely black pixel is defined as a black pixel ('B') which is situated in such a position that there are no other black pixels in its entire row and its entire column. This problem involves scanning the picture, a 2D array, to check every black pixel's surrounding in its row and column to determine if it's lonely.

Examples

Example 1

Input:

picture = [["W","W","B"],["W","B","W"],["B","W","W"]]

Output:

3

Explanation:

All the three 'B's are black lonely pixels.

Example 2

Input:

picture = [["B","B","B"],["B","B","W"],["B","B","B"]]

Output:

0

Constraints

  • m == picture.length
  • n == picture[i].length
  • 1 <= m, n <= 500
  • picture[i][j] is 'W' or 'B'.

Approach and Intuition

To solve this problem, our primary task is to identify these lonely black pixels and count them. Given the constraints of the grid dimensions (1 <= m, n <= 500), we can parse through the grid efficiently using a few logical steps:

  1. Traverse every pixel in the grid. For each black pixel found ('B'):
    • Check its entire row and the column for the presence of any other 'B'. This could be initially attempted via two linear scans for each black pixel found — one horizontal (through the row), and one vertical (through the column).
  2. Optimize the approach using auxiliary space:
    • Create a count array rowBCount where rowBCount[i] holds the count of 'B' in the i-th row.
    • Similarly, create colBCount where colBCount[j] stores the count of 'B' in the j-th column.
    • As we populate these arrays, we also check each 'B' encountered during the traversal:
      • A pixel at picture[i][j] is lonely if and only if rowBCount[i] and colBCount[j] are both 1.
  3. By using these precomputed counts, check each black pixel more efficiently to determine if it is lonely by referencing the counts from rowBCount and colBCount.

This approach minimizes redundancy, reducing the need for multiple scans of the same rows and columns, thereby optimizing the algorithm to work well within the provided constraints.

Solutions

  • C++
  • Java
cpp 
class Solution {
public:
    // Check if given cell is isolated based on provided conditions
    bool isIsolated(vector<vector<char>>& grid, int row, int col) {
        int rows = grid.size();
        int cols = grid[0].size();
        
        int blackCells = 0;
        for (int r = 0; r < rows; r++) {
            blackCells += (grid[r][col] == 'B');
        }
        
        for (int c = 0; c < cols; c++) {
            // to avoid counting the cell itself twice
            if (c != col) blackCells += (grid[row][c] == 'B');
        }
        return grid[row][col] == 'B' && blackCells == 1;
    }
    
    int findLonelyPixel(vector<vector<char>>& grid) {
        int rows = grid.size();
        int cols = grid[0].size();
        
        int lonelyCount = 0;
        // Inspecting the starting row for lonely pixels
        for (int c = 0; c < cols; c++) {
            lonelyCount += isIsolated(grid, 0, c);
        }
        // Inspecting the starting column for lonely pixels
        for (int r = 1; r < rows; r++) {
            lonelyCount += isIsolated(grid, r, 0);
        }

        // Modifying grid to integers for easy handling
        for (int c = 0; c < cols; c++) {
            grid[0][c] = (grid[0][c] == 'B' ? '1' : '0');
        }
        
        for (int r = 0; r < rows; r++) {
            grid[r][0] = (grid[r][0] == 'B' ? '1' : '0');
        }
        
        // Detect isolated 'B's and counting
        for (int r = 1; r < rows; r++) {
            for (int c = 1; c < cols; c++) {
                if (grid[r][c] == 'B') {
                    grid[r][0]++;
                    grid[0][c]++;
                }
            }
        }
        
        for (int r = 1; r < rows; r++) {
            for (int c = 1; c < cols; c++) {
                if (grid[r][c] == 'B') {
                    if (grid[0][c] == '1' && grid[r][0] == '1') {
                        lonelyCount++;
                    }
                }
            }
        }
        
        return lonelyCount;
    }
};

The provided C++ solution is designed to find "lonely pixels" in a given grid. A pixel is considered lonely if it is the only black pixel in its row and column. The solution consists of two main functions within a class named Solution.

  • The isIsolated function checks if a black pixel, located at a specific row and column in the grid, is lonely by counting black pixels in the entire row and column. It returns true if the pixel is lone and false otherwise.

  • The findLonelyPixel function traverses the grid to count all the lonely pixels using the isIsolated function. This function starts by handling the first row and first column differently to check if any pixel in these positions is lonely, due to easy handling and edge cases in grid operations. The calculation is then extended to the entire grid where each cell's interactions with rows and columns are modified and inspected.

In essence, this implementation:

  • Undergoes an initialization step that involves setting grid values to handle conditions better.
  • Uses two nested loops to iterate through the rows and columns, checking each pixel for the "lonely" condition.
  • Deploys an efficient method to ensure that the row-wise and column-wise loneliness check does not doubly count the pixel itself.
  • Returns the total count of lonely pixels in the grid.

A detailed view of handling digital grid values allows for efficient calculation while maintaining clarity in verifying the conditions for lonely pixels. Overall, the approach efficiently identifies and counts these uniquely positioned pixels while employing simple numerical and conditional operations for clarity and performance.

java 
class Solution {
    // Check if a cell (row, col) is 'lonely' or not.
    boolean isLonely(char[][] grid, int row, int col) {
        int rows = grid.length;
        int cols = grid[0].length;
        
        int blackCellsCount = 0;
        for (int i = 0; i < rows; i++) {
            blackCellsCount += (grid[i][col] == 'B' ? 1 : 0);
        }
        
        for (int j = 0; j < cols; j++) {
            if (j != col) blackCellsCount += (grid[row][j] == 'B' ? 1 : 0);
        }
        return grid[row][col] == 'B' && blackCellsCount == 1;
    }
    
    public int findSoloPixel(char[][] grid) {
        int rowLength = grid.length;
        int colLength = grid[0].length;
        
        int singleBlackCells = 0;
        for (int c = 0; c < colLength; c++) {
            singleBlackCells += isLonely(grid, 0, c) ? 1 : 0;
        }
        for (int r = 1; r < rowLength; r++) {
            singleBlackCells += isLonely(grid, r, 0) ? 1 : 0;
        }

        // Convert 'B' to '1' and 'W' to '0' for the first row and column
        for (int c = 0; c < colLength; c++) {
            grid[0][c] = grid[0][c] == 'B' ? '1' : '0';
        }
        
        for (int r = 0; r < rowLength; r++) {
            grid[r][0] = grid[r][0] == 'B' ? '1' : '0';
        }
        
        // Increment the count of black cells for row and column
        for (int r = 1; r < rowLength; r++) {
            for (int c = 1; c < colLength; c++) {
                if (grid[r][c] == 'B') {
                    grid[r][0]++;
                    grid[0][c]++;
                }
            }
        }
        
        for (int r = 1; r < rowLength; r++) {
            for (int c = 1; c < colLength; c++) {
                if (grid[r][c] == 'B' && grid[0][c] == '1' && grid[r][0] == '1') {
                    singleBlackCells++;
                }
            }
        }
        
        return singleBlackCells;
    }
}

The Java solution provided addresses the problem of identifying and counting lonely 'B' pixels in a 2D grid, where a pixel is considered lonely if it is the only black pixel in its row and column.

The solution comprises two primary methods: isLonely and findSoloPixel.

  • isLonely(char[][] grid, int row, int col):

    • Determines if a pixel at a specific row and column is lonely.
    • Iterates through the entire row and column of the pixel to count how many times 'B' appears, excluding the check at the current pixel coordinate.
    • Returns true if the pixel itself is 'B' and it is the only 'B' in its row and column.

  • findSoloPixel(char[][] grid):

    • Initializes counters for the grid dimension and the number of single black cells.
    • Scans the first row and column using the isLonely method to preliminary count lonely 'B' pixels.
    • Converts characters in the first row and column of the grid to simplify further processing: 'B' becomes '1' and 'W' becomes '0'.
    • Further increments counters based on the presence of 'B' to determine potential lonely pixels.
    • After setting up counts, applies the lonely criteria again for the rest of the grid, specifically checking if modified counters from previous steps indicate a lonely pixel condition.
    • Ultimately returns the count of lonely black cells.

With the given approach, pixel isolation is determined in a systematic manner allowing for both initial direct checking and subsequent optimized counting through transformed grid values. The solution ensures that each pixel's loneliness is assessed accurately, reflecting the final count of solo black cells. Hence, execute this method to extract and identify all lonely black pixels in a given 2D character grid efficiently.

Comments

No comments yet.