algoadvance

Leetcode 840. Magic Squares In Grid

Problem Statement

A 3 x 3 magic square is a 3 x 3 grid filled with distinct numbers from 1 to 9 such that each row, column, and both diagonals all have the same sum.

Given an grid of integers, how many 3 x 3 “magic square” subgrids does grid contain?

You could assume the grid has at least 3 rows and 3 columns.

Clarifying Questions

  1. Constraints on the Grid:
    • Is the grid size always at least 3x3?
    • Are the values in the grid always integers?
  2. Possible Values:
    • Can the elements of the grid be negative or zero, or are they restricted to positive integers?
  3. Output Clarification:
    • Should the count of unique magic squares or simply any qualifying 3x3 grids be considered?

Given the standard constraints of LeetCode, we will assume that the grid dimensions are always valid and the numbers are integers.

Strategy

  1. Sliding Window Approach:
    • Traverse through the grid and check each possible 3x3 subgrid.
    • Validate if the subgrid is a magic square.
  2. Validation of a Magic Square:
    • Check if the subgrid contains distinct numbers from 1 to 9.
    • Verify that each row, each column, and both diagonals have the same sum.

Code

public class MagicSquaresInGrid {
    public int numMagicSquaresInside(int[][] grid) {
        int count = 0;
        
        for (int i = 0; i < grid.length - 2; i++) {
            for (int j = 0; j < grid[0].length - 2; j++) {
                if (isMagicSquare(grid, i, j)) {
                    count++;
                }
            }
        }
        
        return count;
    }
    
    private boolean isMagicSquare(int[][] grid, int row, int col) {
        // Check if all numbers in the 3x3 grid are distinct and between 1 and 9
        boolean[] seen = new boolean[10];
        for (int i = row; i < row + 3; i++) {
            for (int j = col; j < col + 3; j++) {
                if (grid[i][j] < 1 || grid[i][j] > 9 || seen[grid[i][j]]) {
                    return false;
                }
                seen[grid[i][j]] = true;
            }
        }
        
        // Check the sum of rows, columns, and diagonals
        int sum = grid[row][col] + grid[row][col+1] + grid[row][col+2];
        
        // Check rows
        for (int i = 0; i < 3; i++) {
            if (grid[row+i][col] + grid[row+i][col+1] + grid[row+i][col+2] != sum) {
                return false;
            }
        }
        
        // Check columns
        for (int i = 0; i < 3; i++) {
            if (grid[row][col+i] + grid[row+1][col+i] + grid[row+2][col+i] != sum) {
                return false;
            }
        }
        
        // Check diagonals
        if (grid[row][col] + grid[row+1][col+1] + grid[row+2][col+2] != sum ||
            grid[row][col+2] + grid[row+1][col+1] + grid[row+2][col] != sum) {
            return false;
        }
        
        return true;
    }
}

Time Complexity

The time complexity of this algorithm primarily consists of:

Therefore, the overall time complexity is O((n-2) * (m-2)), which in big-O notation simplifies to O(n * m).

This approach ensures that we efficiently check each possible 3x3 subgrid and verify if it is a magic square.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI