LeetCode 3070 | Count Submatrices with Top-Left Element and Sum Less Than k | Java | CodeByTushu
Description: 🚀 Welcome Back to CodeByTushu!
In today’s video, we solve LeetCode 3070 — Count Submatrices with Top-Left Element and Sum Less Than k using 2D Prefix Sum in Java.
The problem asks us to count all submatrices starting at the top-left cell (0, 0) whose total element sum is less than or equal to k. Every such submatrix is uniquely determined by its bottom-right corner (i, j). Consequently, computing the sum of any candidate submatrix translates directly to finding the 2D prefix sum of the grid up to cell (i, j).
Using the inclusion-exclusion principle, the prefix sum at (i, j) is calculated from the current cell plus the sum of the cell directly above, plus the cell to the left, minus the diagonally overlapping top-left cell. We accumulate these prefix sums directly in-place within the matrix to maintain strict O(1) auxiliary space, checking whether each evaluated sum is less than or equal to k in optimal O(m * n) overall runtime.
🔥 Problem Highlights
✅ Unique submatrix characterization anchored at the origin (0, 0)
✅ Standard 2D prefix sum computation via the inclusion-exclusion principle
✅ Seamless in-place matrix updates achieving strict O(1) auxiliary memory
✅ Integer overflow safety with maximum total sum bounded by 10^9
✅ Optimal single-pass linear time complexity running in under 2 milliseconds
✅ Clean, production-ready solution applicable across large matrix dimensions
⏱️ TIMESTAMPS
00:00 Intro & Daily Challenge Overview
01:11 Problem Understanding & Fixed Top-Left Geometry
03:01 Key Insights: 2D Prefix Sum & Inclusion-Exclusion
04:54 Algorithmic Strategy & 3-Step Implementation
06:21 Clean Java Solution Walkthrough Line by Line
07:50 Test Cases Walkthrough & Step-by-Step Simulation
09:35 Time Complexity Analysis (O(M·N) - 5 ms)
10:27 Space Complexity Analysis (O(1) Auxiliary Space)
11:10 Outro & Resources
📂 Problem Folder & Detailed Documentation:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/tree/main/solutions/March/18-March/3070-Count-Submatrices-with-Top-Left-Element-and-Sum-Less-Than-k
☕ Java Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/March/18-March/3070-Count-Submatrices-with-Top-Left-Element-and-Sum-Less-Than-k/Solution.java
🐍 Python Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/March/18-March/3070-Count-Submatrices-with-Top-Left-Element-and-Sum-Less-Than-k/solution.py
⚡ C++ Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/March/18-March/3070-Count-Submatrices-with-Top-Left-Element-and-Sum-Less-Than-k/solution.cpp
🌐 JavaScript Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/March/18-March/3070-Count-Submatrices-with-Top-Left-Element-and-Sum-Less-Than-k/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
2D Prefix Sum Techniques
Inclusion-Exclusion Principle
Matrix Precomputation
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
What is the inclusion-exclusion recurrence relation to compute the 2D prefix sum P[i][j] from its neighbors?
1️⃣ P[i][j] = grid[i][j] + P[i - 1][j] + P[i][j - 1] - P[i - 1][j - 1]
2️⃣ P[i][j] = grid[i][j] + P[i - 1][j] + P[i][j - 1] + P[i - 1][j - 1]
3️⃣ P[i][j] = grid[i][j] + P[i - 1][j - 1]
4️⃣ P[i][j] = grid[i][j] - P[i - 1][j] - P[i][j - 1] + P[i - 1][j - 1]
#LeetCode3070 #LeetCode #CountSubmatricesWithTopLeftElementAndSumLessThanK #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 3070 — Count Submatrices with Top-Left Element and Sum Less Than k using 2D Prefix Sum in Java.
The problem asks us to count all submatrices starting at the top-left cell (0, 0) whose total element sum is less than or equal to k. Every such submatrix is uniquely determined by its bottom-right corner (i, j). Consequently, computing the sum of any candidate submatrix translates directly to finding the 2D prefix sum of the grid up to cell (i, j).
Using the inclusion-exclusion principle, the prefix sum at (i, j) is calculated from the current cell plus the sum of the cell directly above, plus the cell to the left, minus the diagonally overlapping top-left cell. We accumulate these prefix sums directly in-place within the matrix to maintain strict O(1) auxiliary space, checking whether each evaluated sum is less than or equal to k in optimal O(m * n) overall runtime.
🔥 Problem Highlights
✅ Unique submatrix characterization anchored at the origin (0, 0)
✅ Standard 2D prefix sum computation via the inclusion-exclusion principle
✅ Seamless in-place matrix updates achieving strict O(1) auxiliary memory
✅ Integer overflow safety with maximum total sum bounded by 10^9
✅ Optimal single-pass linear time complexity running in under 2 milliseconds
✅ Clean, production-ready solution applicable across large matrix dimensions
⏱️ TIMESTAMPS
00:00 Intro & Daily Challenge Overview
01:11 Problem Understanding & Fixed Top-Left Geometry
03:01 Key Insights: 2D Prefix Sum & Inclusion-Exclusion
04:54 Algorithmic Strategy & 3-Step Implementation
06:21 Clean Java Solution Walkthrough Line by Line
07:50 Test Cases Walkthrough & Step-by-Step Simulation
09:35 Time Complexity Analysis (O(M·N) - 5 ms)
10:27 Space Complexity Analysis (O(1) Auxiliary Space)
11:10 Outro & Resources
📂 Problem Folder & Detailed Documentation:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/tree/main/solutions/March/18-March/3070-Count-Submatrices-with-Top-Left-Element-and-Sum-Less-Than-k
☕ Java Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/March/18-March/3070-Count-Submatrices-with-Top-Left-Element-and-Sum-Less-Than-k/Solution.java
🐍 Python Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/March/18-March/3070-Count-Submatrices-with-Top-Left-Element-and-Sum-Less-Than-k/solution.py
⚡ C++ Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/March/18-March/3070-Count-Submatrices-with-Top-Left-Element-and-Sum-Less-Than-k/solution.cpp
🌐 JavaScript Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/March/18-March/3070-Count-Submatrices-with-Top-Left-Element-and-Sum-Less-Than-k/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
2D Prefix Sum Techniques
Inclusion-Exclusion Principle
Matrix Precomputation
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
What is the inclusion-exclusion recurrence relation to compute the 2D prefix sum P[i][j] from its neighbors?
1️⃣ P[i][j] = grid[i][j] + P[i - 1][j] + P[i][j - 1] - P[i - 1][j - 1]
2️⃣ P[i][j] = grid[i][j] + P[i - 1][j] + P[i][j - 1] + P[i - 1][j - 1]
3️⃣ P[i][j] = grid[i][j] + P[i - 1][j - 1]
4️⃣ P[i][j] = grid[i][j] - P[i - 1][j] - P[i][j - 1] + P[i - 1][j - 1]
#LeetCode3070 #LeetCode #CountSubmatricesWithTopLeftElementAndSumLessThanK #Java #JavaDSA #PrefixSum #Matrix #Array #DSA #CodingInterview #ProblemSolving #LeetCodeMedium #DailyLeetCode #JavaProgramming #CodeByTushu
👇 Comment the answer below! 🔥 Close description