Find the number of rectangles of same color in a matrix
Difference between en5 and en6, changed 57 character(s)
**Question:**↵

You have a $N * M$ matrix. The color of cell in $i^{th}$ row and $j^{th}$ column is $a_{ij}$. Find the number of rectangles that can be formed from this matrix by deleting some rows and columns, that have all cells of same color.↵

![ ](https://i.imgur.com/e9aQSKP.png)↵

**Idea:**↵

Let $i_l, j_l$ be the coordinates of the top left corner and $i_r, j_r$ be the coordinates of the bottom right corner.↵
We can see that $(i_l, j_l, i_r, j_r)$ uniquely define a rectangle.↵

Let's call a rectangle valid if it has all cells of same color.↵

Now let $dp[i][j]$ be the number of valid rectangles with their bottom right corner at $(i, j)$.↵

Let $h[i][j]$ be the "height" of columns at $(i, j)$. That is ↵

![ ](https://i.imgur.com/6UEMM3G.png)↵

$h[i][j]$ = max value of $len$ such that $a[i][j] = a[i][t]$ , for all $t = i - len + 1, i - len + 2, ..., i$.↵

How do we computer $dp[i][j]$ efficiently ? ↵

Consider how $dp[i][j]$ depends on $dp[i-1][j], dp[i - 2][j], ...$.↵

For some $k, k < j$, if $a[i][k] != a[i][j]$, then $dp[i][k]$ will make no contribution to $dp[i][j]$. So let's assume that $a[i][t] = a[i][j]$ for all $t = k, k + 1, ..., j$.↵

Now what is the maximum height of rectangle with bottom right corner at $(i, j)$ and top left corner in the column $k$ ? ↵

![ ](https://i.imgur.com/1qew4HO.png)↵

It is $height_k = min_{k \le t \le i}(h[i][t])$. Then then the number of such rectangles is $height_k$, since we can have rectangles of height $1, 2, 3, ..., height_k$.↵

Also consider that if $h[i][k] \le height_k$, then for any rectangle with bottom right corner at $(i, k)$ can be extended so that it has bottom right corner at $(i, j)$.↵


Let $k$ be the first index such that $a[i][k] = a[i][j]$ and $h[i][k] < h[i][j]$. ↵

![ ](https://i.imgur.com/M9qApTC.png)↵

Then every rectangle with bottom right corner at $(i, k)$ can be extended to $(i, j)$. ↵
Also the height of any rectangle with top-left corner after $(i, k)$ is at most $h[i][j]$, since by definition for any $t, k < t \le i$ we have $h[i][t] \ge h[i][j]$.↵

Thus the number of rectangles after k are $h[i][j] * (j - k)$.↵

![ ](https://i.imgur.com/wOZnnvm.png)↵

Thus we have, $dp[i][j] = dp[i][k] + h[i][j] * (j - k)$.↵

Now the question is how do we efficiently find $k$ ?↵

We can do this by maintaining an array of indices $col$ such that $h[i][col] \lt min_{col \le t \le j}(h[i][t])$. ↵

![ ](https://i.imgur.com/QxCbwLp.png)↵


*Time Complexity : $O(N
 * M)$*↵




~~~~~↵

vector<vector<ll>> get_number_of_rectangles(vector<vector<int>> &a, int n, int m){↵
    vector<vector<ll>> dp(n, vector<ll>(m));↵
    vector<vector<ll>> h(n, vector<ll>(m, 1));↵

    for(int i = 1; i < n; ++i){↵
        for(int j = 0; j < m; ++j){↵
            if(a[i - 1][j] == a[i][j]){↵
                h[i][j] += h[i - 1][j];↵
            }↵
        }↵
    }↵

    for(int i = 0; i < n; ++i){↵
        vector<int> indices;↵
        for(int j = 0; j < m; ++j){↵
            int k = -1;↵
            while(!indices.empty()){↵
                int col = indices.back();↵
                if((a[i][col] != a[i][j]) || (h[i][col] < h[i][j])){↵
                    break;↵
                }↵
                indices.pop_back();↵
            }↵
            if(!indices.empty()){↵
                k = indices.back();↵
            }↵
            dp[i][j] += h[i][j] * (j - k);↵
            if(k != -1){↵
                if(a[i][k] == a[i][j]){↵
                    dp[i][j] += dp[i][k];↵
                }↵
            }↵
            indices.push_back(j);↵
        }↵
    }↵

    return dp;↵
}↵
 ↵
void solve() {↵
    int n, m;↵
    cin >> n >> m;↵
    vector<vector<int>> a(n, vector<int>(m));↵
    for(int i = 0; i < n; ++i){↵
        for(int j = 0; j < m; ++j){↵
            cin >> a[i][j];↵
        }↵
    }↵
    vector<vector<ll>> dp = get_number_of_rectangles(a, n, m);↵
    ll ans = 0;↵
    for(int i = 0; i < n; ++i){↵
        for(int j = 0; j < m; ++j){↵
            ans += dp[i][j];↵
        }↵
    }↵
    cout << ans << '\n';↵
}↵


~~~~~↵


History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en7 English one_autum_leaf 2023-10-29 19:29:05 61
en6 English one_autum_leaf 2023-10-28 10:11:54 57 Tiny change: '$k$ ? \n\nIt is ' -> '$k$ ? \n\n![ ](https://i.imgur.com/1qew4HO.png)\n\nIt is ' (published)
en5 English one_autum_leaf 2023-10-28 10:06:24 1625 Tiny change: 'imgur.com/w4jes7x.png)\n\n' -> 'imgur.com/QxCbwLp.png)\n\n'
en4 English one_autum_leaf 2023-10-28 09:45:05 846 Tiny change: 'color.\n\nIdea:\' -> 'color.\n\n![ ](https://imgur.com/a/QK6lnrD)\n\nIdea:\'
en3 English one_autum_leaf 2023-10-28 09:20:17 1462 Tiny change: ' a[i][t]$ \n\nfor all $t' -> ' a[i][t]$ , for all $t'
en2 English one_autum_leaf 2023-10-28 07:37:39 7 Tiny change: 'column is a^ij.' -> 'column is \a^ij.'
en1 English one_autum_leaf 2023-10-28 07:35:17 143 Initial revision (saved to drafts)