algoadvance

Leetcode 840. Magic Squares In Grid

Problem Statement

You are given a 2D array of integers grid of size m x n. A magic square is a 3 x 3 grid filled with distinct numbers from 1 to 9 such that each row, each column, and both diagonals all have the same sum.

Your task is to count all the 3 x 3 magic square sub-grids in the given grid.

Example:

Input: grid = [
  [4,3,8,4],
  [9,5,1,9],
  [2,7,6,2]
]
Output: 1

Clarifying Questions

  1. Are the elements in the grid guaranteed to be integers within the range 1 to 9?
    • No, the elements can be any integer.
  2. Should the grid count only distinct sub-grids?
    • No, we should count every 3x3 sub-grid independently.

Strategy

  1. Identify 3x3 Sub-Grids: Traverse the grid and extract every possible 3x3 sub-grid.
  2. Check Magic Square Conditions:
    • Each 3x3 sub-grid should contain all the numbers from 1 to 9 exactly once.
    • The sum of each row, each column, and both diagonals should be the same.

Code

#include <vector>
#include <unordered_set>

bool isMagicSquare(std::vector<std::vector<int>>& grid, int row, int col) {
    std::unordered_set<int> nums;
    int sum = grid[row][col] + grid[row][col+1] + grid[row][col+2];
    
    // Check if numbers are distinct and between 1 and 9
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j) {
            int num = grid[row + i][col + j];
            if (num < 1 || num > 9 || nums.count(num)) {
                return false;
            }
            nums.insert(num);
        }
    }

    // Check the sums of rows, columns, and diagonals
    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;

    for (int j = 0; j < 3; ++j)
        if (grid[row][col+j] + grid[row+1][col+j] + grid[row+2][col+j] != sum)
            return false;

    if (grid[row][col] + grid[row+1][col+1] + grid[row+2][col+2] != sum)
        return false;

    if (grid[row][col+2] + grid[row+1][col+1] + grid[row+2][col] != sum)
        return false;

    return true;
}

int numMagicSquaresInside(std::vector<std::vector<int>>& grid) {
    int m = grid.size(), n = grid[0].size();
    int count = 0;
    
    for (int i = 0; i <= m - 3; ++i) {
        for (int j = 0; j <= n - 3; ++j) {
            if (isMagicSquare(grid, i, j)) {
                ++count;
            }
        }
    }
    return count;
}

Time Complexity

This solution effectively covers all possible 3x3 sub-grids, verifies the necessary conditions, and counts the number of magic squares.

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