C++ Program For Given An N X N Square Matrix Find Sum Of All Sub Squares Of Size K X K

This article explores how to calculate the sum of all possible KxK sub-squares within a given NxN square matrix. You will learn different techniques, from a straightforward brute-force method to a more optimized approach using 2D prefix sums, complete with C++ code examples and explanations.

Problem Statement

Given an NxN square matrix and an integer K (where 1 <= K <= N), the problem is to find the sum of all sub-squares of size KxK that can be formed within the matrix. This task is common in areas like image processing, where KxK windows are used for filtering, or in data analysis for calculating local averages.

Example

Consider an NxN matrix where N=3, and we want to find sums of all KxK sub-squares where K=2.

Input Matrix:

1  2  3
4  5  6
7  8  9

For K=2, there will be (N-K+1) * (N-K+1) = (3-2+1) * (3-2+1) = 2 * 2 = 4 sub-squares.

Possible KxK sub-squares (2x2) and their sums:

1. Top-left at (0,0):

1  2
    4  5

Sum = 1 + 2 + 4 + 5 = 12

1. Top-left at (0,1):

2  3
    5  6

Sum = 2 + 3 + 5 + 6 = 16

1. Top-left at (1,0):

4  5
    7  8

Sum = 4 + 5 + 7 + 8 = 24

1. Top-left at (1,1):

5  6
    8  9

Sum = 5 + 6 + 8 + 9 = 28

Output (List of sums): 12, 16, 24, 28

Background & Knowledge Prerequisites

To understand and implement the solutions, familiarity with the following concepts is helpful:

• C++ Basics: Variables, data types, loops (for, while), conditional statements.
• Arrays/Vectors: Declaration, initialization, and manipulation of 1D and 2D arrays (or std::vector in C++).
• Functions: Defining and calling functions.
• Basic Algorithm Analysis: Understanding time and space complexity (Big O notation).

Use Cases

Calculating sub-square sums has various practical applications:

• Image Processing: Used in filters (e.g., mean filter, Gaussian blur) where each pixel's new value is derived from the sum or average of its KxK neighborhood.
• Data Analysis: Finding local trends or aggregates in grid-based data, such as geospatial data, financial grids, or experimental results laid out in a matrix.
• Game Development: For evaluating regions on a game board (e.g., calculating influence, resource density, or specific patterns within a KxK area).
• Computational Geometry: In algorithms that involve scanning a grid or detecting patterns within specific windows.
• Digital Signal Processing: Applying moving average filters to 2D signals.

Solution Approaches

We will explore two primary approaches to solve this problem: a brute-force method and an optimized approach using 2D prefix sums.

Approach 1: Brute-Force Iteration

This approach directly iterates through all possible top-left corners of KxK sub-squares and, for each sub-square, iterates through its elements to calculate the sum.

One-line summary: Iterate through all possible starting points of KxK sub-squares and sum their elements individually.

// Brute-Force Sum of KxK Sub-squares
#include <iostream>
#include <vector>

void findKxKSubsquareSumsBruteForce(const std::vector<std::vector<int>>& matrix, int N, int K) {
    if (K <= 0 || K > N) {
        std::cout << "Invalid K value. K must be between 1 and N." << std::endl;
        return;
    }

    std::cout << "Sums of KxK sub-squares (Brute-Force):" << std::endl;

    // Iterate through all possible top-left corners (i, j) of KxK sub-squares
    // The top-left row 'i' can go from 0 to N-K
    // The top-left column 'j' can go from 0 to N-K
    for (int i = 0; i <= N - K; ++i) {
        for (int j = 0; j <= N - K; ++j) {
            int currentSubsquareSum = 0;
            // Iterate through the elements within the current KxK sub-square
            for (int row = i; row < i + K; ++row) {
                for (int col = j; col < j + K; ++col) {
                    currentSubsquareSum += matrix[row][col];
                }
            }
            std::cout << currentSubsquareSum << " ";
        }
    }
    std::cout << std::endl;
}

int main() {
    // Step 1: Define the matrix and its dimensions
    int N = 3; // Matrix size N x N
    int K = 2; // Sub-square size K x K

    std::vector<std::vector<int>> matrix = {
        {1, 2, 3},
        {4, 5, 6},
        {7, 8, 9}
    };

    // Step 2: Call the brute-force function
    findKxKSubsquareSumsBruteForce(matrix, N, K);

    // Another example
    N = 4;
    K = 3;
    std::vector<std::vector<int>> matrix2 = {
        {1, 1, 1, 1},
        {2, 2, 2, 2},
        {3, 3, 3, 3},
        {4, 4, 4, 4}
    };
    findKxKSubsquareSumsBruteForce(matrix2, N, K);

    return 0;
}

Run

Sample Output:

Sums of KxK sub-squares (Brute-Force):
12 16 24 28 
Sums of KxK sub-squares (Brute-Force):
18 27 36

Stepwise explanation:

1. Outer Loops ( i, j): These loops iterate through all possible top-left coordinates (i, j) for a KxK sub-square. The row i goes from 0 to N-K, and the column j goes from 0 to N-K. This ensures that the entire KxK sub-square fits within the NxN matrix.
2. Inner Loops ( row, col): For each (i, j) combination, these nested loops iterate through all elements within the current KxK sub-square.

• row goes from i to i + K - 1.
• col goes from j to j + K - 1.

1. Summation: The value of each element matrix[row][col] is added to currentSubsquareSum.
2. Output: After summing all elements for a sub-square, currentSubsquareSum is printed.

Time Complexity: There are (N-K+1) * (N-K+1) total KxK sub-squares. For each sub-square, we iterate through K * K elements. So, the total time complexity is approximately O((N-K+1)^2 * K^2), which simplifies to O(N^2 * K^2) in the worst case (when K is close to N).

Approach 2: Optimized using 2D Prefix Sums

This approach pre-computes a 2D prefix sum (or integral image) array. This array allows calculating the sum of any rectangular region in the original matrix in O(1) time after an initial O(N^2) pre-computation.

One-line summary: Create a 2D prefix sum matrix to quickly query the sum of any KxK sub-square in constant time.

// Optimized Sum of KxK Sub-squares using 2D Prefix Sums
#include <iostream>
#include <vector>

void findKxKSubsquareSumsOptimized(const std::vector<std::vector<int>>& matrix, int N, int K) {
    if (K <= 0 || K > N) {
        std::cout << "Invalid K value. K must be between 1 and N." << std::endl;
        return;
    }

    // Step 1: Create a 2D prefix sum (or integral image) matrix
    // sumMatrix[i][j] will store sum of all elements in matrix[0...i-1][0...j-1]
    std::vector<std::vector<int>> sumMatrix(N + 1, std::vector<int>(N + 1, 0));

    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            sumMatrix[i + 1][j + 1] = matrix[i][j] + sumMatrix[i][j + 1] + sumMatrix[i + 1][j] - sumMatrix[i][j];
        }
    }

    std::cout << "Sums of KxK sub-squares (Optimized with Prefix Sums):" << std::endl;

    // Step 2: Iterate through all possible top-left corners (i, j) of KxK sub-squares
    // and use the prefix sum matrix to find the sum in O(1)
    for (int i = 0; i <= N - K; ++i) {
        for (int j = 0; j <= N - K; ++j) {
            // The bottom-right corner of the current KxK sub-square is (i + K - 1, j + K - 1)
            // In sumMatrix, these correspond to (i+K, j+K)
            // The top-left corner (i,j) in original matrix corresponds to (i,j) in formula
            
            // Formula for sum of rectangle from (r1, c1) to (r2, c2) using sumMatrix:
            // sum = sumMatrix[r2+1][c2+1] - sumMatrix[r1][c2+1] - sumMatrix[r2+1][c1] + sumMatrix[r1][c1]
            
            int r1 = i;
            int c1 = j;
            int r2 = i + K - 1;
            int c2 = j + K - 1;

            int currentSubsquareSum = sumMatrix[r2 + 1][c2 + 1] - sumMatrix[r1][c2 + 1] - sumMatrix[r2 + 1][c1] + sumMatrix[r1][c1];
            std::cout << currentSubsquareSum << " ";
        }
    }
    std::cout << std::endl;
}

int main() {
    // Step 1: Define the matrix and its dimensions
    int N = 3; // Matrix size N x N
    int K = 2; // Sub-square size K x K

    std::vector<std::vector<int>> matrix = {
        {1, 2, 3},
        {4, 5, 6},
        {7, 8, 9}
    };

    // Step 2: Call the optimized function
    findKxKSubsquareSumsOptimized(matrix, N, K);

    // Another example
    N = 4;
    K = 3;
    std::vector<std::vector<int>> matrix2 = {
        {1, 1, 1, 1},
        {2, 2, 2, 2},
        {3, 3, 3, 3},
        {4, 4, 4, 4}
    };
    findKxKSubsquareSumsOptimized(matrix2, N, K);

    return 0;
}

Run

Sample Output:

Sums of KxK sub-squares (Optimized with Prefix Sums):
12 16 24 28 
Sums of KxK sub-squares (Optimized with Prefix Sums):
18 27 36

Stepwise explanation:

1. Construct sumMatrix:

• A sumMatrix of size (N+1) x (N+1) is created, initialized with zeros. This padding simplifies boundary conditions.
• sumMatrix[i][j] stores the sum of all elements in the original matrix from (0,0) to (i-1, j-1).
• The formula for building sumMatrix is: sumMatrix[i+1][j+1] = matrix[i][j] + sumMatrix[i][j+1] + sumMatrix[i+1][j] - sumMatrix[i][j]. This accounts for overlapping sums efficiently. This step takes O(N^2) time.

1. Calculate Sub-square Sums:

• Iterate through all possible top-left coordinates (i, j) of KxK sub-squares, similar to the brute-force method.
• For each sub-square, determine its top-left (r1, c1) and bottom-right (r2, c2) coordinates in the *original* matrix.
• Use the sumMatrix to find the sum of this KxK sub-square in O(1) time using the formula:

sum = sumMatrix[r2+1][c2+1] - sumMatrix[r1][c2+1] - sumMatrix[r2+1][c1] + sumMatrix[r1][c1].

• This formula effectively calculates the sum of the rectangle bounded by (r1, c1) and (r2, c2) by including the sum up to (r2, c2), subtracting the sums of the regions above and to the left of the desired rectangle (which were double-counted), and adding back the sum of the top-left overlapping region (which was subtracted twice).

Time Complexity:

• Building the sumMatrix: O(N^2)
• Calculating sums for all KxK sub-squares: There are (N-K+1) * (N-K+1) sub-squares, and each sum takes O(1) time. So, O((N-K+1)^2) which simplifies to O(N^2).
• Total time complexity: O(N^2).

Space Complexity: O(N^2) for the sumMatrix.

Conclusion

Finding the sum of all KxK sub-squares in an NxN matrix can be approached in several ways. The brute-force method is intuitive but becomes computationally expensive for larger matrices or sub-squares, with a time complexity of O(N^2 * K^2). A significantly more efficient solution leverages the concept of 2D prefix sums, allowing for the calculation of any sub-rectangle sum in O(1) time after an initial O(N^2) pre-computation. This optimized approach offers a total time complexity of O(N^2), making it much more suitable for larger datasets.

Summary

• The problem involves calculating sums for all KxK sub-regions within an NxN matrix.
• Brute-Force Approach: Iterates through each potential sub-square and sums its elements directly.
• Time Complexity: O(N^2 * K^2)
• Space Complexity: O(1) (excluding input matrix)
• 2D Prefix Sums Approach: Pre-computes a sumMatrix where each cell stores the sum of elements from (0,0) to the current cell in the original matrix.
• Sum of any KxK sub-square can then be found in O(1) using the sumMatrix.
• Time Complexity: O(N^2) (O(N^2) for pre-computation + O(N^2) for querying all sub-squares)
• Space Complexity: O(N^2) for the sumMatrix.
• The 2D prefix sums method is generally preferred for its efficiency, especially when N or K are large.