chepestb's blog

How to count the total number of such squares whose boundary consists of ones only?
By chepestb, history, 2 years ago, In English

I am stuck on problem to count total number of such squares whose boundary consists of ones only in binary matrix.Please help. Problem Link:

  • Vote: I like it
  • +9
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

link of video solution of similar kind of question

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

On a surface, the idea is to work on each diagonal seperately as each diagonal will have the top leftmost and bottom rightmost point of a square. Now for each element,if it's the top leftmost element, then the bottom-rightmost element will lie in some range,Same thing holds for bottom rightmost elements. It reduces the problem to finding total number of relevant intersections of ranges in each diagonal which can be done in nlogn for each diagonal.

→ Reply