पायथन में बाइनरी मैट्रिक्स में बाएं सबसे 1 वाले स्तंभ का सूचकांक ढूंढने का प्रोग्राम

एक 2D बाइनरी मैट्रिक्स दिया गया है जहां प्रत्येक पंक्ति आरोही क्रम में सॉर्ट है (0s पहले, फिर 1s)। पूरे मैट्रिक्स में बाएं सबसे 1 वाले स्तंभ का सूचकांक ढूंढें। यदि कोई 1 नहीं है, तो -1 वापस करें।

उदाहरण

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

[[0, 0, 0, 1],
 [0, 0, 1, 1],
 [0, 0, 1, 1],
 [0, 0, 1, 0]]

आउटपुट: 2

स्तंभ 2 (0-आधारित) में सबसे बाएं 1 है।

एल्गोरिदम (सीढ़ी खोज / Staircase Search)

1. यदि मैट्रिक्स खाली है, तो -1 वापस करें।
2. N = पंक्तियाँ, M = स्तंभ।
3. i = 0 (पहली पंक्ति), j = M - 1 (अंतिम स्तंभ) से शुरू करें।
4. leftmost = -1।
5. जब तक i < N और j >= 0:
   • यदि matrix[i][j] == 0: नीचे जाएं (i += 1)।
   • अन्यथा (1 मिला): leftmost = j, बाएं जाएं (j -= 1)।
6. leftmost वापस करें।

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

class Solution:
    def solve(self, matrix):
        if not matrix or not matrix[0]:
            return -1
        N = len(matrix)
        M = len(matrix[0])
        i = 0
        j = M - 1
        leftmost = -1
        
        while i < N and j >= 0:
            if matrix[i][j] == 0:
                i += 1
            else:
                leftmost = j
                j -= 1
        return leftmost

# परीक्षण
ob = Solution()
matrix = [
    [0, 0, 0, 1],
    [0, 0, 1, 1],
    [0, 0, 1, 1],
    [0, 0, 1, 0]
]
print(ob.solve(matrix))  # 2
print(ob.solve([[0,0],[0,0]]))  # -1

क्यों काम करता है?

पंक्तियाँ सॉर्ट हैं, इसलिए यदि (i,j) पर 1 है, तो उसी पंक्ति में बाएं और 1 हो सकते हैं (इसलिए बाएं जाएं)। यदि 0 है, तो इस पंक्ति में और बाएं 0 ही होंगे (इसलिए नीचे जाएं)। यह O(N+M) में पूरे मैट्रिक्स को कवर करता है।

समय जटिलता

• O(N + M) समय।
• O(1) स्थान।
• बाइनरी सर्च प्रति पंक्ति (O(N log M)) से बेहतर।