समस्या विवरण
इस समस्या में, हमें एक N×N मैट्रिक्स mat[][] दिया गया है। हमारा कार्य सभी समान तत्वों वाले अधिकतम वर्ग उप-मैट्रिक्स को खोजना है।
इस समस्या में, हमें दिए गए मैट्रिक्स से अधिकतम आकार के उप-मैट्रिक्स को खोजने की आवश्यकता है जिसके सभी तत्व समान हों।
उदाहरण
इनपुट: mat[][] = {{1, 2, 1},
{1, 2, 2},
{2, 2, 2}}
आउटपुट: 2
व्याख्या
मैट्रिक्स a₁₁, a₁₂, a₂₁, a₂₂ आकार 2×2 का है और सभी समान तत्वों वाला उप-मैट्रिक्स बनाता है।
हल का दृष्टिकोण
समस्या का एक सरल समाधान मैट्रिक्स के सभी तत्वों को पार करना और फिर उन सभी उप-मैट्रिक्स की जांच करना है जिनके सभी तत्व समान हैं। एल्गोरिदम की समय जटिलता O(N³) है और प्रत्येक उप-मैट्रिक्स O(N²) समय जटिलता के साथ बनाया जाता है।
वैकल्पिक विधि डायनामिक प्रोग्रामिंग का उपयोग करके समस्या को हल करना है जहां हम उस स्थिति तक की शर्त को संतुष्ट करने वाले सबसे बड़े उप-मैट्रिक्स का आकार संग्रहीत करेंगे। इसके लिए हम पड़ोसी तत्वों पर विचार करेंगे और फिर दी गई शर्त को संतुष्ट करने वाले सबसे लंबे मैट्रिक्स पर विचार करेंगे।
DP मैट्रिक्स के किसी भी सेल के आकार को सूत्रबद्ध करें:
यदि तत्व के सभी पड़ोसी समान हैं, तो हम सबसे लंबे उप-मैट्रिक्स के मान बढ़ाएंगे। इस मामले में,
DP[i][j] = min(DP[i-1][j], DP[i][j-1], DP[i-1][j-1]) + 1
यदि ऐसा नहीं है,
DP[i][j] = 1
C++ कार्यान्वयन
#include <bits/stdc++.h>
#define N 4
#define M 4
using namespace std;
int findMaxSqMatSize(int mat[][M]) {
int DP[N][M];
memset(DP, 0, sizeof(DP));
int maxSqMatSize = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (i == 0 || j == 0) {
DP[i][j] = 1;
} else {
if (mat[i][j] == mat[i-1][j] &&
mat[i][j] == mat[i][j-1] &&
mat[i][j] == mat[i-1][j-1]) {
DP[i][j] = min({DP[i-1][j], DP[i][j-1], DP[i-1][j-1]}) + 1;
} else {
DP[i][j] = 1;
}
}
maxSqMatSize = max(maxSqMatSize, DP[i][j]);
}
}
return maxSqMatSize;
}
int main() {
int mat[N][M] = {
{2, 1, 4, 3},
{5, 1, 1, 7},
{1, 1, 1, 4},
{9, 4, 6, 0}
};
cout << "सभी समान तत्वों वाला अधिकतम वर्ग उप-मैट्रिक्स है " << findMaxSqMatSize(mat);
return 0;
}
आउटपुट
सभी समान तत्वों वाला अधिकतम वर्ग उप-मैट्रिक्स है 2
जटिलता विश्लेषण
- समय जटिलता: O(N × M)
- स्पेस जटिलता: O(N × M) - DP टेबल के लिए
DP अंतर्ज्ञान
DP[i][j] मैट्रिक्स के निचले-दाएं कोने (i, j) पर समाप्त होने वाले सभी समान तत्वों वाले सबसे बड़े वर्ग का आकार दर्शाता है। यह तभी बढ़ सकता है जब ऊपर, बाएं, और विकर्ण-ऊपर-बाएं सभी का मान समान हो और स्वयं वर्ग बना सकें।
