The key is "all the non-blurred pixels are connected in such a way that any horizontal or vertical line drawn between two non-blurred pixels goes only through non-blurred pixels". That means that to check if a square is inside the non-blurred part you only need to check that the four vertexes are inside. Each row i contains a segment [a_i, b_i] of non-blurred pixels. To check whether a square of length k+1 fits on the non-blurred part, denote by m_i = max(a_i, a_{i+k}). You need to check that (i, m_i) (i+k, m_i), (i, m_i+k) (i+k, m_i+k) all belong to the non-blurred parts. This can be done in O(1) time. Thus in O(N) time, you check if a square of side length (k+1) fits.