Approach #1: Brute Force [Accepted]
Intuition and Algorithm
Let's check every 3x3 grid individually. For each grid, all numbers must be unique and between 1 and 9; plus every row, column, and diagonal must have the same sum.
We could also include an
if grid[r+1][c+1] != 5: continue check into our code, helping us skip over our
for r... for c... for loops faster. This is based on the following observations:
- The sum of the grid must be 45, as it is the sum of the distinct values from 1 to 9.
- Each horizontal and vertical line must add up to 15, as the sum of 3 of these lines equals the sum of the whole grid.
- The diagonal lines must also sum to 15, by definition of the problem statement.
- Adding the 12 values from the four lines that cross the center, these 4 lines add up to 60; but they also add up to the entire grid (45), plus 3 times the middle value. This implies the middle value is 5.
Time Complexity: , where are the number of rows and columns in the given
Space Complexity: .
Analysis written by: @awice.