Find sum of every subarray in 2D array

Question

I'm trying to find the sum of every subarray in a 2D array in Java and store them in a new array. This includes the sums of columns and rows. So far, all I can get down is code that can print out the sum of columns and rows.

I don't care about the complexity. In fact, I want to know the most brute force, obvious answer even if it is O(n^4). I am going to be comparing the subarray sums to a given value to see if that sum exists in the rectangular 2D array.

What I have:

public static void outputArray(int[][] array) {
    for (int i = 0; i < array.length; i++){   
        int sum=0;
        for (int j = 0; j < array[0].length; j++){                
            sum += array[i][j]; 
        }
        System.out.println("Print the sum of rows =" + sum);
    }  

    int colSum=0;
    for(int col=0;col<array[0].length;col++){
        for(int row=0;row<array.length;row++){
            colSum+=array[row][col];
        }
        System.out.println("Sum is "+colSum);
        colSum = 0;
    }
}

Golam Mazid Sajib · Accepted Answer · 2018-07-20 04:43:07Z

If u don't care about complexity && don't want to store the value then u can do it 0(n^6).

public static void outputArray(int[][] array) {
    for(int i = 0; i < array.length; i++){
        for(int j = 0; j< array[i].length; j++){
            for(int k = i; k < array.length; k++){
                for(int l = j; l < array[i].length; l++){
                    System.out.print("["+i+","+j+"]--->"+"["+k+","+l+"]");
                    int sum = 0;
                    for(int x = i; x <= k; x++){
                        for(int y = j; y<= l; y++){
                            sum+=array[x][y];
                        }
                    }
                    System.out.println("--->"+sum);
                }
            }
        }
    }
}

If u do some optimize like store prefix some then u can do it 0(n^4). With more optimization its possible to solve O(n^3).

Collectives™ on Stack Overflow

Find sum of every subarray in 2D array

1 Answer 1

Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Related