513. Maximum Side Length of a Square with Sum <= Threshold

Given a matrix of non-negative integers and a threshold, return the maximum side length of a square sub-matrix whose element sum is less than or equal to the threshold (return 0 if no such square exists). The input is JSON {matrix, threshold}. Use a 2D prefix sum and binary search on the side length.

Input: JSON {matrix, threshold}.

Output: Integer — the maximum square side length.

Examples

Input: {"matrix":[[1,1,3,2,4,3,2],[1,1,3,2,4,3,2],[1,1,3,2,4,3,2]],"threshold":4}
Output: 2
Explanation: A 2x2 square of ones sums to 4.

Input: {"matrix":[[2,2,2,2,2]],"threshold":1}
Output: 0
Explanation: Even a single cell exceeds the threshold.

Input: {"matrix":[[1]],"threshold":1}
Output: 1
Explanation: Single cell fits.

Constraints

• 1<=rows,cols<=300
• 0<=value<=10^4
• 0<=threshold<=10^9

Asked by