Sliding Window Matrix Maximum 558

Question

Given an array of n*n matrix, and a moving matrix window (size k), move the window from top left to bottom right at each iteration, find the maximum sum of the elements inside the window at each moving. Return 0 if the answer does not exist.

Example

For matrix [ [1, 5, 3], [3, 2, 1], [4, 1, 9], ]The moving window size k = 2. return 13.

At first the window is at the start of the array like this

[ [|1, 5|, 3], [|3, 2|, 1], [4, 1, 9], ],get the sum 11; then the window move one step forward.

[ [1, |5, 3|], [3, |2, 1|], [4, 1, 9], ],get the sum 11; then the window move one step forward again.

[ [1, 5, 3], [|3, 2|, 1], [|4, 1|, 9], ],get the sum 10; then the window move one step forward again.

[ [1, 5, 3], [3, |2, 1|], [4, |1, 9|], ],get the sum 13;

So finally, get the maximum from all the sum which is 13.

Challenge: O(n^2) time.

Thoughts:

O(n^2) time->traverse maps of dim O(n^2) -> Dynamic Programming:

1. state function: sum[i][j]: sum of all the elements from (0, i-1) and (0, j-1) and initially set sum[0][0] = 0
2. state transition: sum[i][j] = matrix[i-1][j-1] + sum[i][j-1] + sum[i - 1][j] - sum[i-1][j-1]
3. to get window sum value, we reverse the calculation from step 2 with window size parameter k: window_sum = sum[i][j] - sum[i][j-k] - sum[i-k][j] + sum[i-k][j-k]

Code:

public class Solution {
    /**
     * @param matrix an integer array of n * m matrix
     * @param k an integer
     * @return the maximum number
     */
    public int maxSlidingWindow2(int[][] matrix, int k) {
        // Write your code here
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0 || k > matrix.length || k > matrix[0].length){
            return 0;
        }

        int n = matrix.length;
        int m = matrix[0].length;
        int[][] sum = new int[n + 1][m + 1];

        for(int i = 0; i <= n; i++){
            sum[i][0] = 0;
        }

        for(int j = 1; j <= m; j++){
            sum[0][j] = 0;
        }

        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                sum[i][j] = matrix[i - 1][j - 1] + sum[i][j - 1] + sum[i - 1][j] -sum[i - 1][j - 1];
            }
        }

        int max = Integer.MIN_VALUE;
        for(int i = k; i <= n; i++){
            for(int j = k; j <= m; j++){
                int window= sum[i][j] - sum[i - k][j] - sum[i][j - k] + sum[i - k][j - k];
                max = Math.max(max, window);
            }
        }

        return max;
    }
}

Special Thanks zhengyang2015's gitbook solution