The explanation for this problem is wrong.Sir has considered only horizontal line but we have to take account of vertical line also?Please explain
The explanation for this problem is wrong.Sir has considered only horizontal line but we have to take account of vertical line also?
Hey @sahazeer123 the explanation is correct!
First build prefix[i] which stores number of white rows till ith row.
also make left[i] and right[i] which stores index of leftmost and rightmost black cell in ith row.
See lets place eraser at top left (0,0) to (k-1,k-1), now
calculate how many rows turns white because of this in O(NK),
now if you move eraser one row down, you have to update the answer,
to update answer you can simply know whether eraser makes current row white if left[i]>=start_of_eraser and right[i]<=end_of_eraser.
So you choose the eraser start as 0, move vertically down, then choose eraser start as 1 and again move vertically down and so on.
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.