Interview Question
- 0of 0 votes
AnswersGiven a matrix of 0's and 1's find the smallest number of groups made of 1's, where one group can cover up to two 1's at the same time vertically or horizontally.
- matk100.100 October 31, 2018
01111
11011
00100
The matrix above has 5 of such groups. I've seen similar questions but there the question was about groups of adjacent 1's. Here the groups are limited.
Another question how it would change, if the group wasn't limited to two but to given k - number of 1's vertically or horizontally. The time complexity should be the most efficient.
My idea here i to iterate through rows and when we find a 1, check it's bottom and right neighbour. If it has a right but no bottom, a group is made and we skip the right neighbour as it is already in a group. When the checked 1 has a bottom but no right, we make a group of them and we can skip checking the right as well i think.| Report Duplicate | Flag | PURGE
Algorithm