Facebook Pixel

1895. Largest Magic Square

MediumArrayMatrixPrefix Sum
Leetcode Link

Problem Description

You are given an m x n integer grid and need to find the largest magic square that can be formed within this grid.

A magic square is a square grid where:

  • All row sums are equal
  • All column sums are equal
  • Both diagonal sums are equal (main diagonal from top-left to bottom-right, and anti-diagonal from top-right to bottom-left)
  • The integers in the magic square don't need to be distinct

For example, a 3 x 3 magic square must have all 3 rows summing to the same value, all 3 columns summing to that same value, and both diagonals also summing to that value.

Every 1 x 1 grid is considered a magic square by default.

Your task is to find the maximum side length k of a magic square that can be found as a subgrid within the given grid. The magic square must be formed by consecutive rows and columns from the original grid.

Example scenarios:

  • If you have a 4 x 5 grid, you could potentially find magic squares of size 1 x 1, 2 x 2, 3 x 3, or 4 x 4 (limited by the smaller dimension)
  • You need to check all possible square subgrids and determine which ones are magic squares
  • Return the side length of the largest magic square found

The solution uses prefix sums to efficiently calculate row and column sums, then checks squares from largest to smallest size (starting from min(m, n) down to 1) to find the first valid magic square, which will be the largest.

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

Intuition

The key insight is that we need to efficiently check many potential square subgrids to determine if they're magic squares. A brute force approach would repeatedly sum rows, columns, and diagonals for each candidate square, leading to redundant calculations.

To optimize this, we can precompute prefix sums. For any subarray, the sum can be calculated in O(1) time using the formula: sum[i to j] = prefixSum[j+1] - prefixSum[i]. This principle extends to 2D grids where we maintain separate prefix sums for rows and columns.

Why search from largest to smallest size? Since we want the maximum side length, once we find a valid magic square of size k, we can immediately return k without checking smaller sizes. This greedy approach saves time - we start with k = min(m, n) (the largest possible square that fits) and decrease k until we find a valid magic square.

For each candidate square with top-left corner (x1, y1) and bottom-right corner (x2, y2), we need to verify:

  1. All rows have the same sum
  2. All columns have the same sum
  3. Both diagonals have the same sum
  4. All these sums are equal to each other

We use the first row's sum as our reference value val. Then we check if all other rows, all columns, and both diagonals equal this value. The prefix sums make row and column checks O(1) per row/column. The diagonals still need O(k) time to sum since they're not consecutive elements, but there are only two diagonals to check.

This approach transforms a potentially O(m * n * k^3) brute force solution into an O(m * n * k^2) solution, where the k^2 comes from checking all rows and columns of a k x k square.

Learn more about Prefix Sum patterns.

Solution Approach

The implementation consists of three main parts: preprocessing prefix sums, checking if a square is magic, and searching for the largest valid square.

1. Building Prefix Sums:

We create two 2D arrays rowsum and colsum of size (m+1) x (n+1) to store cumulative sums:

  • rowsum[i][j] = sum of elements from grid[i-1][0] to grid[i-1][j-1] (row-wise prefix sum)
  • colsum[i][j] = sum of elements from grid[0][j-1] to grid[i-1][j-1] (column-wise prefix sum)
for i in range(1, m + 1):
    for j in range(1, n + 1):
        rowsum[i][j] = rowsum[i][j - 1] + grid[i - 1][j - 1]
        colsum[i][j] = colsum[i - 1][j] + grid[i - 1][j - 1]

The indices are shifted by 1 to handle boundary cases elegantly (avoiding negative indices).

2. Checking Magic Square Validity:

The check(x1, y1, x2, y2) function verifies if the square from (x1, y1) to (x2, y2) is magic:

  • First, calculate the sum of the first row as reference: val = rowsum[x1 + 1][y2 + 1] - rowsum[x1 + 1][y1]

  • Check all rows have the same sum:

for i in range(x1 + 1, x2 + 1):
    if rowsum[i + 1][y2 + 1] - rowsum[i + 1][y1] != val:
        return False
  • Check all columns have the same sum:
for j in range(y1, y2 + 1):
    if colsum[x2 + 1][j + 1] - colsum[x1][j + 1] != val:
        return False
  • Check the main diagonal (top-left to bottom-right):
s, i, j = 0, x1, y1
while i <= x2:
    s += grid[i][j]
    i += 1
    j += 1
  • Check the anti-diagonal (top-right to bottom-left):
s, i, j = 0, x1, y2
while i <= x2:
    s += grid[i][j]
    i += 1
    j -= 1

3. Finding the Largest Magic Square:

We iterate through possible square sizes from largest to smallest:

for k in range(min(m, n), 1, -1):

For each size k, we try all possible positions where a k x k square can fit:

i = 0
while i + k - 1 < m:
    j = 0
    while j + k - 1 < n:
        i2, j2 = i + k - 1, j + k - 1
        if check(i, j, i2, j2):
            return k
        j += 1
    i += 1

If no magic square larger than 1 is found, we return 1 (since every single cell is trivially a magic square).

The time complexity is O(m * n * min(m,n)^2) where the min(m,n)^2 factor comes from checking all positions for each square size and validating each square in O(k) time.

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through finding the largest magic square in this grid:

grid = [[7, 1, 4, 5, 6],
        [2, 5, 1, 6, 4],
        [1, 5, 4, 3, 2],
        [1, 2, 7, 3, 4]]

Step 1: Build Prefix Sums

We create rowsum and colsum arrays (size 5×6 to handle 0-indexing):

For rowsum[i][j] (cumulative sum along each row):

  • Row 1: [0, 7, 8, 12, 17, 23]
  • Row 2: [0, 2, 7, 8, 14, 18]
  • Row 3: [0, 1, 6, 10, 13, 15]
  • Row 4: [0, 1, 3, 10, 13, 17]

For colsum[i][j] (cumulative sum along each column):

  • Column 1: [0, 7, 9, 10, 11]
  • Column 2: [0, 1, 6, 11, 13]
  • Column 3: [0, 4, 5, 9, 16]
  • And so on...

Step 2: Search from Largest to Smallest

Start with k = min(4, 5) = 4. Check all possible 4×4 squares:

  • Position (0,0) to (3,3): Check the square [[7,1,4,5], [2,5,1,6], [1,5,4,3], [1,2,7,3]]
    • Row sums using prefix: Row 1 = 17-0 = 17, Row 2 = 14-0 = 14 ❌ Not equal!
  • Position (0,1) to (3,4): Check the square [[1,4,5,6], [5,1,6,4], [5,4,3,2], [2,7,3,4]]
    • Row sums: Row 1 = 23-7 = 16, Row 2 = 18-2 = 16, Row 3 = 15-1 = 14 ❌ Not equal!

No 4×4 magic squares found.

Step 3: Try k = 3

Check all possible 3×3 squares:

  • Position (0,0) to (2,2): [[7,1,4], [2,5,1], [1,5,4]]
    • Row sums: 12-0=12, 8-0=8 ❌ Not equal!
  • Position (0,1) to (2,3): [[1,4,5], [5,1,6], [5,4,3]]
    • Row sums: 17-7=10, 14-2=12 ❌ Not equal!
  • Position (1,1) to (3,3): [[5,1,6], [5,4,3], [2,7,3]]
    • Row sums: 14-2=12, 13-1=12, 13-1=12 ✓
    • Column sums: 13-1=12, 16-4=12, 16-4=12 ✓
    • Main diagonal: 5+4+3=12 ✓
    • Anti-diagonal: 6+4+2=12 ✓

Found a 3×3 magic square! Return 3.

The algorithm efficiently finds this by:

  1. Using prefix sums to calculate row/column sums in O(1) time
  2. Starting from the largest possible size to minimize checks
  3. Returning immediately upon finding the first (largest) valid magic square

Solution Implementation

1class Solution:
2    def largestMagicSquare(self, grid: List[List[int]]) -> int:
3        """
4        Find the size of the largest magic square that can be found in the grid.
5        A magic square is a square where all rows, columns, and both diagonals sum to the same value.
6        """
7        rows, cols = len(grid), len(grid[0])
8      
9        # Build prefix sum arrays for efficient range sum queries
10        # row_prefix_sum[i][j] = sum of elements from grid[i-1][0] to grid[i-1][j-1]
11        row_prefix_sum = [[0] * (cols + 1) for _ in range(rows + 1)]
12        # col_prefix_sum[i][j] = sum of elements from grid[0][j-1] to grid[i-1][j-1]
13        col_prefix_sum = [[0] * (cols + 1) for _ in range(rows + 1)]
14      
15        # Populate prefix sum arrays
16        for i in range(1, rows + 1):
17            for j in range(1, cols + 1):
18                row_prefix_sum[i][j] = row_prefix_sum[i][j - 1] + grid[i - 1][j - 1]
19                col_prefix_sum[i][j] = col_prefix_sum[i - 1][j] + grid[i - 1][j - 1]
20
21        def is_magic_square(top_row: int, left_col: int, bottom_row: int, right_col: int) -> bool:
22            """
23            Check if the square defined by corners (top_row, left_col) and (bottom_row, right_col)
24            is a magic square where all rows, columns, and diagonals have the same sum.
25            """
26            # Calculate the target sum using the first row
27            target_sum = row_prefix_sum[top_row + 1][right_col + 1] - row_prefix_sum[top_row + 1][left_col]
28          
29            # Check all rows have the same sum
30            for row in range(top_row + 1, bottom_row + 1):
31                row_sum = row_prefix_sum[row + 1][right_col + 1] - row_prefix_sum[row + 1][left_col]
32                if row_sum != target_sum:
33                    return False
34          
35            # Check all columns have the same sum
36            for col in range(left_col, right_col + 1):
37                col_sum = col_prefix_sum[bottom_row + 1][col + 1] - col_prefix_sum[top_row][col + 1]
38                if col_sum != target_sum:
39                    return False
40          
41            # Check main diagonal (top-left to bottom-right)
42            main_diagonal_sum = 0
43            row, col = top_row, left_col
44            while row <= bottom_row:
45                main_diagonal_sum += grid[row][col]
46                row += 1
47                col += 1
48            if main_diagonal_sum != target_sum:
49                return False
50          
51            # Check anti-diagonal (top-right to bottom-left)
52            anti_diagonal_sum = 0
53            row, col = top_row, right_col
54            while row <= bottom_row:
55                anti_diagonal_sum += grid[row][col]
56                row += 1
57                col -= 1
58            if anti_diagonal_sum != target_sum:
59                return False
60          
61            return True
62
63        # Try square sizes from largest to smallest
64        for square_size in range(min(rows, cols), 1, -1):
65            # Try all possible positions for a square of this size
66            for start_row in range(rows - square_size + 1):
67                for start_col in range(cols - square_size + 1):
68                    end_row = start_row + square_size - 1
69                    end_col = start_col + square_size - 1
70                  
71                    if is_magic_square(start_row, start_col, end_row, end_col):
72                        return square_size
73      
74        # Every 1x1 square is a magic square
75        return 1
76
1class Solution {
2    // Prefix sum arrays for rows and columns
3    private int[][] rowPrefixSum;
4    private int[][] colPrefixSum;
5
6    /**
7     * Finds the largest magic square in the grid.
8     * A magic square has all rows, columns, and both diagonals sum to the same value.
9     * 
10     * @param grid The input 2D grid
11     * @return The side length of the largest magic square
12     */
13    public int largestMagicSquare(int[][] grid) {
14        int rows = grid.length;
15        int cols = grid[0].length;
16      
17        // Initialize prefix sum arrays with extra row/column for easier calculation
18        rowPrefixSum = new int[rows + 1][cols + 1];
19        colPrefixSum = new int[rows + 1][cols + 1];
20      
21        // Build prefix sum arrays
22        // rowPrefixSum[i][j] = sum of elements from grid[i-1][0] to grid[i-1][j-1]
23        // colPrefixSum[i][j] = sum of elements from grid[0][j-1] to grid[i-1][j-1]
24        for (int i = 1; i <= rows; i++) {
25            for (int j = 1; j <= cols; j++) {
26                rowPrefixSum[i][j] = rowPrefixSum[i][j - 1] + grid[i - 1][j - 1];
27                colPrefixSum[i][j] = colPrefixSum[i - 1][j] + grid[i - 1][j - 1];
28            }
29        }
30      
31        // Try all possible square sizes from largest to smallest
32        for (int squareSize = Math.min(rows, cols); squareSize > 1; squareSize--) {
33            // Try all possible top-left corners for current square size
34            for (int topRow = 0; topRow + squareSize - 1 < rows; topRow++) {
35                for (int leftCol = 0; leftCol + squareSize - 1 < cols; leftCol++) {
36                    int bottomRow = topRow + squareSize - 1;
37                    int rightCol = leftCol + squareSize - 1;
38                  
39                    // Check if current square is a magic square
40                    if (isMagicSquare(grid, topRow, leftCol, bottomRow, rightCol)) {
41                        return squareSize;
42                    }
43                }
44            }
45        }
46      
47        // Minimum size is 1 (single cell is always a magic square)
48        return 1;
49    }
50
51    /**
52     * Checks if the square defined by corners is a magic square.
53     * 
54     * @param grid The input grid
55     * @param topRow Top row index of the square
56     * @param leftCol Left column index of the square
57     * @param bottomRow Bottom row index of the square
58     * @param rightCol Right column index of the square
59     * @return true if it's a magic square, false otherwise
60     */
61    private boolean isMagicSquare(int[][] grid, int topRow, int leftCol, 
62                                   int bottomRow, int rightCol) {
63        // Calculate the sum of the first row as reference value
64        int targetSum = rowPrefixSum[topRow + 1][rightCol + 1] - 
65                        rowPrefixSum[topRow + 1][leftCol];
66      
67        // Check if all rows have the same sum
68        for (int row = topRow + 1; row <= bottomRow; row++) {
69            int rowSum = rowPrefixSum[row + 1][rightCol + 1] - 
70                         rowPrefixSum[row + 1][leftCol];
71            if (rowSum != targetSum) {
72                return false;
73            }
74        }
75      
76        // Check if all columns have the same sum
77        for (int col = leftCol; col <= rightCol; col++) {
78            int colSum = colPrefixSum[bottomRow + 1][col + 1] - 
79                         colPrefixSum[topRow][col + 1];
80            if (colSum != targetSum) {
81                return false;
82            }
83        }
84      
85        // Check main diagonal (top-left to bottom-right)
86        int mainDiagonalSum = 0;
87        for (int i = topRow, j = leftCol; i <= bottomRow; i++, j++) {
88            mainDiagonalSum += grid[i][j];
89        }
90        if (mainDiagonalSum != targetSum) {
91            return false;
92        }
93      
94        // Check anti-diagonal (top-right to bottom-left)
95        int antiDiagonalSum = 0;
96        for (int i = topRow, j = rightCol; i <= bottomRow; i++, j--) {
97            antiDiagonalSum += grid[i][j];
98        }
99        if (antiDiagonalSum != targetSum) {
100            return false;
101        }
102      
103        return true;
104    }
105}
106
1class Solution {
2public:
3    int largestMagicSquare(vector<vector<int>>& grid) {
4        int m = grid.size(), n = grid[0].size();  // Fixed: should be grid[0].size() for column count
5      
6        // Prefix sum arrays for rows and columns (1-indexed for easier calculation)
7        vector<vector<int>> rowPrefixSum(m + 1, vector<int>(n + 1));
8        vector<vector<int>> colPrefixSum(m + 1, vector<int>(n + 1));
9      
10        // Build prefix sum arrays
11        // rowPrefixSum[i][j] = sum of elements from grid[i-1][0] to grid[i-1][j-1]
12        // colPrefixSum[i][j] = sum of elements from grid[0][j-1] to grid[i-1][j-1]
13        for (int i = 1; i <= m; ++i) {
14            for (int j = 1; j <= n; ++j) {
15                rowPrefixSum[i][j] = rowPrefixSum[i][j - 1] + grid[i - 1][j - 1];
16                colPrefixSum[i][j] = colPrefixSum[i - 1][j] + grid[i - 1][j - 1];
17            }
18        }
19      
20        // Try squares from largest possible size down to 2x2
21        for (int squareSize = min(m, n); squareSize > 1; --squareSize) {
22            // Try all possible top-left corners for current square size
23            for (int topRow = 0; topRow + squareSize - 1 < m; ++topRow) {
24                for (int leftCol = 0; leftCol + squareSize - 1 < n; ++leftCol) {
25                    int bottomRow = topRow + squareSize - 1;
26                    int rightCol = leftCol + squareSize - 1;
27                  
28                    // Check if current square is a magic square
29                    if (isMagicSquare(grid, rowPrefixSum, colPrefixSum, 
30                                     topRow, leftCol, bottomRow, rightCol)) {
31                        return squareSize;
32                    }
33                }
34            }
35        }
36      
37        // A 1x1 square is always magic
38        return 1;
39    }
40
41private:
42    bool isMagicSquare(vector<vector<int>>& grid, 
43                       vector<vector<int>>& rowPrefixSum, 
44                       vector<vector<int>>& colPrefixSum, 
45                       int topRow, int leftCol, int bottomRow, int rightCol) {
46      
47        // Calculate the target sum using the first row
48        int targetSum = rowPrefixSum[topRow + 1][rightCol + 1] - rowPrefixSum[topRow + 1][leftCol];
49      
50        // Check if all rows have the same sum
51        for (int row = topRow + 1; row <= bottomRow; ++row) {
52            int rowSum = rowPrefixSum[row + 1][rightCol + 1] - rowPrefixSum[row + 1][leftCol];
53            if (rowSum != targetSum) {
54                return false;
55            }
56        }
57      
58        // Check if all columns have the same sum
59        for (int col = leftCol; col <= rightCol; ++col) {
60            int colSum = colPrefixSum[bottomRow + 1][col + 1] - colPrefixSum[topRow][col + 1];
61            if (colSum != targetSum) {
62                return false;
63            }
64        }
65      
66        // Check main diagonal (top-left to bottom-right)
67        int mainDiagonalSum = 0;
68        for (int i = topRow, j = leftCol; i <= bottomRow; ++i, ++j) {
69            mainDiagonalSum += grid[i][j];
70        }
71        if (mainDiagonalSum != targetSum) {
72            return false;
73        }
74      
75        // Check anti-diagonal (top-right to bottom-left)
76        int antiDiagonalSum = 0;
77        for (int i = topRow, j = rightCol; i <= bottomRow; ++i, --j) {
78            antiDiagonalSum += grid[i][j];
79        }
80        if (antiDiagonalSum != targetSum) {
81            return false;
82        }
83      
84        return true;
85    }
86};
87
1/**
2 * Finds the largest magic square in a grid
3 * A magic square has equal sums for all rows, columns, and both diagonals
4 * @param grid - The input 2D number array
5 * @returns The side length of the largest magic square
6 */
7function largestMagicSquare(grid: number[][]): number {
8    const rows: number = grid.length;
9    const cols: number = grid[0].length;
10  
11    // Build prefix sum arrays for rows and columns
12    // rowPrefixSum[i][j] represents the sum of elements from grid[i-1][0] to grid[i-1][j-1]
13    const rowPrefixSum: number[][] = Array.from(
14        { length: rows + 1 }, 
15        () => new Array(cols + 1).fill(0)
16    );
17  
18    // colPrefixSum[i][j] represents the sum of elements from grid[0][j-1] to grid[i-1][j-1]
19    const colPrefixSum: number[][] = Array.from(
20        { length: rows + 1 }, 
21        () => new Array(cols + 1).fill(0)
22    );
23  
24    // Calculate row prefix sums
25    for (let i = 0; i < rows; i++) {
26        rowPrefixSum[i + 1][1] = grid[i][0];
27        for (let j = 1; j < cols; j++) {
28            rowPrefixSum[i + 1][j + 1] = rowPrefixSum[i + 1][j] + grid[i][j];
29        }
30    }
31  
32    // Calculate column prefix sums
33    for (let j = 0; j < cols; j++) {
34        colPrefixSum[1][j + 1] = grid[0][j];
35        for (let i = 1; i < rows; i++) {
36            colPrefixSum[i + 1][j + 1] = colPrefixSum[i][j + 1] + grid[i][j];
37        }
38    }
39  
40    // Search for the largest magic square, starting from the maximum possible size
41    for (let squareSize = Math.min(rows, cols); squareSize > 1; squareSize--) {
42        // Try all possible positions for a square of current size
43        for (let topRow = 0; topRow + squareSize - 1 < rows; topRow++) {
44            for (let leftCol = 0; leftCol + squareSize - 1 < cols; leftCol++) {
45                const bottomRow: number = topRow + squareSize - 1;
46                const rightCol: number = leftCol + squareSize - 1;
47              
48                // Check if the current square is a magic square
49                if (isMagicSquare(grid, rowPrefixSum, colPrefixSum, topRow, leftCol, bottomRow, rightCol)) {
50                    return squareSize;
51                }
52            }
53        }
54    }
55  
56    // A single cell is always a magic square
57    return 1;
58}
59
60/**
61 * Validates if a given square region is a magic square
62 * @param grid - The original grid
63 * @param rowPrefixSum - Row prefix sum array
64 * @param colPrefixSum - Column prefix sum array
65 * @param topRow - Top row index of the square
66 * @param leftCol - Left column index of the square
67 * @param bottomRow - Bottom row index of the square
68 * @param rightCol - Right column index of the square
69 * @returns True if the square is a magic square, false otherwise
70 */
71function isMagicSquare(
72    grid: number[][],
73    rowPrefixSum: number[][],
74    colPrefixSum: number[][],
75    topRow: number,
76    leftCol: number,
77    bottomRow: number,
78    rightCol: number
79): boolean {
80    // Get the sum of the first row as the target sum
81    const targetSum: number = rowPrefixSum[topRow + 1][rightCol + 1] - rowPrefixSum[topRow + 1][leftCol];
82  
83    // Check if all rows have the same sum
84    for (let row = topRow + 1; row <= bottomRow; row++) {
85        const currentRowSum: number = rowPrefixSum[row + 1][rightCol + 1] - rowPrefixSum[row + 1][leftCol];
86        if (targetSum !== currentRowSum) {
87            return false;
88        }
89    }
90  
91    // Check if all columns have the same sum
92    for (let col = leftCol; col <= rightCol; col++) {
93        const currentColSum: number = colPrefixSum[bottomRow + 1][col + 1] - colPrefixSum[topRow][col + 1];
94        if (targetSum !== currentColSum) {
95            return false;
96        }
97    }
98  
99    // Check main diagonal (top-left to bottom-right)
100    let mainDiagonalSum: number = targetSum;
101    for (let i = topRow, j = leftCol; i <= bottomRow; i++, j++) {
102        mainDiagonalSum -= grid[i][j];
103    }
104    if (mainDiagonalSum !== 0) {
105        return false;
106    }
107  
108    // Check anti-diagonal (top-right to bottom-left)
109    let antiDiagonalSum: number = targetSum;
110    for (let i = topRow, j = rightCol; i <= bottomRow; i++, j--) {
111        antiDiagonalSum -= grid[i][j];
112    }
113    if (antiDiagonalSum !== 0) {
114        return false;
115    }
116  
117    return true;
118}
119

Time and Space Complexity

Time Complexity: O(min(m,n) * m * n * min(m,n)) which simplifies to O(m * n * min(m,n)^2)

The analysis breaks down as follows:

  • Building the prefix sum arrays rowsum and colsum takes O(m * n) time
  • The main loop iterates through all possible square sizes from min(m,n) down to 2, which is O(min(m,n)) iterations
  • For each square size k, we check all possible positions where a k×k square can fit:
    • There are O(m * n) possible top-left corners for the square
    • The check function is called for each valid position
  • Inside the check function:
    • Checking all rows takes O(k) time
    • Checking all columns takes O(k) time
    • Checking the main diagonal takes O(k) time
    • Checking the anti-diagonal takes O(k) time
    • Total for check: O(k) where k ≤ min(m,n)
  • Overall: O(min(m,n) * m * n * k) where k ≤ min(m,n), resulting in O(m * n * min(m,n)^2)

Space Complexity: O(m * n)

The space usage comes from:

  • rowsum array: O((m+1) * (n+1)) = O(m * n)
  • colsum array: O((m+1) * (n+1)) = O(m * n)
  • Other variables use constant space O(1)
  • Total space complexity: O(m * n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Off-by-One Errors in Prefix Sum Indexing

The most common pitfall in this solution is mishandling the index mapping between the original grid (0-indexed) and the prefix sum arrays (1-indexed). The prefix sum arrays are intentionally sized as (rows+1) x (cols+1) to avoid boundary checks, but this creates a shift in indexing.

Pitfall Example:

# WRONG: Using grid indices directly with prefix sums
target_sum = row_prefix_sum[top_row][right_col] - row_prefix_sum[top_row][left_col]

# CORRECT: Add 1 to account for the shifted indexing
target_sum = row_prefix_sum[top_row + 1][right_col + 1] - row_prefix_sum[top_row + 1][left_col]

Solution: Always remember that row_prefix_sum[i][j] corresponds to the cumulative sum up to grid[i-1][j-1]. When working with a square from (top_row, left_col) to (bottom_row, right_col) in the grid, use indices shifted by 1 in the prefix sum arrays.

2. Incorrect Square Size Calculation

Another common mistake is incorrectly calculating the ending coordinates when given a square size.

Pitfall Example:

# WRONG: Forgetting to subtract 1 when calculating end position
for square_size in range(min(rows, cols), 1, -1):
    for start_row in range(rows - square_size):  # Missing +1
        end_row = start_row + square_size  # Should be square_size - 1

# CORRECT: Proper boundary calculation
for square_size in range(min(rows, cols), 1, -1):
    for start_row in range(rows - square_size + 1):
        end_row = start_row + square_size - 1

Solution: For a square of size k starting at position (i, j), the ending position should be (i + k - 1, j + k - 1), not (i + k, j + k).

3. Diagonal Sum Calculation Boundary Issues

When calculating diagonal sums manually, it's easy to iterate beyond the square boundaries or miss elements.

Pitfall Example:

# WRONG: Using wrong loop condition for diagonal
row, col = top_row, left_col
while row < bottom_row:  # Should be <=
    main_diagonal_sum += grid[row][col]
    row += 1
    col += 1

# CORRECT: Include the bottom_row in the iteration
while row <= bottom_row:
    main_diagonal_sum += grid[row][col]
    row += 1
    col += 1

Solution: Use <= instead of < when iterating to bottom_row or right_col since these represent inclusive boundaries of the square.

4. Anti-Diagonal Direction Error

The anti-diagonal goes from top-right to bottom-left, requiring column decrement while row increments.

Pitfall Example:

# WRONG: Incrementing both row and column for anti-diagonal
row, col = top_row, right_col
while row <= bottom_row:
    anti_diagonal_sum += grid[row][col]
    row += 1
    col += 1  # Should be col -= 1

# CORRECT: Decrement column while incrementing row
row, col = top_row, right_col
while row <= bottom_row:
    anti_diagonal_sum += grid[row][col]
    row += 1
    col -= 1

Solution: For the anti-diagonal, start at (top_row, right_col) and move by incrementing row and decrementing column.

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

The three-steps of Depth First Search are:

  1. Identify states;
  2. Draw the state-space tree;
  3. DFS on the state-space tree.

Recommended Readings

Prefix Sum

Prefix Sum The prefix sum is an incredibly powerful and straightforward technique Its primary goal is to allow for constant time range sum queries on an array What is Prefix Sum The prefix sum of an array at index i is the sum of all numbers from index 0 to i By

Coding Interview Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https assets algo monster recursion jpg You first call Ben and ask

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More