LeetCode 3070: Count Submatrices with Top-Left Element and Sum Less Than k Solution

Master LeetCode problem 3070 (Count Submatrices with Top-Left Element and Sum Less Than k), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

3070. Count Submatrices with Top-Left Element and Sum Less Than k

Medium

Array Matrix Prefix Sum

Problem Explanation

Explanation

To solve this problem, we can use a sliding window technique along with prefix sum. The idea is to iterate over all possible top-left elements of submatrices and then use two pointers to find the submatrices with a sum less than or equal to k.

We start by fixing the top-left element of the submatrix at position (i, j) and iterate over all possible bottom-right elements of submatrices starting from (i, j).
We maintain a sliding window using two pointers left and right to track the current submatrix.
We update the sum of the current submatrix by adding the elements from the current column.
If the sum exceeds k, we move the left pointer to reduce the sum.
The number of valid submatrices with top-left element (i, j) is equal to the number of valid submatrices ending at (i, j-1) plus the number of valid submatrices ending at (i-1, j) minus the number of overlapping submatrices.

Time complexity: O(m^2 * n) where m is the number of rows and n is the number of columns. Space complexity: O(m * n) for the prefix sum matrix.

Solution Code

class Solution {
    public int numSubmatrixSumTarget(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;
        int count = 0;
        
        for (int i = 0; i < m; i++) {
            int[] sum = new int[n];
            for (int j = i; j < m; j++) {
                for (int c = 0; c < n; c++) {
                    sum[c] += matrix[j][c];
                }
                count += countSubarraysWithSumLessThanK(sum, target);
            }
        }
        
        return count;
    }
    
    private int countSubarraysWithSumLessThanK(int[] arr, int k) {
        int count = 0;
        int sum = 0;
        Map<Integer, Integer> prefixSumCount = new HashMap<>();
        prefixSumCount.put(0, 1);
        
        for (int num : arr) {
            sum += num;
            count += prefixSumCount.getOrDefault(sum - k, 0);
            prefixSumCount.put(sum, prefixSumCount.getOrDefault(sum, 0) + 1);
        }
        
        return count;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 3070 (Count Submatrices with Top-Left Element and Sum Less Than k)?

This page provides optimized solutions for LeetCode problem 3070 (Count Submatrices with Top-Left Element and Sum Less Than k) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 3070 (Count Submatrices with Top-Left Element and Sum Less Than k)?

The time complexity for LeetCode 3070 (Count Submatrices with Top-Left Element and Sum Less Than k) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 3070 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 3070 in Java, C++, or Python.

Back to LeetCode Solutions