# Count on 1D/2D array

## 1513. Number of Substrings With Only 1s

`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;    }};`

## 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  R0011110000111100001111000011110000000000`
`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

## More from Jimmy Shen

Data Scientist/MLE/SWE @takemobi