Matrix Block Sum – 2D Prefix Sum | Running Sum of 2D Array | C++, Java, Python

RisingBrain

4 chapters6 takeaways9 key terms5 questions

Overview

यह वीडियो 2D एरे (मैट्रिक्स) के लिए ब्लॉक सम या रनिंग सम की गणना करने की समस्या को हल करता है। यह पहले ब्रूट-फोर्स दृष्टिकोण की व्याख्या करता है, जहां प्रत्येक सेल के लिए, यह k रेडियस के भीतर सभी तत्वों का योग करता है, जिसकी समय जटिलता O(m*n*k^2) होती है, जो बड़े इनपुट के लिए अक्षम है। फिर, यह प्रीफिक्स सम (2D प्रीफिक्स सम) का उपयोग करके एक अनुकूलित समाधान प्रस्तुत करता है। यह 2D प्रीफिक्स सम मैट्रिक्स बनाने की प्रक्रिया और फिर इस प्रीफिक्स मैट्रिक्स का उपयोग करके प्रत्येक सेल के लिए ब्लॉक सम की गणना करने के लिए आवश्यक सूत्र को विस्तार से बताता है, जिससे समय जटिलता O(m*n) तक कम हो जाती है।

How was this?

Save this permanently with flashcards, quizzes, and AI chat

Chapters

समस्या: दिए गए मैट्रिक्स में प्रत्येक सेल (i, j) के लिए, एक नया मैट्रिक्स बनाना है जहां प्रत्येक सेल में मूल मैट्रिक्स के उन सभी तत्वों का योग हो जो (i, j) से k दूरी के भीतर (ऊपर, नीचे, बाएं, दाएं और विकर्ण) हैं।
ब्रूट-फोर्स विधि: प्रत्येक सेल (i, j) के लिए, k रेडियस के भीतर सभी वैध तत्वों (पंक्ति i-k से i+k और कॉलम j-k से j+k तक) को सीधे जोड़ें।
ब्रूट-फोर्स की समय जटिलता: प्रत्येक सेल के लिए, हमें लगभग (2k+1) * (2k+1) तत्वों को देखना होता है, जिससे कुल समय जटिलता O(m*n*(2k+1)^2) या लगभग O(m*n*k^2) हो जाती है, जो बड़े k के लिए बहुत धीमी है।

ब्रूट-फोर्स दृष्टिकोण समस्या को समझने में मदद करता है लेकिन इसकी अक्षमता के कारण यह व्यावहारिक नहीं है, जो अनुकूलित समाधान की आवश्यकता को दर्शाता है।

सेल (0,0) के लिए k=1 के साथ, हमें पंक्ति -1 से 1 और कॉलम -1 से 1 तक के तत्वों को देखना होगा। केवल वैध तत्व (0,0), (0,1), (1,0), (1,1) को जोड़ा जाएगा।

2D प्रीफिक्स सम का उद्देश्य: किसी दिए गए आयताकार क्षेत्र के योग की गणना को O(1) समय में सक्षम करना, बार-बार गणना से बचना।
प्रीफिक्स मैट्रिक्स का निर्माण: एक नया मैट्रिक्स (आमतौर पर मूल से एक आकार बड़ा) बनाया जाता है जहां प्रत्येक सेल (i, j) मूल मैट्रिक्स के (0,0) से (i-1, j-1) तक के सभी तत्वों के योग को संग्रहीत करता है।
प्रीफिक्स योग सूत्र: प्रीफिक्स[i][j] = मैट्रिक्स[i-1][j-1] + प्रीफिक्स[i-1][j] + प्रीफिक्स[i][j-1] - प्रीफिक्स[i-1][j-1]। यह सूत्र ओवरलैपिंग क्षेत्रों को दो बार जोड़ने से बचाता है।

2D प्रीफिक्स सम किसी भी आयताकार उप-मैट्रिक्स के योग को कुशलतापूर्वक खोजने के लिए एक शक्तिशाली तकनीक है, जो कई प्रश्नों के लिए आवश्यक है।

यदि मूल मैट्रिक्स में सेल (0,0) = 1, (0,1) = 2, (1,0) = 3, (1,1) = 4 है, तो प्रीफिक्स मैट्रिक्स में सेल (1,1) का मान 1 होगा, सेल (1,2) का मान 1+2=3 होगा, सेल (2,1) का मान 1+3=4 होगा, और सेल (2,2) का मान 1+2+3+4=10 होगा।

लक्ष्य क्षेत्र का निर्धारण: प्रत्येक उत्तर सेल (i, j) के लिए, हमें योग के लिए ऊपरी-बाएं कोने (r1, c1) और निचले-दाएं कोने (r2, c2) को परिभाषित करना होगा, जो (i-k, j-k) से (i+k, j+k) तक की सीमा में हैं।
सीमाओं का प्रबंधन: r1, c1, r2, c2 की गणना करते समय, हमें यह सुनिश्चित करना होगा कि वे मैट्रिक्स की वैध सीमाओं के भीतर रहें (0 से m-1 और 0 से n-1 तक)।
ब्लॉक योग सूत्र (प्रीफिक्स का उपयोग करके): एक बार r1, c1, r2, c2 परिभाषित हो जाने के बाद, ब्लॉक का योग प्रीफिक्स मैट्रिक्स का उपयोग करके गणना की जाती है: प्रीफिक्स[r2+1][c2+1] - प्रीफिक्स[r1][c2+1] - प्रीफिक्स[r2+1][c1] + प्रीफिक्स[r1][c1]। यह 2D रेंज योग सूत्र का एक अनुप्रयोग है।

यह चरण दर्शाता है कि कैसे पूर्व-गणना किए गए 2D प्रीफिक्स योग का उपयोग करके, हम प्रत्येक सेल के लिए ब्लॉक योग की गणना बहुत तेज़ी से कर सकते हैं।

सेल (i, j) के लिए k=1 के साथ, ऊपरी-बाएं कोने (r1, c1) को max(0, i-1) और max(0, j-1) के रूप में और निचले-दाएं कोने (r2, c2) को min(m-1, i+1) और min(n-1, j+1) के रूप में परिभाषित किया जाएगा। फिर, इन कोनों का उपयोग करके प्रीफिक्स योग सूत्र लागू किया जाएगा।

अनुकूलित समय जटिलता: प्रीफिक्स सम मैट्रिक्स बनाने में O(m*n) समय लगता है, और फिर उत्तर मैट्रिक्स भरने में भी O(m*n) समय लगता है। कुल समय जटिलता O(m*n) है।
स्थान जटिलता: हमें मूल मैट्रिक्स के अलावा एक प्रीफिक्स मैट्रिक्स और एक उत्तर मैट्रिक्स की आवश्यकता होती है, इसलिए स्थान जटिलता O(m*n) है।
महत्व: यह दृष्टिकोण ब्रूट-फोर्स की तुलना में काफी अधिक कुशल है, खासकर बड़े इनपुट आकार और k मानों के लिए, जिससे यह एक व्यावहारिक समाधान बन जाता है।

O(m*n) की समय जटिलता इस समस्या को विभिन्न कोडिंग प्लेटफार्मों पर स्वीकार्य बनाती है और बड़े डेटासेट को संभालने के लिए एक कुशल तरीका प्रदान करती है।

यदि मूल मैट्रिक्स 100x100 है, तो ब्रूट-फोर्स दृष्टिकोण (k=50 के साथ) लगभग 100*100*50*50 = 25,000,000 संचालन कर सकता है, जबकि अनुकूलित दृष्टिकोण केवल 2*100*100 = 20,000 संचालन करेगा।

Key takeaways

12D मैट्रिक्स में ब्लॉक सम की गणना के लिए ब्रूट-फोर्स दृष्टिकोण अक्षम है क्योंकि यह बार-बार समान उप-क्षेत्रों के योग की गणना करता है।
22D प्रीफिक्स सम एक शक्तिशाली तकनीक है जो किसी भी आयताकार उप-मैट्रिक्स के योग की गणना को O(1) समय में सक्षम बनाती है।
32D प्रीफिक्स सम मैट्रिक्स बनाने के लिए, प्रत्येक सेल (i, j) मूल मैट्रिक्स के (0,0) से (i-1, j-1) तक के योग को संग्रहीत करता है।
42D प्रीफिक्स योग सूत्र है: P[i][j] = M[i-1][j-1] + P[i-1][j] + P[i][j-1] - P[i-1][j-1], जहां P प्रीफिक्स मैट्रिक्स है और M मूल मैट्रिक्स है।
5ब्लॉक सम की गणना के लिए, हम लक्ष्य क्षेत्र के कोनों (r1, c1) और (r2, c2) को परिभाषित करते हैं और 2D रेंज योग सूत्र का उपयोग करके प्रीफिक्स योग मैट्रिक्स से योग प्राप्त करते हैं।
6अनुकूलित दृष्टिकोण की समय जटिलता O(m*n) है, जो ब्रूट-फोर्स की तुलना में बहुत बेहतर है।

Key terms

Matrix Block Sum2D Prefix SumRunning Sum of 2D ArrayBrute Force ApproachOptimized ApproachTime ComplexitySpace ComplexityRange Sum QuerySub-matrix Sum

Test your understanding

1ब्रूट-फोर्स दृष्टिकोण 2D मैट्रिक्स में ब्लॉक सम की गणना के लिए क्यों अक्षम है?
22D प्रीफिक्स सम मैट्रिक्स का निर्माण कैसे किया जाता है और यह किस जानकारी को संग्रहीत करता है?
32D प्रीफिक्स योग सूत्र क्या है और यह ओवरलैप को कैसे संभालता है?
42D प्रीफिक्स सम का उपयोग करके किसी दिए गए सेल (i, j) के लिए ब्लॉक योग की गणना करने के लिए आवश्यक सूत्र क्या है?
5इस समस्या को हल करने के लिए अनुकूलित दृष्टिकोण की समय और स्थान जटिलता क्या है?