Verbose C++ Solution


  • 0
    E

    Realized afterwards I could reduce time complexity by combining the isLonely and markVisited functions although that would reduce clarity.

    class Solution {
    public:
        // use picture as cache 
        bool isLonely(size_t row, size_t col, vector<vector<char>>& pic)
        {
            const size_t height = pic.size();
            const size_t width = pic.front().size();
            
            // test row
            for(size_t i=0; i<width; ++i)
            {
                if(i == col)
                    continue;
                if(pic[row][i] == 'B')
                    return false;
            }
            
            // test col
            for(size_t i=0; i<height; ++i)
            {
                if(i == row)
                    continue;
                if(pic[i][col] == 'B')
                    return false;
            }
            return true;
        }
        // mark row and col visited
        void markVisited(size_t row, size_t col, vector<vector<char>>& pic)
        {
            const size_t height = pic.size();
            const size_t width = pic.front().size();
    
            // mark row
            for(size_t col=0; col<width; ++col)
                pic[row][col] = 'V';
            
            // mark col
            for(size_t row=0; row<height; ++row)
                pic[row][col] = 'V';
        }
        int findLonelyPixel(vector<vector<char>>& picture)
        {
            const size_t height = picture.size();
            if(height == 0)
                return 0;
            const size_t width = picture.front().size();
            if(width == 0)
                return 0;
                
            int lonelyCount = 0;
            for(size_t row=0; row<height; ++row)
            {
                for(size_t col=0; col<width; ++col)
                {
                    if(picture[row][col] == 'V') // visited
                        continue;
                    if(picture[row][col] == 'W') // white
                        continue; 
                    
                    // black - check for lonely
                    const bool lonely = isLonely(row,col,picture);
                    if(lonely)
                    {
                        markVisited(row,col,picture);
                        lonelyCount++;
                    }
                }
            }
            return lonelyCount;
            
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.