1. Runtime Distribution

2. Submission Details

3. Description

Given a non-empty 2D matrix matrix and an integer k, find the max sum of a rectangle in the matrix such that its sum is no larger than k.

What is the maximum number of envelopes can you Russian doll? (put one inside other)

4. Example

Given matrix = [
[1, 0, 1],
[0, -2, 3]
]
k = 2

5. Code

public int maxSumSubmatrix(int[][] matrix, int k) {

    int rowLength = matrix.length, colLength = matrix[0].length;

    int result = Integer.MIN_VALUE;

    int[] prefixSum = new int[rowLength + 1];

    for (int i = 0; i < colLength; i++) {

        int[] rowSum = new int[rowLength];
        for (int j = i; j < colLength; j++) {

            for (int r = 0; r < rowLength; r++) {
                rowSum[r] += matrix[r][j];
                prefixSum[r + 1] = prefixSum[r] + rowSum[r];
            }

            result = Math.max(result, mergeSort(prefixSum, 0, rowLength + 1, k));
            if (result == k) {
                return k;
            }
        }
    }
    return result;
}

private static int mergeSort(int[] prefixSum, int l, int r, int sum) {

    if (l + 1 == r) {
        return Integer.MIN_VALUE;
    }

    int mid = l + ((r - l) >> 1);

    int result = mergeSort(prefixSum, l, mid, sum);

    if (result == sum) {
        return sum;
    }

    result = Math.max(result, mergeSort(prefixSum, mid, r, sum));

    if (result == sum) {
        return sum;
    }

    int[] mergedArray = new int[r - l];

    int index = 0, k = mid;
    for (int i = l, j = mid; i < mid; i++) {
        while (j < r && prefixSum[j] - prefixSum[i] <= sum)
            j++;
        if (j - 1 >= mid) {
            result = Math.max(result, prefixSum[j - 1] - prefixSum[i]);
            if (result == sum) {
                return sum;
            }
        }

        while (k < r && prefixSum[k] < prefixSum[i]) {
            mergedArray[index++] = prefixSum[k++];
        }

        mergedArray[index++] = prefixSum[i];
    }

    while (k < r){
        mergedArray[index++] = prefixSum[k++];
    }

    System.arraycopy(mergedArray, 0, prefixSum, l, index);

    return result;
}

6.Test

import org.junit.Test;

public class LeetCode0363_1 {

    public int maxSumSubmatrix(int[][] matrix, int k) {

        int rowLength = matrix.length, colLength = matrix[0].length;

        int result = Integer.MIN_VALUE;

        int[] prefixSum = new int[rowLength + 1];

        for (int i = 0; i < colLength; i++) {

            int[] rowSum = new int[rowLength];
            for (int j = i; j < colLength; j++) {

                for (int r = 0; r < rowLength; r++) {
                    rowSum[r] += matrix[r][j];
                    prefixSum[r + 1] = prefixSum[r] + rowSum[r];
                }

                result = Math.max(result, mergeSort(prefixSum, 0, rowLength + 1, k));
                if (result == k) {
                    return k;
                }
            }
        }
        return result;
    }

    private static int mergeSort(int[] prefixSum, int l, int r, int sum) {

        if (l + 1 == r) {
            return Integer.MIN_VALUE;
        }

        int mid = l + ((r - l) >> 1);

        int result = mergeSort(prefixSum, l, mid, sum);

        if (result == sum) {
            return sum;
        }

        result = Math.max(result, mergeSort(prefixSum, mid, r, sum));

        if (result == sum) {
            return sum;
        }

        int[] mergedArray = new int[r - l];

        int index = 0, k = mid;
        for (int i = l, j = mid; i < mid; i++) {
            while (j < r && prefixSum[j] - prefixSum[i] <= sum)
                j++;
            if (j - 1 >= mid) {
                result = Math.max(result, prefixSum[j - 1] - prefixSum[i]);
                if (result == sum) {
                    return sum;
                }
            }

            while (k < r && prefixSum[k] < prefixSum[i]) {
                mergedArray[index++] = prefixSum[k++];
            }

            mergedArray[index++] = prefixSum[i];
        }

        while (k < r){
            mergedArray[index++] = prefixSum[k++];
        }

        System.arraycopy(mergedArray, 0, prefixSum, l, index);

        return result;
    }

    @Test
    public void test() {
        int martix[][] = { { 2, 2, -1 } };
        System.out.println(maxSumSubmatrix(martix, 0));
    }

}