LeetCode POTD 1895 – Largest Magic Square

📂 Source Code:
https://github.com/RakeshMundel/LeetCode-POTD-Solutions
In this video, we solve LeetCode Problem 1897: Largest Magic Square step by step using an optimized prefix-sum based approach.

🧠 Problem Overview
🔹 You are given an m × n integer grid
🔹 A k × k magic square is a grid where:
All row sums are equal
All column sums are equal
Both diagonal sums are equal
🔹 Numbers do not need to be distinct
🔹 Every 1 × 1 grid is trivially a magic square

🔹 Your task is to find the largest possible size k of a magic square inside the grid.

💡 Key Insight
To efficiently check all possible subgrids:
Use prefix sums to compute row and column sums in O(1) time
Try all possible square sizes k from largest to smallest
For each candidate square:
Verify all row sums
Verify all column sums
Verify both diagonals
As soon as a valid magic square is found, we return its size.
🚀 Approach Used
Precompute row-wise and column-wise prefix sums
Iterate over all possible top-left positions
Check each k × k subgrid efficiently
Track the maximum valid size
This avoids recomputing sums repeatedly and keeps the solution efficient.
⏱️ Time & Space Complexity
Time Complexity: O(m × n × min(m, n))
Space Complexity: O(m × n)
(Prefix sum storage)
📌 Perfect for:

Matrix & prefix sum problems

LeetCode POTD practice

Coding interview preparation

Understanding 2D optimization techniques

👍 Like, Share & Subscribe for more LeetCode + DSA tutorials
💬 Drop a comment if you want a visual explanation of magic square validation!
#LeetCode #LeetCode1897 #POTD #MagicSquare #PrefixSum #Matrix #DSA #CodingInterview #Java #FAANG #CareerYacht

Видео LeetCode POTD 1895 – Largest Magic Square канала CareerYacht