The Sum of all Submatrices with Example

The sum of all submatrices is beneficial in various scenarios, such as solving problems in competitive programming, data analysis, and certain algorithms in image processing or computer vision.

Understanding this concept can help in optimizing algorithms and reducing computational complexity in such tasks.

Here’s a breakdown of why the sum of all submatrices might be important

Competitive Programming and Algorithmic Challenges
Data Analysis
Image Processing
Optimization in Matrix Operations

Let’s understand with an example.

Problem Description

Given a 2D Matrix A of dimensions N*N, we need to return the sum of all possible submatrices.

Problem Constraints

1 <= N <=30 0 <= A[i][j] <= 10

Input Format

Single argument representing a 2-D array A of size N x N.

Output Format

Return an integer denoting the sum of all possible submatrices in the given matrix.

Example Input & Output

Input 1:
A = [ [1, 1]
      [1, 1] ]
Input 2:
A = [ [1, 2]
      [3, 4] ]
      

Output 1:
16
Output 2:
40

Output

Sum of all Submatrices in JAVA

public class Solution {
    public int solve(int[][] A) {
        int n = A.length;
        int totalSum = 0;
 
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                totalSum += A[i][j] * (i + 1) * (j + 1) * (n - i) * (n - j);
            }
        }
 
        return totalSum;
    }
}

Sum of all Submatrices in Python

def solve(A):
    n = len(A)
    total_sum = 0
 
    for i in range(n):
        for j in range(n):
            total_sum += A[i][j] * (i + 1) * (j + 1) * (n - i) * (n - j)
 
    return total_sum

Sum of all Submatrices in JavaScript

function solve(A) {
    const n = A.length;
    let totalSum = 0;
 
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            totalSum += A[i][j] * (i + 1) * (j + 1) * (n - i) * (n - j);
        }
    }
 
    return totalSum;
}