We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Largest Magic Square

Difficulty: Medium

Problem Description

Given an m x n integer grid, return the size (i.e., the side length k) of the largest magic square that can be found within this grid. A k x k magic square is a k x k grid filled with integers such that every row sum, every column sum, and both diagonal sums are all equal.

Key Insights

  • A magic square of size k must have equal sums for all rows, columns, and both diagonals.
  • A brute force approach would involve checking all possible k x k sub-squares, which can be computationally expensive.
  • We can use prefix sums to efficiently calculate sums for rows and columns.
  • The problem can be solved by iterating from the largest possible k down to 1 to find the first valid magic square.

Space and Time Complexity

Time Complexity: O(m * n * min(m, n)), where m is the number of rows and n is the number of columns. The worst case involves checking every possible k x k square for sums. Space Complexity: O(m + n), primarily for storing prefix sums for rows and columns.

Solution

We can use a brute-force approach combined with prefix sums to determine the validity of potential magic squares. The algorithm involves:

  1. Calculating prefix sums for rows and columns.
  2. Iterating over possible square sizes from the largest to the smallest.
  3. Checking if each k x k square satisfies the magic square conditions using the prefix sums.

Code Solutions

def largestMagicSquare(grid):
    m, n = len(grid), len(grid[0])
    # Create prefix sum arrays
    row_sum = [[0] * (n + 1) for _ in range(m + 1)]
    col_sum = [[0] * (n + 1) for _ in range(m + 1)]
    
    # Fill prefix sum arrays
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            row_sum[i][j] = grid[i - 1][j - 1] + row_sum[i][j - 1]
            col_sum[i][j] = grid[i - 1][j - 1] + col_sum[i - 1][j]
    
    # Function to check if a k x k square is magic
    def isMagic(i, j, k):
        target_sum = sum(grid[i][j:j + k])
        # Check rows and columns
        for r in range(k):
            if sum(grid[i + r][j:j + k]) != target_sum:
                return False
        for c in range(k):
            if sum(grid[i + r][j + c] for r in range(k)) != target_sum:
                return False
        # Check diagonals
        if sum(grid[i + r][j + r] for r in range(k)) != target_sum:
            return False
        if sum(grid[i + r][j + k - 1 - r] for r in range(k)) != target_sum:
            return False
        return True

    # Check all possible sizes
    for k in range(min(m, n), 0, -1):
        for i in range(m - k + 1):
            for j in range(n - k + 1):
                if isMagic(i, j, k):
                    return k
    return 1
← Back to All Questions