HeYulong 3D

[LeetCode] The Process of Solving Lonely Pixel I(531) and Lonely Pixel II(533)

Lonely Pixel I(531)

Description

Given an m x n picture consisting of black ‘B’ and white ‘W’ pixels, return the number of black lonely pixels.
A black lonely pixel is a character ‘B’ that located at a specific position where the same row and same column don’t have any other black pixels.


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

My Submissions

Submission 1

At first, I think it should iterate over the whole matrix to extract enough information. We can see 2 conditions for a black lonely pixel:

  1. is a character ‘B’
  2. located at a specific position where the same row and same column don’t have any other black pixels.

Condition 1 is just local information, but condition 2 is global information. So I just need to save this global information in some way. After that, I can just iterate over this matrix again, and use this global information to calculate the count of black lonely pixels.

class Solution {
public:
    int findLonelyPixel(vector<vector<char>>& picture) {
        int result = 0;

		std::vector<int> row_pixel_num(picture.size(), 0);
		std::vector<int> col_pixel_num(picture[0].size(), 0);

		for (int i = 0; i < picture.size(); ++i)
		{
			for (int j = 0; j < picture[0].size(); ++j)
			{
				if (picture[i][j] == 'B')
				{
					row_pixel_num[i]++;
					col_pixel_num[j]++;
				}
			}
		}

		for (int i = 0; i < picture.size(); ++i)
		{
			for (int j = 0; j < picture[0].size(); ++j)
			{
				if (picture[i][j] == 'B')
				{
					if (row_pixel_num[i] == 1 && col_pixel_num[j] == 1) result++;
				}
			}
		}

		return result;
    }
};

Submission 2

But I do not like the second iteration. In the first iteration, we’ve already seen the local information. If the matrix is very big and the count of black lonely pixels is small, it can be a waste of time. So I use more space to save time.

class Solution {
public:
    int findLonelyPixel(vector<vector<char>>& picture) {
        int result = 0;
		const int m = picture.size();
		const int n = picture[0].size();

		std::vector<unsigned short> row_pixel_num(m, 0);
		std::vector<unsigned short> col_pixel_num(n, 0);
		std::vector<std::tuple<unsigned short, unsigned short>> indices;
		indices.reserve(m + n);

		for (int i = 0; i < m; ++i)
		{
			for (int j = 0; j < n; ++j)
			{
				if (picture[i][j] == 'B')
				{
					row_pixel_num[i]++;
					col_pixel_num[j]++;
					indices.emplace_back(std::make_tuple(i, j));
				}
			}
		}

		for (const auto& index : indices)
		{
			if (row_pixel_num[std::get<0>(index)] == 1 && col_pixel_num[std::get<1>(index)] == 1)
			{
				result++;
			}
		}

		return result;
    }
};

Using this code, I can get a result that has a lower runtime:

Lonely Pixel I(531)

Description

Given an m x n picture consisting of black 'B' and white 'W' pixels and an integer target, return the number of black lonely pixels.

A black lonely pixel is a character 'B' that located at a specific position (r, c) where:

  • Row r and column c both contain exactly target black pixels.
  • For all rows that have a black pixel at column c, they should be exactly the same as row r.

Example 1:

Input: picture = [["W","B","W","B","B","W"],["W","B","W","B","B","W"],["W","B","W","B","B","W"],["W","W","B","W","B","W"]], target = 3
Output: 6
Explanation: All the green 'B' are the black pixels we need (all 'B's at column 1 and 3).
Take 'B' at row r = 0 and column c = 1 as an example:
 - Rule 1, row r = 0 and column c = 1 both have exactly target = 3 black pixels. 
 - Rule 2, the rows have black pixel at column c = 1 are row 0, row 1 and row 2. They are exactly the same as row r = 0.

Example 2:

Input: picture = [["W","W","B"],["W","W","B"],["W","W","B"]], target = 1
Output: 0

Constraints:

  • m == picture.length
  • n == picture[i].length
  • 1 <= m, n <= 200
  • picture[i][j] is 'W' or 'B'.
  • 1 <= target <= min(m, n)

My Submissions

Submission 1(Time Limit Exceeded)

By using the same structure, we can achieve condition 1: Row r and column c both contain exactly target black pixels. As for the condition 2, I used a rather naive and time-consuming code to check:

class Solution {
public:
bool checkRowsAreSame(std::vector<std::vector<char>>& picture, int row, int col)
	{
		for (int i = 0; i < picture.size(); ++i)
		{
			if (picture[i][col] == 'B' && i != row)
			{
				for (int j = 0; j < picture[0].size(); ++j)
				{
					if (picture[i][j] != picture[row][j]) return false;  // Check same
				}
			}
		}
		return true;
	}
    
    int findBlackPixel(vector<vector<char>>& picture, int target) {
        int result = 0;
		const int m = picture.size();
		const int n = picture[0].size();
		
		std::vector<int> row_black_num(m, 0);
		std::vector<int> col_black_num(n, 0);
		std::vector<std::tuple<int, int>> indices;

		for (int i = 0; i < m; ++i)
		{
			for (int j = 0; j < n; ++j)
			{
				if (picture[i][j] == 'B')
				{
					row_black_num[i]++;
					col_black_num[j]++;
					indices.emplace_back(std::make_tuple(i, j));
				}
			}
		}

		for (const auto& index : indices)
		{
			int i = std::get<0>(index);
			int j = std::get<1>(index);
			if (row_black_num[i] == target && col_black_num[j] == target)  // Rule 1
			{
				if (checkRowsAreSame(picture, i, j)) result++;
			}
		}

		return result;
    }
};

Opps! Time limit exceeded.

Submission 2(Time Limit Exceeded)

checkRowsAreSame may repeat calculate isSameRow for the same i and j, so I use an unordered map to store this information to avoid this.

class Solution {
public:
	bool isSameRow(const std::vector<char>& row1, const std::vector<char>& row2)
	{
		for (int i = 0; i < row1.size(); ++i)
		{
			if (row1[i] != row2[i]) return false;
		}
		return true;
	}

	bool checkRowsAreSame(std::vector<std::vector<char>>& picture, std::unordered_map<std::string, bool>& sameRows, int row, int col)
	{
		for (int i = 0; i < picture.size(); ++i)
		{
			if (picture[i][col] == 'B' && i != row)
			{
				std::string key;
				if (i < row) key = std::to_string(i) + "-" + std::to_string(row);
				else key = std::to_string(row) + "-" + std::to_string(i);
				if (sameRows.find(key) != sameRows.end())
				{
					// Find it, so use it without calculating
					if (!sameRows[key]) return false;
				}
				else
				{
					// Do not find it, so calculate and save it.
					bool same = isSameRow(picture[i], picture[row]);
					sameRows.emplace(key, same);
					if (!same) return false;
				}
			}
		}
		return true;
	}
    
    int findBlackPixel(vector<vector<char>>& picture, int target) {
        int result = 0;
		const int m = picture.size();
		const int n = picture[0].size();
		
		std::vector<int> row_black_num(m, 0);
		std::vector<int> col_black_num(n, 0);
		std::vector<std::tuple<int, int>> indices;
		std::unordered_map<std::string, bool> sameRows;

		for (int i = 0; i < m; ++i)
		{
			for (int j = 0; j < n; ++j)
			{
				if (picture[i][j] == 'B')
				{
					row_black_num[i]++;
					col_black_num[j]++;
					indices.emplace_back(std::make_tuple(i, j));
				}
			}
		}

		for (const auto& index : indices)
		{
			int i = std::get<0>(index);
			int j = std::get<1>(index);
			if (row_black_num[i] == target && col_black_num[j] == target)  // Rule 1
			{
				if (checkRowsAreSame(picture, sameRows, i, j)) result++;
			}
		}

		return result;
    }
};

Still, time limit exceeded!

Submission 3 and 4(Passed)

I think, for each valid column(rule 1), I can only call checkRowsAreSame only once, because if rule 2 are satisfied, other black pixel for this column should satisfy rule 2 too.

class Solution {
public:
	bool isSameRow(const std::vector<char>& row1, const std::vector<char>& row2)
	{
		for (int i = 0; i < row1.size(); ++i)
		{
			if (row1[i] != row2[i]) return false;
		}
		return true;
	}

	bool checkRowsAreSame(std::vector<std::vector<char>>& picture, std::unordered_map<std::string, bool>& sameRows, int row, int col)
	{
		for (int i = 0; i < picture.size(); ++i)
		{
			if (picture[i][col] == 'B' && i != row)
			{
				std::string key;
				if (i < row) key = std::to_string(i) + "-" + std::to_string(row);
				else key = std::to_string(row) + "-" + std::to_string(i);
				if (sameRows.find(key) != sameRows.end())
				{
					// Find it, so use it without calculating
					if (!sameRows[key]) return false;
				}
				else
				{
					// Do not find it, so calculate and save it.
					bool same = isSameRow(picture[i], picture[row]);
					sameRows.emplace(key, same);
					if (!same) return false;
				}
			}
		}
		return true;
	}
    
    int findBlackPixel(vector<vector<char>>& picture, int target) {
        int result = 0;
		const int m = picture.size();
		const int n = picture[0].size();
		
		std::vector<int> row_black_num(m, 0);
		std::vector<int> col_black_num(n, 0);
		std::vector<std::tuple<int, int>> indices;
		std::unordered_map<std::string, bool> same_rows;
		std::unordered_set<int> col_checked;

		for (int i = 0; i < m; ++i)
		{
			for (int j = 0; j < n; ++j)
			{
				if (picture[i][j] == 'B')
				{
					row_black_num[i]++;
					col_black_num[j]++;
					indices.emplace_back(std::make_tuple(i, j));
				}
			}
		}

		for (const auto& index : indices)
		{
			int i = std::get<0>(index);
			int j = std::get<1>(index);
			if (row_black_num[i] == target && col_black_num[j] == target)  // Rule 1
			{
				if (col_checked.find(j) == col_checked.end())
				{
					// Need some calculation when this column unchecked
					bool same = checkRowsAreSame(picture, same_rows, i, j);
					col_checked.emplace(j);
					if (same) result += target;
				}
			}
		}

		return result;
    }
};

Thankfully, this code had passed, but I thought it can be more performant and readable…

I tried to optimize the code, but it can be hard to understand…

class Solution {
public:
	bool isSameRow(const std::vector<char>& row1, const std::vector<char>& row2)
	{
		for (int i = 0; i < row1.size(); ++i)
		{
			if (row1[i] != row2[i]) return false;
		}
		return true;
	}

	bool checkRowsAreSame(std::vector<std::vector<char>>& picture, int row, int col, unsigned short* row_black_num, char** same_row_status)
	{
		for (int i = 0; i < picture.size(); ++i)
		{
			if (picture[i][col] == 'B' && i != row)
			{
				char& status = same_row_status[i < row ? i : row][i > row ? i : row];
				switch (status)
				{
				case 0:  // undefined
					if (row_black_num[i] != row_black_num[row])
					{
						status = 'F';
						return false;
					}

					if (isSameRow(picture[i], picture[row])) status = 'T';
					else
					{
						status = 'F';
						return false;
					}
					break;
				case 'F':
					return false;  // calculated status: not same
				default:
					// calculated status: same
					break;
				}
			}
		}

		return true;
	}
    
    int findBlackPixel(vector<vector<char>>& picture, int target) {
		int result = 0;
		const int m = picture.size();
		const int n = picture[0].size();

		unsigned short* row_black_num = new unsigned short[m] {};
		unsigned short* col_black_num = new unsigned short[n] {};
		bool* col_checked = new bool[n] {};
		char** same_row_status = new char* [m];
		for (int i = 0; i < m; ++i) same_row_status[i] = new char[m] {};

		std::vector<std::tuple<int, int>> indices;
		indices.reserve(m * n);

		for (int i = 0; i < m; ++i)
		{
			for (int j = 0; j < n; ++j)
			{
				if (picture[i][j] == 'B')
				{
					row_black_num[i]++;
					col_black_num[j]++;
					indices.emplace_back(std::make_tuple(i, j));
				}
			}
		}

		for (const auto& index : indices)
		{
			int i = std::get<0>(index);
			int j = std::get<1>(index);
			if (row_black_num[i] == target && col_black_num[j] == target && !col_checked[j])
			{
				// Need some calculation when this column unchecked
				if (checkRowsAreSame(picture, i, j, row_black_num, same_row_status)) result += target;
				col_checked[j] = true;
			}
		}

		delete[] row_black_num;
		delete[] col_black_num;
		delete[] col_checked;
		for (int i = 0; i < m; ++i) delete[] same_row_status[i];
		delete[] same_row_status;

		return result;
	}
};

Submission 5(May be good enough)

I found other’s solution, it looks like easier to read and still performant.

The key idea here is that we can use a map to store rows as strings, and only rows that repeated target numbers are valid. Very clever👍.

class Solution {
public:
    int findBlackPixel(vector<vector<char>>& picture, int target) {
        const int m = picture.size();
		const int n = picture[0].size();

		std::vector<int> col_nums(n);

		for (int i = 0; i < m; ++i)
		{
			for (int j = 0; j < n; ++j)
			{
				if (picture[i][j] == 'B') ++col_nums[j];
			}
		}
			
		std::unordered_map<std::string, int> row_repeated_map;

		for (int i = 0; i < m; ++i)
		{
			row_repeated_map[std::string(picture[i].begin(), picture[i].end())]++;
		}

		int result = 0;
		for (const auto& row : row_repeated_map)
		{
			if (row.second != target) continue;
			int row_num = 0;
			int valid_col_num = 0;
			for (int j = 0; j < row.first.size(); ++j)
			{
				if (row.first[j] == 'B')
				{
					row_num++;
					if (col_nums[j] == target) valid_col_num++;
				}
			}
			if (row_num == target) result += valid_col_num * target;
		}
		return result;
    }
};
Post Views: 227

hyl3d

Leave a Reply

Your email address will not be published. Required fields are marked *

css.php