0363. Max Sum of Rectangle No Larger Than K

https://leetcode.com/problems/max-sum-of-rectangle-no-larger-than-k

Description

Given an m x n matrix matrix and an integer k, return the max sum of a rectangle in the matrix such that its sum is no larger than k.

It is guaranteed that there will be a rectangle with a sum no larger than k.

Example 1:

**Input:** matrix = [[1,0,1],[0,-2,3]], k = 2
**Output:** 2
**Explanation:** Because the sum of the blue rectangle [[0, 1], [-2, 3]] is 2, and 2 is the max number no larger than k (k = 2).

Example 2:

**Input:** matrix = [[2,2,-1]], k = 3
**Output:** 3

Constraints:

• m == matrix.length

• n == matrix[i].length

• 1 <= m, n <= 100

• -100 <= matrix[i][j] <= 100

• -105 <= k <= 105

Follow up: What if the number of rows is much larger than the number of columns?

ac

class Solution {
    public int maxSumSubmatrix(int[][] matrix, int k) {
        // edge cases

        int row = matrix.length, col = matrix[0].length;
        int res = Integer.MIN_VALUE;

        // 1) 2 pointers, iterate each col -> get sum array;
        for (int l = 0; l < col; l++) {
            int[] nums = new int[row];
            for (int r = l; r < col; r++) {
                for (int i = 0; i < row; i++) nums[i] += matrix[i][r];

                // 3) can use Kadane's algorithm to early stop
                int currMax = Integer.MIN_VALUE, globalMax = Integer.MIN_VALUE;
                for (int i = 0; i < nums.length; i++) {
                    currMax = Math.max(currMax + nums[i], nums[i]);
                    globalMax = Math.max(globalMax, currMax);
                }
                if (globalMax <= k) {
                    res = Math.max(res, globalMax);
                } else {
                    // 2) perform maxSum <= k calculation. TreeSet to help binary search find ceiling(currSum - k)
                    TreeSet<Integer> tset = new TreeSet<>();
                    tset.add(0);

                    int currSum = 0;
                    for (int n : nums) {
                        currSum += n;
                        // find currSum - oldSum <= k, so it's the ceiling of currSum - k
                        Integer oldSum = tset.ceiling(currSum - k);
                        if (oldSum != null) res = Math.max(res, currSum - oldSum);
                        tset.add(currSum);
                    }
                }
                if (res == k) return k; // earlier return
            }
        }

        return res;
    }
}

/*
convert to 1D array maxSum. 1) 2 pointers, iterate each col -> get sum array; 2) perform maxSum <= k calculation. TreeSet to help binary search find ceiling(currSum - k)  3) can use Kadane's algorithm to early stop
*/