Problem statement

https://leetcode.com/problems/lonely-pixel-ii/

Solution

The main difficulty of this problem is to understand the second condition. What is asked: for each black pixel we need to count number of black pixels in row R and column C$and make sure they are equal. Also, we need to check all other black pixels in the column C and make sure, that rows are equal to row R.

So, we need to check equality of row a lot, so let us create dictionary dic, where we group rows by groups with equal rows inside. Then we create corrs array, where we put unique numbers for each row, and numbers are equal only for equal rows. Also we count number of black pixels in each row.

Finally, we iterate over columns. For each column we found black pixels, check rules 1 and 2 in O(m).

Complexity

Overall time complexity is O(mn), space complexity is also O(mn).

Code

class Solution:
    def findBlackPixel(self, picture, N):
        m, n = len(picture), len(picture[0])
        dic = defaultdict(list)
        corrs = [-1]*m
        lines_black = [-1]*m
        for i, line in enumerate(picture):
            dic["".join(line)].append(i)
            lines_black[i] = sum([picture[i][j]=="B" for j in range(n)])
        
        it, result = 0, 0
        for line, nums in dic.items():
            for num in nums: corrs[num] = it
            it += 1

        for i in range(n):
            lines = [j for j in range(m) if picture[j][i] == "B"]
            l_num = [corrs[j] for j in lines]
            if len(set(l_num)) == 1 and len(lines) == lines_black[lines[0]] and len(lines) == N:
                result += len(lines)

        return result