LeetCode 1895 | Largest Magic Square | Java | Medium | Matrix & Prefix Sum | CodeByTushu
Description: 🚀 Welcome Back to CodeByTushu!
In today’s video, we solve LeetCode 1895 — Largest Magic Square using Matrix and Prefix Sum in Java.
A magic square is defined as a k x k subgrid where the sum of integers in each row, each column, and both main diagonals are completely identical. Since any single 1 x 1 cell is trivially a magic square, the minimum answer is always 1. To find the largest possible magic square efficiently, we greedily iterate over candidate side lengths k starting from min(m, n) down to 2. The very first valid size k that satisfies the magic square invariant across all rows, columns, and diagonals is guaranteed to be the maximum possible answer.
To verify each candidate k x k subgrid in O(k) time rather than O(k^2), we precalculate row and column prefix sums. For any top-left corner (r, c), any row or column segment sum is computed in O(1). We use the first row sum as our benchmark target, early-exit if any row or column differs, and finally verify both the primary and secondary diagonals. This prefix-accelerated approach provides optimal performance well within the time limits.
🔥 Problem Highlights
✅ Greedy search from maximum side length min(m, n) down to 2
✅ 2D prefix sums for O(1) row and column range sum lookups
✅ Single-pass validation per candidate square in O(k) time
✅ Guaranteed base case of size 1 handled seamlessly
✅ Early-exit pruning as soon as any row or column sum mismatches
✅ Optimal O(min(m, n) * m * n) time and O(m * n) auxiliary space complexity
⏱️ TIMESTAMPS
00:00 Intro
01:09 Problem Understanding & Constraints
02:27 Core Observations & Mathematical Insight
03:23 Algorithmic Approach & Prefix Sum Strategy
04:40 Line-by-Line Java Code Walkthrough
06:07 Step-by-Step Test Run & Dry Run
07:22 Time Complexity Analysis
08:07 Space Complexity Analysis
08:42 Outro & Key Takeaways
📂 Problem Folder & Detailed Documentation:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/tree/main/solutions/January/18-January/1895-Largest-Magic-Square
☕ Java Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/January/18-January/1895-Largest-Magic-Square/Solution.java
🐍 Python Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/January/18-January/1895-Largest-Magic-Square/solution.py
⚡ C++ Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/January/18-January/1895-Largest-Magic-Square/solution.cpp
🌐 JavaScript Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/January/18-January/1895-Largest-Magic-Square/solution.js
🔗 LeetCode Source Code
📌 Admin type the link
🌐 All LeetCode Solutions
📌 https://codebytushu.com/Leetcode/
📱 Join CodeByTushu on WhatsApp
Get coding updates, LeetCode solutions, daily questions and more.
https://whatsapp.com/channel/0029Vb8k5mCDeON2Xwlkxe40
❤️ Donate
📌 https://codebytushu.com/Leetcode/donate.php
🔥 Perfect For
LeetCode Medium Problems
Java DSA Preparation
Matrix Algorithms
2D Prefix Sums
Magic Square Verification
Time Complexity Optimization
Coding Interview Preparation
Problem Solving
🌐 Follow CodeByTushu
▶️ YouTube: https://www.youtube.com/@codebytushu
📸 Instagram: https://instagram.com/codebytushu/
💼 LinkedIn: https://www.linkedin.com/company/codebytushu/
🌍 Website: https://codebytushu.com
🐙 GitHub: https://github.com/CodeByTushu
❤️ Don’t Forget To
👍 Like | 💬 Comment | 🔔 Subscribe
💬 Question of the Day
Why is it optimal to test candidate square sizes k in descending order from min(m, n) down to 2?
1️⃣ It ensures the prefix sum array requires less memory
2️⃣ The first valid k found is guaranteed to be the largest, allowing immediate return
3️⃣ Only descending order allows checking diagonals
4️⃣ Smaller squares cannot be magic squares
#LeetCode1895 #LeetCode #LargestMagicSquare #Java #JavaDSA #Matrix #PrefixSum #DSA #CodingInterview #ProblemSolving #LeetCodeMedium #DailyLeetCode #JavaProgramming #CodeByTushu
👇 Comment the answer below! 🔥 Close description
In today’s video, we solve LeetCode 1895 — Largest Magic Square using Matrix and Prefix Sum in Java.
A magic square is defined as a k x k subgrid where the sum of integers in each row, each column, and both main diagonals are completely identical. Since any single 1 x 1 cell is trivially a magic square, the minimum answer is always 1. To find the largest possible magic square efficiently, we greedily iterate over candidate side lengths k starting from min(m, n) down to 2. The very first valid size k that satisfies the magic square invariant across all rows, columns, and diagonals is guaranteed to be the maximum possible answer.
To verify each candidate k x k subgrid in O(k) time rather than O(k^2), we precalculate row and column prefix sums. For any top-left corner (r, c), any row or column segment sum is computed in O(1). We use the first row sum as our benchmark target, early-exit if any row or column differs, and finally verify both the primary and secondary diagonals. This prefix-accelerated approach provides optimal performance well within the time limits.
🔥 Problem Highlights
✅ Greedy search from maximum side length min(m, n) down to 2
✅ 2D prefix sums for O(1) row and column range sum lookups
✅ Single-pass validation per candidate square in O(k) time
✅ Guaranteed base case of size 1 handled seamlessly
✅ Early-exit pruning as soon as any row or column sum mismatches
✅ Optimal O(min(m, n) * m * n) time and O(m * n) auxiliary space complexity
⏱️ TIMESTAMPS
00:00 Intro
01:09 Problem Understanding & Constraints
02:27 Core Observations & Mathematical Insight
03:23 Algorithmic Approach & Prefix Sum Strategy
04:40 Line-by-Line Java Code Walkthrough
06:07 Step-by-Step Test Run & Dry Run
07:22 Time Complexity Analysis
08:07 Space Complexity Analysis
08:42 Outro & Key Takeaways
📂 Problem Folder & Detailed Documentation:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/tree/main/solutions/January/18-January/1895-Largest-Magic-Square
☕ Java Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/January/18-January/1895-Largest-Magic-Square/Solution.java
🐍 Python Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/January/18-January/1895-Largest-Magic-Square/solution.py
⚡ C++ Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/January/18-January/1895-Largest-Magic-Square/solution.cpp
🌐 JavaScript Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/January/18-January/1895-Largest-Magic-Square/solution.js
🔗 LeetCode Source Code
📌 Admin type the link
🌐 All LeetCode Solutions
📌 https://codebytushu.com/Leetcode/
📱 Join CodeByTushu on WhatsApp
Get coding updates, LeetCode solutions, daily questions and more.
https://whatsapp.com/channel/0029Vb8k5mCDeON2Xwlkxe40
❤️ Donate
📌 https://codebytushu.com/Leetcode/donate.php
🔥 Perfect For
LeetCode Medium Problems
Java DSA Preparation
Matrix Algorithms
2D Prefix Sums
Magic Square Verification
Time Complexity Optimization
Coding Interview Preparation
Problem Solving
🌐 Follow CodeByTushu
▶️ YouTube: https://www.youtube.com/@codebytushu
📸 Instagram: https://instagram.com/codebytushu/
💼 LinkedIn: https://www.linkedin.com/company/codebytushu/
🌍 Website: https://codebytushu.com
🐙 GitHub: https://github.com/CodeByTushu
❤️ Don’t Forget To
👍 Like | 💬 Comment | 🔔 Subscribe
💬 Question of the Day
Why is it optimal to test candidate square sizes k in descending order from min(m, n) down to 2?
1️⃣ It ensures the prefix sum array requires less memory
2️⃣ The first valid k found is guaranteed to be the largest, allowing immediate return
3️⃣ Only descending order allows checking diagonals
4️⃣ Smaller squares cannot be magic squares
#LeetCode1895 #LeetCode #LargestMagicSquare #Java #JavaDSA #Matrix #PrefixSum #DSA #CodingInterview #ProblemSolving #LeetCodeMedium #DailyLeetCode #JavaProgramming #CodeByTushu
👇 Comment the answer below! 🔥 Close description
