पायथन में रो-वाइज और कॉलम-वाइज सॉर्टेड मैट्रिक्स में नेगेटिव नंबर गिनना

इस लेख में हम एक ऑप्टिमल एल्गोरिदम देखेंगे जो रो-वाइज और कॉलम-वाइज सॉर्टेड मैट्रिक्स में नेगेटिव नंबरों को कुशलतापूर्वक गिनता है।

रो-वाइज और कॉलम-वाइज सॉर्टेड मैट्रिक्स

ऐसे मैट्रिक्स में प्रत्येक तत्व अपने दाएं और नीचे के तत्वों से छोटा या बराबर होता है। उदाहरण:

M = [[-40, -12, 1, 5],
     [-20, -2, 5, 15],
     [-22, -1, 13, 18],
     [-12, 0, 15, 38]]

यहां M[0][0] = -40 अपने दाएं (-12) और नीचे (-20) के तत्वों से छोटा है, और यह पैटर्न पूरे मैट्रिक्स में बना रहता है।

ऑप्टिमल एल्गोरिदम: O(m + n) समय

साधारण O(m×n) ट्रैवर्सल के बजाय, हम ऊपरी-दाएं कोने से शुरू करके रैखिक समय में गिनती कर सकते हैं।

matrix = [
    [-40, -12, 1, 5],
    [-20, -2, 5, 15],
    [-22, -1, 13, 18],
    [-12, 0, 15, 38]
]

row_count = len(matrix)
col_count = len(matrix[0])

count = 0
row = 0
col = col_count - 1  # ऊपरी-दाएं कोने से शुरू

while row < row_count and col >= 0:
    if matrix[row][col] < 0:
        # वर्तमान कॉलम में इस रो और नीचे के सभी तत्व नेगेटिव हैं
        count += (row_count - row)
        col -= 1  # बाएं जाएं
    else:
        row += 1  # नीचे जाएं

print("नेगेटिव इंटीजर्स की संख्या:", count)
# आउटपुट: 7

एल्गोरिदम समझाया

1. ऊपरी-दाएं कोने से शुरू करें (सबसे बड़ा तत्व उस रो में, सबसे छोटा उस कॉलम में)।
2. यदि तत्व नेगेटिव है: उस कॉलम में वर्तमान रो से नीचे के सभी तत्व भी नेगेटिव होंगे (क्योंकि कॉलम सॉर्टेड है)। गिनती में जोड़ें और बाएं जाएं।
3. यदि तत्व नॉन-नेगेटिव है: उस रो में बाएं के सभी तत्व भी नॉन-नेगेटिव होंगे (क्योंकि रो सॉर्टेड है)। नीचे जाएं।
4. प्रक्रिया तब तक दोहराएं जब तक मैट्रिक्स की सीमा पार न हो जाए।

सामान्यीकरण

यह एल्गोरिदम किसी भी मान k से छोटे तत्वों को गिनने के लिए अनुकूलित किया जा सकता है - बस शर्त matrix[row][col] < 0 को matrix[row][col] < k में बदलें।

जटिलता

• समय: O(m + n) जहां m पंक्तियाँ और n कॉलम हैं।
• स्थान: O(1) अतिरिक्त स्थान।

यह दृष्टिकोण बड़े मैट्रिक्स के लिए पूर्ण ट्रैवर्सल से कहीं अधिक कुशल है।