Given an integer matrix, find a submatrix where the sum of numbers is zero. Your code should return the coordinate of the left-up and right-down number.
Have you met this question in a real interview?
Yes
Example
Given matrix
[
[1 ,5 ,7],
[3 ,7 ,-8],
[4 ,-8 ,9],
]
return[(1,1), (2,2)]
O(n3) time.
syntax error
line 10 missing one last brace
for loop use comma second semicolen
name problem
line 30 should not use m, n as they are already used
line 53 missing adding pair to hashmap
class Solution {
public:
/\*\*
\* @param matrix an integer matrix
\* @return the coordinate of the left-up and right-down number
\*/
vector<vector<int>> submatrixSum\(vector<vector<int>>& matrix\) {
// Write your code here
if \(matrix.empty\(\) \|\| matrix\[0\].empty\(\)\) {
return vector<vector<int> >\( {{ -1, -1}, {-1, -1}}\);
}
vector<vector<int>> res;
int n = matrix.size\(\);
int m = matrix\[0\].size\(\);
vector<vector<vector<int>>> sum\(m, vector<vector<int>>\(n, vector<int>\(n, 0\)\)\);
for \(int k = 0; k < m; ++k\) {
for \(int i = 0; i < n; ++i\) {
int tempSum = 0;
for \(int j = i; j < n; ++j\) {
tempSum += matrix\[j\]\[k\];
sum\[k\]\[i\]\[j\] = tempSum;
}
}
}
// cout << sum\[0\]\[1\]\[2\] << endl;
// cout << sum\[1\]\[1\]\[2\] << endl;
// cout << sum\[2\]\[1\]\[2\] << endl;
for \(int i = 0; i < n; ++i\) {
for \(int j = i; j < n; ++j\) {
int p = -1, q = -1;
if \(!helperSubArray\(sum, i, j, p, q\)\) {
continue;
}
res.push\_back\({i, p}\);
res.push\_back\({j, q}\);
return res;
}
}
res.push\_back\({-1, -1}\);
res.push\_back\({-1, -1}\);
return res;
}
private:
bool helperSubArray\(const vector<vector<vector<int>>>& sum, const int i, const int j, int& p, int& q\) {
unordered\_map<int, int> hash;
hash.insert\({0, -1}\);
int tempSum = 0;
// cout << sum.size\(\) << endl;
for \(int k = 0; k < sum.size\(\); ++k\) {
tempSum += sum\[k\]\[i\]\[j\];
if \(hash.find\(tempSum\) == hash.end\(\)\) {
hash\[tempSum\] = k;
continue;
}
p = hash\[tempSum\] + 1;
q = k;
return true;
}
return false;
}
};