Solution: Number of Submatrices That Sum to Target

Leetcode Solutions (161 Part Series)

1 Solution: Next Permutation
2 Solution: Trim a Binary Search Tree
… 157 more parts…
3 Leetcode Solutions Index
4 Solution: Minimize Deviation in Array
5 Solution: Vertical Order Traversal of a Binary Tree
6 Solution: Count Ways to Make Array With Product
7 Solution: Smallest String With A Given Numeric Value
8 Solution: Linked List Cycle
9 Solution: Path With Minimum Effort
10 Solution: Concatenation of Consecutive Binary Numbers
11 Solution: Minimum Operations to Make a Subsequence
12 Solution: Longest Harmonious Subsequence
13 Solution: Simplify Path
14 Solution: Building Boxes
15 Solution: Decode XORed Permutation
16 Solution: Binary Tree Right Side View
17 Solution: Find Kth Largest XOR Coordinate Value
18 Solution: Change Minimum Characters to Satisfy One of Three Conditions
19 Solution: Shortest Distance to a Character
20 Solution: Peeking Iterator
21 Solution: Convert BST to Greater Tree
22 Solution: Copy List with Random Pointer
23 Solution: Valid Anagram
24 Solution: Number of Steps to Reduce a Number to Zero
25 Solution: Shortest Path in Binary Matrix
26 Solution: Is Graph Bipartite?
27 Solution: Maximum Score From Removing Substrings (ver. 1)
28 Solution: Maximum Score From Removing Substrings (ver. 2)
29 Solution: Sort the Matrix Diagonally
30 Solution: The K Weakest Rows in a Matrix (ver. 1)
31 Solution: The K Weakest Rows in a Matrix (ver. 2)
32 Solution: Letter Case Permutation
33 Solution: Container With Most Water
34 Solution: Arithmetic Slices
35 Solution: Minimum Remove to Make Valid Parentheses
36 Solution: Roman to Integer
37 Solution: Broken Calculator
38 Solution: Find the Most Competitive Subsequence
39 Solution: Longest Word in Dictionary through Deleting
40 Solution: Search a 2D Matrix II
41 Solution: Score of Parentheses
42 Solution: Shortest Unsorted Continuous Subarray
43 Solution: Validate Stack Sequences
44 Solution: Divide Two Integers (ver. 1)
45 Solution: Divide Two Integers (ver. 2)
46 Solution: Maximum Frequency Stack
47 Solution: Distribute Candies
48 Solution: Set Mismatch (ver. 1)
49 Solution: Set Mismatch (ver. 2)
50 Solution: Missing Number
51 Solution: Intersection of Two Linked Lists
52 Solution: Average of Levels in Binary Tree
53 Solution: Short Encoding of Words (ver. 1)
54 Solution: Design HashMap (ver. 1)
55 Solution: Short Encoding of Words (ver. 2)
56 Solution: Design HashMap (ver. 2)
57 Solution: Remove Palindromic Subsequences
58 Solution: Add One Row to Tree
59 Solution: Integer to Roman
60 Solution: Coin Change
61 Solution: Check If a String Contains All Binary Codes of Size K
62 Solution: Binary Trees With Factors
63 Solution: Swapping Nodes in a Linked List
64 Solution: Encode and Decode TinyURL
65 Solution: Best Time to Buy and Sell Stock with Transaction Fee
66 Solution: Generate Random Point in a Circle
67 Solution: Wiggle Subsequence
68 Solution: Keys and Rooms
69 Solution: Design Underground System
70 Solution: Reordered Power of 2
71 Solution: Vowel Spellchecker
72 Solution: 3Sum With Multiplicity
73 Solution: Advantage Shuffle
74 Solution: Pacific Atlantic Water Flow
75 Solution: Word Subsets
76 Solution: Palindromic Substrings
77 Solution: Reconstruct Original Digits from English
78 Solution: Flip Binary Tree To Match Preorder Traversal
79 Solution: Russian Doll Envelopes
80 Solution: Stamping The Sequence
81 Solution: Palindrome Linked List
82 Solution: Ones and Zeroes
83 Solution: Longest Valid Parentheses
84 Solution: Design Circular Queue
85 Solution: Global and Local Inversions
86 Solution: Minimum Operations to Make Array Equal
87 Solution: Determine if String Halves Are Alike
88 Solution: Letter Combinations of a Phone Number
89 Solution: Verifying an Alien Dictionary
90 Solution: Longest Increasing Path in a Matrix
91 Solution: Deepest Leaves Sum
92 Solution: Beautiful Arrangement II
93 Solution: Flatten Nested List Iterator
94 Solution: Partition List
95 Solution: Fibonacci Number
96 Solution: Remove All Adjacent Duplicates in String II
97 Solution: Number of Submatrices That Sum to Target
98 Solution: Remove Nth Node From End of List
99 Solution: Combination Sum IV
100 Solution: N-ary Tree Preorder Traversal
101 Solution: Triangle
102 Solution: Brick Wall
103 Solution: Count Binary Substrings
104 Solution: Critical Connections in a Network
105 Solution: Rotate Image
106 Solution: Furthest Building You Can Reach
107 Solution: Power of Three
108 Solution: Unique Paths II
109 Solution: Find First and Last Position of Element in Sorted Array
110 Solution: Powerful Integers
111 Solution: Prefix and Suffix Search
112 Solution: Course Schedule III
113 Solution: Running Sum of 1d Array
114 Solution: Non-decreasing Array
115 Solution: Jump Game II
116 Solution: Convert Sorted List to Binary Search Tree
117 Solution: Delete Operation for Two Strings
118 Solution: Super Palindromes
119 Solution: Construct Target Array With Multiple Sums
120 Solution: Count Primes
121 Solution: Maximum Points You Can Obtain from Cards
122 Solution: Range Sum Query 2D – Immutable
123 Solution: Ambiguous Coordinates
124 Solution: Flatten Binary Tree to Linked List
125 Solution: Valid Number
126 Solution: Binary Tree Cameras
127 Solution: Longest String Chain
128 Solution: Find Duplicate File in System
129 Solution: Minimum Moves to Equal Array Elements II
130 Solution: Binary Tree Level Order Traversal
131 Solution: Find and Replace Pattern
132 Solution: N-Queens
133 Solution: To Lower Case
134 Solution: Evaluate Reverse Polish Notation
135 Solution: Partitioning Into Minimum Number Of Deci-Binary Numbers
136 Solution: Maximum Product of Word Lengths
137 Solution: Maximum Erasure Value
138 Solution: N-Queens II
139 Solution: Maximum Gap
140 Solution: Search Suggestions System
141 Solution: Max Area of Island
142 Solution: Interleaving String
143 Solution: Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts
144 Solution: Open the Lock
145 Solution: Maximum Performance of a Team
146 Solution: Longest Consecutive Sequence
147 Solution: Min Cost Climbing Stairs
148 Solution: Construct Binary Tree from Preorder and Inorder Traversal
149 Solution: Jump Game VI
150 Solution: My Calendar I
151 Solution: Stone Game VII
152 Solution: Minimum Number of Refueling Stops
153 Solution: Palindrome Pairs
154 Solution: Maximum Units on a Truck
155 Solution: Matchsticks to Square
156 Solution: Generate Parentheses
157 Solution: Number of Subarrays with Bounded Maximum
158 Solution: Swim in Rising Water
159 Solution: Pascal’s Triangle
160 Solution: Out of Boundary Paths
161 Solution: Redundant Connection

This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode’s forums.

Leetcode Problem #1074 (Hard): Number of Submatrices That Sum to Target

Description:

(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)

Given a matrix and a target, return the number of non-empty submatrices that sum to target.

A submatrix x1, y1, x2, y2 is the set of all cells matrix[x][y] with x1 <= x <= x2 and y1 <= y <= y2.

Two submatrices (x1, y1, x2, y2) and (x1', y1', x2', y2') are different if they have some coordinate that is different: for example, if x1 != x1'.

Examples:

Example 1:

Input: matrix = [[0,1,0],[1,1,1],[0,1,0]], target = 0

Output: 4

Explanation: The four 1×1 submatrices that only contain 0.

Visual:

Example 2:

Input: matrix = [[1,-1],[-1,1]], target = 0

Output: 5

Explanation: The two 1×2 submatrices, plus the two 2×1 submatrices, plus the 2×2 submatrix.

Example 3:

Input: matrix = [[904]], target = 0

Output: 0

Example 1:
Input:	matrix = [[0,1,0],[1,1,1],[0,1,0]], target = 0
Output:	4
Explanation:	The four 1×1 submatrices that only contain 0.
Visual:

Example 2:
Input:	matrix = [[1,-1],[-1,1]], target = 0
Output:	5
Explanation:	The two 1×2 submatrices, plus the two 2×1 submatrices, plus the 2×2 submatrix.

Example 3:
Input:	matrix = [[904]], target = 0
Output:	0

Constraints:

1 <= matrix.length <= 100

1 <= matrix[0].length <= 100

-1000 <= matrix[i] <= 1000

-10^8 <= target <= 10^8

Idea:

(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)

This problem is essentially a 2-dimensional version of #560. Subarray Sum Equals K (S.S.E.K). By using a prefix sum on each row or each column, we can compress this problem down to either N^2 iterations of the O(M) SSEK, or M^2 iterations of the O(N) SSEK.

In the SSEK solution, we can find the number of subarrays with the target sum by utilizing a result map (res) to store the different values found as we iterate through the array while keeping a running sum (csum). Just as in the case with a prefix sum array, the sum of a subarray between i and j is equal to the sum of the subarray from 0 to j minus the sum of the subarray from 0 to i-1.

Rather than iteratively checking if sum[0,j] – sum[0,i-1] = T for every pair of i, j values, we can flip it around to sum[0,j] – T = sum[0,i-1] and since every earlier sum value has been stored in res, we can simply perform a lookup on sum[0,j] – T to see if there are any matches.

When extrapolating this solution to our 2-dimensional matrix (M), we will need to first prefix sum the rows or columns, (which we can do in-place to avoid extra space, as we will not need the original values again). Then we should iterate through M again in the opposite order of rows/columns where the prefix sums will allow us to treat a group of columns or rows as if it were a 1-dimensional array and apply the SSEK algorithm.

Implementation:

There are only minor differences in the code of all four languages.

Javascript Code:

(Jump to: Problem Description || Solution Idea)

var numSubmatrixSumTarget = function(M, T) {
    let xlen = M[0].length, ylen = M.length,
        ans = 0, res = new Map()
    for (let i = 0, r = M[0]; i < ylen; r = M[++i]) 
        for (let j = 1; j < xlen; j++)
            r[j] += r[j-1]
    for (let j = 0; j < xlen; j++)
        for (let k = j; k < xlen; k++) {
            res.clear(), res.set(0,1), csum = 0
            for (let i = 0; i < ylen; i++) {
                csum += M[i][k] - (j ? M[i][j-1] : 0)
                ans += (res.get(csum - T) || 0)
                res.set(csum, (res.get(csum) || 0) + 1)
            }
        }
    return ans
};

Enter fullscreen mode Exit fullscreen mode

Python Code:

(Jump to: Problem Description || Solution Idea)

class Solution:
    def numSubmatrixSumTarget(self, M: List[List[int]], T: int) -> int:
        xlen, ylen, ans, res = len(M[0]), len(M), 0, defaultdict(int)
        for r in M:
            for j in range(1, xlen):
                r[j] += r[j-1]
        for j in range(xlen):
            for k in range(j, xlen):
                res.clear()
                res[0], csum = 1, 0
                for i in range(ylen):
                    csum += M[i][k] - (M[i][j-1] if j else 0)
                    ans += res[csum - T]
                    res[csum] += 1
        return ans

Enter fullscreen mode Exit fullscreen mode

Java Code:

(Jump to: Problem Description || Solution Idea)

class Solution {
    public int numSubmatrixSumTarget(int[][] M, int T) {
        int xlen = M[0].length, ylen = M.length, ans = 0;
        Map<Integer, Integer> res = new HashMap<>();
        for (int[] r : M)
            for (int j = 1; j < xlen; j++)
                r[j] += r[j-1];
        for (int j = 0; j < xlen; j++)
            for (int k = j; k < xlen; k++) {
                res.clear();
                res.put(0,1);
                int csum = 0;
                for (int i = 0; i < ylen; i++) {
                    csum += M[i][k] - (j > 0 ? M[i][j-1] : 0);
                    ans += res.getOrDefault(csum - T, 0);
                    res.put(csum, res.getOrDefault(csum, 0) + 1);
                }
            }
        return ans;
    }
}

Enter fullscreen mode Exit fullscreen mode

C++ Code:

(Jump to: Problem Description || Solution Idea)

class Solution {
public:
    int numSubmatrixSumTarget(vector<vector<int>>& M, int T) {
        int xlen = M[0].size(), ylen = M.size(), ans = 0;
        unordered_map<int, int> res;
        for (int i = 0; i < ylen; i++)
            for (int j = 1; j < xlen; j++)
                M[i][j] += M[i][j-1];
        for (int j = 0; j < xlen; j++)
            for (int k = j; k < xlen; k++) {
                res.clear();
                res[0] = 1;
                int csum = 0;
                for (int i = 0; i < ylen; i++) {
                    csum += M[i][k] - (j ? M[i][j-1] : 0);
                    ans += res.find(csum - T) != res.end() ? res[csum - T] : 0;
                    res[csum]++;
                }
            }
        return ans;
    }
};

Enter fullscreen mode Exit fullscreen mode

Leetcode Solutions (161 Part Series)

原文链接：Solution: Number of Submatrices That Sum to Target

文章版权声明 1、本网站名称：拾光赋
2、本站永久网址：https://www.blogs.ink
3、本网站的文章部分内容可能来源于网络，仅供大家学习与参考，如有侵权，请联系站长QQ：805375623进行删除处理。
4、本站一切资源不代表本站立场，并不代表本站赞同其观点和对其真实性负责。
5、本站一律禁止以任何方式发布或转载任何违法的相关信息，访客发现请向站长举报
6、本站资源大多存储在云盘，如发现链接失效，请联系我们我们会第一时间更新。

THE END