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

This is not related to counting. However, the method used here to get the subarray sum is similar to the previous question.

221. Maximal Square

A straightforward solution based on a 2d range sum can be found here.

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

OMG, this problem is almost identical to leetcode 85 mentioned above.
We do have some better algorithms with a better complexity. For the solutions here, I am using algorithms with the complexity of O(R*C²) to demonstrate the similarity of those two problems. The basic idea is
- precalculate the prefix sum for each row, the prefix sum for each row can help us quickly decide whether from a range [l, r] contains all 1s.
- set two pointers left and right in the column dimension and we can traverse all possible width of the rectangle.
- based on each width, traverse from the first row to the last row, we can aggregate the results that we need.

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]

From left to right, if for a given row, we have all ones from left to right, then we will generate something like this

  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

[1]https://www.bilibili.com/video/BV1BA411i7sm

Data Scientist/MLE/SWE @takemobi