Count on 1D/2D array

const int MOD = 1e9+7;
class Solution {
public:
int numSub(string s) {
unsigned long long ret = 0;
unsigned long long ones = 0;
for (auto c:s)
{
if (c == '1')
{
ones++;
}
else
{
ret += ones*(ones+1)/2;
if (ret>=MOD)
{
ret %=MOD;
}
ones = 0;
}
}
ret += ones*(ones+1)/2;
if (ret>=MOD)
{
ret %=MOD;
}
return int(ret);
}
};
const int MOD = 1e9+7;
class Solution {
public:
int numSub(string s) {
int ret = 0, ones = 0;
for(auto x:s)
{
if(x=='1')ones++;
else ones=0;
ret += ones;
if(ret>MOD)ret%=MOD;
}
return ret;
}
};

1508. Range Sum of Sorted Subarray Sums

221. Maximal Square

class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
if(matrix.empty() || matrix[0].empty())return 0;
const int R = matrix.size(), C = matrix[0].size();
vector<vector<int>> dp(R+1, vector<int>(C+1, 0));
for(int i=0;i<R;++i)
for(int j=0;j<C;++j)
{
auto r = i+1, c = j+1;
dp[r][c] = dp[r-1][c]+dp[r][c-1] - dp[r-1][c-1] + int(matrix[i][j]=='1');
}
//for(auto x:dp){for(auto c:x)cout<<c<<" ";cout<<endl;}
int ret = 0;
for(int i=R-1;i>=0;--i)
for(int j=C-1;j>=0;--j)
{
for(int l=min(i, j)+1;l>=1;--l)
{
//cout<<"i, j, l"<<i<<","<<j<<","<<l<<endl;;
auto r = i-l+1, c = j-l+1;
//cout<<"r,c"<<r<<" "<<c<<endl;
if(dp[i+1][j+1]-dp[i+1][c]-dp[r][j+1]+dp[r][c]==l*l)ret = max(ret, l*l);
}
}
return ret;
}
};

85. Maximal Rectangle

O(R²C²) solution (TLE)

class Solution {
public:
int maximalRectangle(vector<vector<char>>& matrix) {
if(matrix.empty() || matrix[0].empty())return 0;
const int R = matrix.size(), C = matrix[0].size();
vector<vector<int>> dp(R+1, vector<int>(C+1, 0));
for(int i=0;i<R;++i)
for(int j=0;j<C;++j)
{
dp[i+1][j+1] = dp[i+1][j]+dp[i][j+1] - dp[i][j] + int(matrix[i][j] == '1');
}
int ret = 0;
for(int i = 0; i < R; ++i)
for(int j=0;j<C;++j)
for(int r = 1;r<=i+1;++r)
for(int c =1;c<=j+1;++c)
{
auto ii = i-r+1, jj = j-c+1;
if (dp[i+1][j+1]-dp[ii][j+1]-dp[i+1][jj]+dp[ii][jj]==r*c)ret=max(ret, r*c);
}
return ret;
}
};
class Solution {
public:
int maximalRectangle(vector<vector<char>>& matrix) {
if(matrix.empty() || matrix[0].empty())return 0;
const int R = matrix.size(), C = matrix[0].size();
vector<vector<int>> dp(R, vector<int>(C, 0));
for(int i=0;i<R;++i)
{
dp[i][0] = int(matrix[i][0]=='1');
for(int j=1;j<C;++j)
{
dp[i][j] = dp[i][j-1] + int(matrix[i][j]=='1');
}
}

int ret = 0;
for(int l=0;l<C;++l)
for(int r = l;r<C;++r)
{
int row = 0, max_row = 0;
for(int i=0;i<R;++i)
{
int this_sum = dp[i][r];
if(l>0)this_sum -= dp[i][l-1];
if (this_sum==r-l+1)row++;
else
{
max_row = max(max_row, row);
row = 0;
}
}
max_row = max(max_row, row);
ret = max(ret, max_row*(r-l+1));
}
return ret;
}
};

1504. Count Submatrices With All Ones

Naive solution get TLE (O(R²C²))

class Solution {
public:
int numSubmat(vector<vector<int>>& mat) {
int R=mat.size(), C=mat[0].size();
int dp[151][151];
memset(dp, 0, sizeof(dp));
for(int i=0;i<R;++i){
for(int j=0;j<C;++j){
dp[i+1][j+1] = -dp[i][j] + dp[i][j+1] + dp[i+1][j] + mat[i][j];
}
}
int res = 0;
for(int i=0;i<R;++i){
for(int j=0;j<C;++j){
if(mat[i][j]){
int row=i+1, col=j+1;
for(int cc=1;cc<=col;cc++){
for (int rr=1;rr<=row;rr++){
int ii= i+1-rr, jj=j+1-cc;
if(dp[i+1][j+1]-dp[i+1][jj]-dp[ii][j+1]+dp[ii][jj]==rr*cc)res++;

}

}
}
//dp[i+1][j+1] = -dp[i][j] + dp[i][j+1] + dp[i+1][j] + mat[i][j];
}
}
//cout<<R<<C<<endl;
return res;
}
};

O(R²C) modified from [1]

  L  R
00111100
00111100
00111100
00111100
00000000
class Solution {
public:
int numSubmat(vector<vector<int>>& a) {
const int R = a.size(), C = a[0].size();
vector<vector<int>> s = a;
for(int i=0;i<R;++i)
for(int j=1;j<C;++j)
{
s[i][j] += s[i][j-1];
}
int ret = 0;
for(int l=0; l<C; l++)
for(int r = l; r<C;r++)
{
int len = 0;
for(int i=0;i<R;++i)
{
int this_sum = s[i][r] - (l>0?s[i][l-1]:0);
if(this_sum==(r-l+1))ret += (++len);
else len=0;
}
}
return ret;
}
};
class Solution {
public:
int numSubmat(vector<vector<int>>& a) {
const int R = a.size(), C = a[0].size();
vector<vector<int>> s = a;
for(int i=0;i<R;++i)
for(int j=1;j<C;++j)
{
s[i][j] += s[i][j-1];
}
int ret = 0;
for(int l=0; l<C; l++)
for(int r = l; r<C;r++)
{
int len = 0;
for(int i=0;i<R;++i)
{
int this_sum = s[i][r] - (l>0?s[i][l-1]:0);
if(this_sum==(r-l+1)) ++len;
else
{
ret += len*(len+1)/2;
len=0;
}
}
// do not forget this line
ret += len*(len+1)/2;
}
return ret;
}
};

Reference

Data Scientist/MLE/SWE @takemobi