Maximum size of square such that all submatrices of that size have sum less than K

Given an N x M matrix of integers and an integer K, the task is to find the size of the maximum square sub-matrix (S x S), such that all square sub-matrices of the given matrix of that size have a sum less than K.

Examples: 

Input: K = 30 
mat[N][M] = {{1, 2, 3, 4, 6}, 
             {5, 3, 8, 1, 2}, 
             {4, 6, 7, 5, 5}, 
             {2, 4, 8, 9, 4} }; 
Output: 2
Explanation:
All Sub-matrices of size 2 x 2 
have sum less than 30

Input : K = 100 
mat[N][M] = { { 1, 2, 3, 4 },
              { 5, 6, 7, 8 }, 
              { 9, 10, 11, 12 }, 
              { 13, 14, 15, 16 } };
Output: 3
Explanation:
All Sub-matrices of size 3 x 3 
have sum less than 100

Naive Approach The basic solution is to choose the size S of the submatrix and find all the submatrices of that size and check that the sum of all sub-matrices is less than the given sum whereas, this can be improved by computing the sum of the matrix using this approach. Therefore, the task will be to choose the maximum size possible and the starting and ending position of every possible sub-matrices. Due to which the overall time complexity will be O(N³).

Below is the implementation of the above approach:

2

• Time complexity: O(N³)
• Auxiliary Space: O(N²)

Efficient Approach: The key observation is, if a square of side s is the maximum size satisfying the condition, then all sizes smaller than it will satisfy the condition. Using this we can reduce our search space at each step by half which is precisely the idea of Binary Search. Below is the illustration of the steps of the approach: 

• Search Space: The search space for this problem will be from [1, min(N, M)]. That is the search space for binary search is defined as –

low = 1
high = min(N, M)

• Next Search Space: In each iteration find the mid of the search space and then Finally, check that all subarrays of that size have the sum less than K. If all subarrays of that size have sum less than K. Then the next search space possible will be in the right of the middle. Otherwise, the next search space possible will be in the left of the middle. That is less than the middle. 
  • Case 1: Condition when the all the subarrays of size mid have sum less than K. Then –

if checkSubmatrix(mat, mid, K):
    low = mid + 1

• Case 2: Condition when the all the subarrays of size mid have sum greater than K. Then –

if not checkSubmatrix(mat, mid, K):
    high = mid - 1

Below is the implementation of the above approach:

2

Performance Analysis: 

• Time Complexity: O(N² * log(N) )
• Auxiliary Space: O(N²)