LeetCode 3546 | Equal Sum Grid Partition I | Java | Medium | Matrix Partitioning | CodeByTushu
Description: 🚀 Welcome Back to CodeByTushu!
In today’s video, we solve LeetCode 3546 — Equal Sum Grid Partition I using Prefix Sum and Matrix in Java.
We are given an m x n matrix of positive integers. We need to determine if we can make either one horizontal or one vertical cut such that both resulting subgrids are non-empty and have equal sums. For two sections to have identical sums, each section must sum to exactly half of the total sum of all matrix elements.
If the total sum of the grid is odd, an equal integer split is immediately impossible, so we can return false upfront. Otherwise, we calculate the target sum as totalSum / 2. We then evaluate horizontal cuts by accumulating prefix row sums up to row m - 2 and vertical cuts by accumulating prefix column sums up to column n - 2. If any accumulated prefix sum matches our target, we return true, giving an optimal O(m * n) time and O(m + n) auxiliary space complexity.
🔥 Problem Highlights
✅ Total Sum Parity Check: Immediately prunes odd total sums as impossible to partition equally
✅ Row & Column Prefix Sweeps: Evaluates all candidate horizontal cuts and vertical cuts independently
✅ Non-Empty Section Guarantee: Tests cuts only between 0 and m - 2 (for rows) and 0 and n - 2 (for columns)
✅ 64-Bit Integer Precision: Safely accumulates elements into 64-bit longs to handle matrix sums up to 10^10
✅ Grid Dimension Flexibility: Handles single-row or single-column grids without out-of-bounds indexing
✅ Optimal Complexity: Operates in O(m * n) time complexity and O(m + n) auxiliary space
⏱️ TIMESTAMPS
00:00 Intro & Daily Challenge Overview
01:22 Problem Understanding & Cut Constraints
02:57 Key Insights: Parity Filtering & 64-Bit Range
04:48 Algorithmic Strategy: Row/Column Sum Prefix Verification
06:30 Clean Java Solution Walkthrough Line by Line
07:57 Dry Run & Step-by-Step Example Walkthrough
10:08 Time Complexity Analysis (O(M × N) - 3 ms, Beats 99.2%)
11:25 Space Complexity Analysis (O(M + N) Auxiliary Space)
12:31 Outro & Resources
📂 Problem Folder & Detailed Documentation:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/tree/main/solutions/March/25-March/3546-Equal-Sum-Grid-Partition-I
☕ Java Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/March/25-March/3546-Equal-Sum-Grid-Partition-I/Solution.java
🐍 Python Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/March/25-March/3546-Equal-Sum-Grid-Partition-I/solution.py
⚡ C++ Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/March/25-March/3546-Equal-Sum-Grid-Partition-I/solution.cpp
🌐 JavaScript Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/March/25-March/3546-Equal-Sum-Grid-Partition-I/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
Prefix Sums on Matrices
Grid Partitioning Patterns
Parity Invariants
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
If the total sum of all elements in the grid is an odd number, why can we immediately return false?
1️⃣ Because all elements are positive integers, two equal sections must each have an integer sum of totalSum / 2, which is impossible if totalSum is odd
2️⃣ Because horizontal cuts cannot be performed on odd-sized matrices
3️⃣ Because the problem requires the matrix to be symmetric
4️⃣ Because 64-bit integers cannot divide odd numbers
#LeetCode3546 #LeetCode #EqualSumGridPartitionI #Java #JavaDSA #PrefixSum #Matrix #Array #DSA #CodingInterview #ProblemSolving #LeetCodeMedium #DailyLeetCode #JavaProgramming #CodeByTushu
👇 Comment the answer below! 🔥 Close description
In today’s video, we solve LeetCode 3546 — Equal Sum Grid Partition I using Prefix Sum and Matrix in Java.
We are given an m x n matrix of positive integers. We need to determine if we can make either one horizontal or one vertical cut such that both resulting subgrids are non-empty and have equal sums. For two sections to have identical sums, each section must sum to exactly half of the total sum of all matrix elements.
If the total sum of the grid is odd, an equal integer split is immediately impossible, so we can return false upfront. Otherwise, we calculate the target sum as totalSum / 2. We then evaluate horizontal cuts by accumulating prefix row sums up to row m - 2 and vertical cuts by accumulating prefix column sums up to column n - 2. If any accumulated prefix sum matches our target, we return true, giving an optimal O(m * n) time and O(m + n) auxiliary space complexity.
🔥 Problem Highlights
✅ Total Sum Parity Check: Immediately prunes odd total sums as impossible to partition equally
✅ Row & Column Prefix Sweeps: Evaluates all candidate horizontal cuts and vertical cuts independently
✅ Non-Empty Section Guarantee: Tests cuts only between 0 and m - 2 (for rows) and 0 and n - 2 (for columns)
✅ 64-Bit Integer Precision: Safely accumulates elements into 64-bit longs to handle matrix sums up to 10^10
✅ Grid Dimension Flexibility: Handles single-row or single-column grids without out-of-bounds indexing
✅ Optimal Complexity: Operates in O(m * n) time complexity and O(m + n) auxiliary space
⏱️ TIMESTAMPS
00:00 Intro & Daily Challenge Overview
01:22 Problem Understanding & Cut Constraints
02:57 Key Insights: Parity Filtering & 64-Bit Range
04:48 Algorithmic Strategy: Row/Column Sum Prefix Verification
06:30 Clean Java Solution Walkthrough Line by Line
07:57 Dry Run & Step-by-Step Example Walkthrough
10:08 Time Complexity Analysis (O(M × N) - 3 ms, Beats 99.2%)
11:25 Space Complexity Analysis (O(M + N) Auxiliary Space)
12:31 Outro & Resources
📂 Problem Folder & Detailed Documentation:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/tree/main/solutions/March/25-March/3546-Equal-Sum-Grid-Partition-I
☕ Java Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/March/25-March/3546-Equal-Sum-Grid-Partition-I/Solution.java
🐍 Python Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/March/25-March/3546-Equal-Sum-Grid-Partition-I/solution.py
⚡ C++ Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/March/25-March/3546-Equal-Sum-Grid-Partition-I/solution.cpp
🌐 JavaScript Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/March/25-March/3546-Equal-Sum-Grid-Partition-I/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
Prefix Sums on Matrices
Grid Partitioning Patterns
Parity Invariants
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
If the total sum of all elements in the grid is an odd number, why can we immediately return false?
1️⃣ Because all elements are positive integers, two equal sections must each have an integer sum of totalSum / 2, which is impossible if totalSum is odd
2️⃣ Because horizontal cuts cannot be performed on odd-sized matrices
3️⃣ Because the problem requires the matrix to be symmetric
4️⃣ Because 64-bit integers cannot divide odd numbers
#LeetCode3546 #LeetCode #EqualSumGridPartitionI #Java #JavaDSA #PrefixSum #Matrix #Array #DSA #CodingInterview #ProblemSolving #LeetCodeMedium #DailyLeetCode #JavaProgramming #CodeByTushu
👇 Comment the answer below! 🔥 Close description
