Naive solution is O(n^4). But on 1 certain dimension, naive O(n^2) can be O(n) by this well-known equation: sum[i..j] = sum[0..j] - sum[0..i]. And pls take care of several corner cases.
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>>& m) {
int h = m.size();
if(!h) return {};
int w = m[].size();
if(!w) return {};
// Get accumulate sum by columns
vector<vector<int>> cols(h, vector<int>(w, ));
for(int i = ; i < w; i ++)
{
unordered_map<int, int> rec; // sum-inx
for(int j = ; j < h; j ++)
{
if(m[j][i] == )
{
return {{i, j},{i, j}};
}
cols[j][i] = (j ? cols[j - ][i] : ) + m[j][i];
if (!cols[j][i])
{
return {{, i}, {j, i}};
}
else if(rec.find(cols[j][i]) != rec.end())
{
return {{rec[cols[j][i]] + , i}, {j, i}};
}
rec[cols[j][i]] = j;
}
}
// horizontal case
for(int i = ; i < h; i ++)
for(int j = i; j < h; j ++)
{
vector<int> hsum(w, );
for(int x = ; x < w; x ++)
{
int prev = ((i == ) ? : cols[i - ][x]);
hsum[x] = cols[j][x] - prev;
}
//
vector<int> asum(w, );
unordered_map<int, int> rec; // sum-inx
for(int x = ; x < w; x ++)
{
int nsum = (x ? asum[x - ] : ) + hsum[x];
if (!nsum)
{
return {{i + , }, {j, x}};
}
else if(rec.find(nsum) != rec.end())
{
return {{i, rec[nsum] + }, {j, x}};
}
rec[nsum] = x;
asum[x] = nsum;
}
}
return {};
}
};