I am not able to reduce the time complexity to get a valid answer. at best i have been able to reduce the time complexity from the common O((m*n)^2) to O(k*m*n).

The basic solution would be to check all the smaller squares inside the matrix.

i want to know the fastest way to solve the problem. Best time complexity .

You can certainly do away with the factor k. Think in terms of having **extra space** to save your computation results for the next step. Also a major hint is the **use of a queue**.

the answer that you shared is of 0.98 sec and the time limit of the question is 1 sec that is it just somehow got saved. People have solved it in much lesser time than that. I am not able to understand how?

http://www.codechef.com/viewsolution/5607150

^that’s my solution