पायथन में स्काईलाइन बरकरार रखते हुए कॉन्डोमिनियम की ऊंचाई को अधिकतम करने का प्रोग्राम

एक 2D मैट्रिक्स दिया गया है जहां matrix[r][c] शहर में एक कॉन्डोमिनियम की ऊंचाई दर्शाता है। पश्चिम-पूर्व स्काईलाइन मैट्रिक्स की प्रत्येक पंक्ति के अधिकतम मान से दिखाई देती है, जबकि उत्तर-दक्षिण स्काईलाइन प्रत्येक स्तंभ के अधिकतम मान से दिखाई देती है। हमें एक नया मैट्रिक्स ढूंढना है जहां प्रत्येक कॉन्डोमिनियम की ऊंचाई को अधिकतम संभव ऊंचाई तक बढ़ाया जाए, लेकिन दोनों स्काईलाइन अपरिवर्तित रहें।

उदाहरण

इनपुट मैट्रिक्स:

[[2, 3, 4],
 [5, 6, 7],
 [8, 9, 10]]

पंक्ति अधिकतम (पश्चिम-पूर्व स्काईलाइन): [4, 7, 10]

स्तंभ अधिकतम (उत्तर-दक्षिण स्काईलाइन): [8, 9, 10]

आउटपुट मैट्रिक्स:

[[4, 4, 4],
 [7, 7, 7],
 [8, 9, 10]]

पहली पंक्ति के सभी मान 4 हो जाते हैं (क्योंकि पंक्ति अधिकतम 4 है और स्तंभ अधिकतम 8, 9, 10 हैं, इसलिए न्यूनतम 4 लिया जाता है)। दूसरी पंक्ति के सभी मान 7 हो जाते हैं। तीसरी पंक्ति अपरिवर्तित रहती है क्योंकि इसके मान पहले से ही स्काईलाइन से मेल खाते हैं।

एल्गोरिदम

1. प्रत्येक पंक्ति का अधिकतम मान निकालकर सूची row_max बनाएं।
2. प्रत्येक स्तंभ का अधिकतम मान निकालकर सूची col_max बनाएं।
3. मैट्रिक्स के प्रत्येक सेल (i, j) के लिए, नया मान min(row_max[i], col_max[j]) सेट करें।
4. संशोधित मैट्रिक्स वापस करें।

पायथन कार्यान्वयन

class Solution:
    def solve(self, matrix):
        # पंक्ति और स्तंभ अधिकतम की गणना करें
        row_max = [max(row) for row in matrix]
        col_max = [max(col) for col in zip(*matrix)]
        
        # प्रत्येक सेल को अपडेट करें
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                matrix[i][j] = min(row_max[i], col_max[j])
        return matrix

# परीक्षण
ob = Solution()
matrix = [
    [2, 3, 4],
    [5, 6, 7],
    [8, 9, 10]
]
print(ob.solve(matrix))
# आउटपुट: [[4, 4, 4], [7, 7, 7], [8, 9, 10]]

समय और स्थान जटिलता

• समय जटिलता: O(m × n) जहां m पंक्तियों की संख्या है और n स्तंभों की संख्या है।
• स्थान जटिलता: O(m + n) पंक्ति और स्तंभ अधिकतम संग्रहीत करने के लिए।

मुख्य बिंदु

• स्काईलाइन अपरिवर्तित रखने के लिए, प्रत्येक सेल की ऊंचाई उसकी पंक्ति और स्तंभ के अधिकतम मान से अधिक नहीं हो सकती।
• इसलिए इष्टतम वृद्धि min(row_max[i], col_max[j]) है।
• यह समस्या लीटकोड "Max Increase to Keep City Skyline" के समान है।