टीएल;डीआर

  • समस्या: डेटा संरचनाओं और एल्गोरिदम के लिए समय और स्थान जटिलता (टाइम एंड स्पेस कॉम्प्लेक्सिटी) का अनुकूलन।
  • दृष्टिकोण: अगर कोई सेल ० है तो पूरी पंक्ति और स्तंभ ० कर दें। पहले ब्रूट फोर्स, फिर जावा में पहली पंक्ति/स्तंभ फ्लैग से O(१) अतिरिक्त जगह।
  • जटिलता: सीमांत मामलों (एज केसेस) के प्रबंधन के साथ इष्टतम समय और मेमोरी संतुलन।

थिएटर की सीट चार्ट सोचें। अगर एक सीट टूटी है, तो पूरी पंक्ति और पूरा स्तंभ बंद कर देते हैं ताकि उस क्रॉस पर कोई न बैठे। चार्ट पूर्णांकों का मैट्रिक्स है। शून्य का मतलब "टूटी"। आपका काम हर टूटी सीट का नियम जगह पर (in place) लागू करना है, बिना दूसरी पूरी चार्ट बनाए अगर बच सकें।

यह Cracking the Coding Interview शैली की समस्या १.८ Zero Matrix है, अध्याय १ (ऐरे and Strings) से। सीटीसीआई जावा श्रृंखला का हिस्सा। मूल व्याख्या और कोड, किताब की नकल नहीं।

साधारण भाषा में समस्या

इनपुट: पूर्णांकों का M x N मैट्रिक्स (जावा में अक्सर int[][])।

आउटपुट: मैट्रिक्स को बदलें ताकि अगर matrix[i][j] == 0 हो, तो पंक्ति i की हर प्रविष्टि और स्तंभ j की हर प्रविष्टि 0 हो जाए।

महत्वपूर्ण नियम:

  • अगर माँगा जाए तो जगह पर करें (बहुत आम फॉलो-अप)।
  • कई शून्य एक पंक्ति या स्तंभ साझा कर सकते हैं। दो बार शून्य करना ठीक है; परिणाम ऐसा लगे जैसे सभी नियम चले।
  • साफ करते समय लिखे गए शून्य नए "मूल शून्य" नियम न बनाएँ। यही क्लासिक जाल है।

उदाहरण:

पहले:                   बाद में:
1  2  3  0              0  0  0  0
5  6  7  8       →      5  6  7  0
9  0 11 12              0  0  0  0

पंक्ति ० में स्तंभ ३ पर शून्य है। पंक्ति २ में स्तंभ १ पर शून्य है। पंक्ति ० और २ खत्म, स्तंभ १ और ३ भी।

कोड से पहले कैसे सोचें

ब्रूट फोर्स (और यह क्यों टूटता है)

स्कैन करते हुए शून्य खोजें, और मिलते ही उसकी पंक्ति व स्तंभ तुरंत शून्य कर दें।

बग: स्कैन के बीच गैर-शून्य को शून्य बना देते हैं। बाद में उन नए शून्यों को मूल मानकर आधा मैट्रिक्स गलती से मिटा देते हैं।

बेहतर: अतिरिक्त ऐरे के साथ दो पास

१. पहला पास: किन पंक्तियों और किन स्तंभों को शून्य करना है, लिख लें। लंबाई M का boolean[] zeroRow और लंबाई N का boolean[] zeroCol। २. दूसरा पास: हर सेल (r, c) पर, अगर zeroRow[r] या zeroCol[c] तो 0 लिखें।

समय O(MN)। अतिरिक्त जगह O(M + N)। अगर कॉन्स्टेंट जगह न माँगें तो यह साफ इंटरव्यू जवाब है।

पसंदीदा: पहली पंक्ति और पहले स्तंभ से O(१) अतिरिक्त जगह

मैट्रिक्स खुद फ्लैग रख सकता है।

  • पंक्ति ० को स्तंभ फ्लैग बनाएँ: अगर स्तंभ c शून्य होना है तो matrix[0][c] = 0।
  • स्तंभ ० को पंक्ति फ्लैग बनाएँ: अगर पंक्ति r शून्य होनी है तो matrix[r][0] = 0।
  • सेल matrix[0][0] दोनों में है। दो बूलियन रखें, firstRowHasZero और firstColHasZero, कि पंक्ति ० और स्तंभ ० खुद शून्य होने चाहिए या नहीं।

क्रम मायने रखता है:

१. केवल पहली पंक्ति और पहला स्तंभ स्कैन कर दो बूलियन सेट करें। २. बाकी मैट्रिक्स (r >= 1, c >= 1) स्कैन करें। शून्य पर matrix[r][0] = 0 और matrix[0][c] = 0 मार्क करें। ३. अंदरूनी हिस्से का दूसरा पास: अगर matrix[r][0] == 0 या matrix[0][c] == 0 तो matrix[r][c] = 0। ४. आखिर में जरूरत हो तो पहली पंक्ति शून्य करें, फिर पहला स्तंभ। फ्लैग जल्दी मिटाने से बचने के लिए इन्हें अंत में करें।

पूरा ट्रिक यही है: हिसाब किनारे पर रखें, अंदर पहले लगाएँ, किनारा अंत में ठीक करें।

जावा समाधान (O(१) अतिरिक्त जगह)

public final class ZeroMatrix {

    private ZeroMatrix() {}

    /**
     * If any cell is 0, set its entire row and column to 0.
     * Mutates matrix in place. O(1) extra space via first row/col flags.
     */
    public static void setZeros(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return;
        }

        int rows = matrix.length;
        int cols = matrix[0].length;

        boolean firstRowHasZero = false;
        boolean firstColHasZero = false;

        // Does row 0 already contain a zero?
        for (int c = 0; c < cols; c++) {
            if (matrix[0][c] == 0) {
                firstRowHasZero = true;
                break;
            }
        }

        // Does column 0 already contain a zero?
        for (int r = 0; r < rows; r++) {
            if (matrix[r][0] == 0) {
                firstColHasZero = true;
                break;
            }
        }

        // Use first row / first col as flags for the rest of the matrix.
        for (int r = 1; r < rows; r++) {
            for (int c = 1; c < cols; c++) {
                if (matrix[r][c] == 0) {
                    matrix[r][0] = 0;
                    matrix[0][c] = 0;
                }
            }
        }

        // Zero interior cells based on flags.
        for (int r = 1; r < rows; r++) {
            for (int c = 1; c < cols; c++) {
                if (matrix[r][0] == 0 || matrix[0][c] == 0) {
                    matrix[r][c] = 0;
                }
            }
        }

        // Zero first row last (it held column flags).
        if (firstRowHasZero) {
            for (int c = 0; c < cols; c++) {
                matrix[0][c] = 0;
            }
        }

        // Zero first column last (it held row flags).
        if (firstColHasZero) {
            for (int r = 0; r < rows; r++) {
                matrix[r][0] = 0;
            }
        }
    }
}

वैकल्पिक साफ संस्करण, जगह O(M + N) (वही विचार, अलग फ्लैग ऐरे):

public static void setZerosWithFlagArrays(int[][] matrix) {
    if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
        return;
    }
    int rows = matrix.length;
    int cols = matrix[0].length;
    boolean[] zeroRow = new boolean[rows];
    boolean[] zeroCol = new boolean[cols];

    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (matrix[r][c] == 0) {
                zeroRow[r] = true;
                zeroCol[c] = true;
            }
        }
    }

    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (zeroRow[r] || zeroCol[c]) {
                matrix[r][c] = 0;
            }
        }
    }
}

इंटरव्यू में पहले फ्लैग ऐरे से शुरू करें ताकि विचार साफ दिखे, फिर जब कॉन्स्टेंट जगह माँगें तो फ्लैग को पहली पंक्ति और पहले स्तंभ में समेटें।

जटिलता

तरीका समय अतिरिक्त जगह
स्कैन करते हुए तुरंत शून्य O(MN) बदतर स्थिति, पर गलत O(1)
फ्लैग ऐरे O(MN) O(M + N)
पहली पंक्ति / पहले स्तंभ फ्लैग O(MN) O(1)

हर सेल कम से कम एक बार देखना पड़ता है, इसलिए समय O(MN) अपेक्षित है। लड़ाई जगह की है, और उन शून्यों से स्कैन को जहर न देने की जो आपने अभी लिखे।

किनारे के मामले जो इंटरव्यूअर छूते हैं

  • नल या खाली मैट्रिक्स। क्रैश किए बिना लौटें।
  • १ x १. [0] [0] रहता है। [5] [5] रहता है।
  • एक पंक्ति या एक स्तंभ। पहली पंक्ति / पहले स्तंभ फ्लैग फिर भी चलते हैं; अंदरूनी लूप कुछ नहीं करते।
  • शून्य सिर्फ matrix[0][0] पर। दोनों बूलियन true हो जाते हैं। पूरी पहली पंक्ति और पूरा पहला स्तंभ साफ। अगर और शून्य न हों तो अंदर रह सकता है।
  • हर सेल पहले से शून्य। परिणाम सब शून्य। ठीक।
  • कोई शून्य नहीं। मैट्रिक्स नहीं बदलता। स्कैन फिर भी O(MN) खर्च करता है।
  • आयताकार, वर्ग नहीं। कोड rows और cols अलग रखता है। वर्ग कभी न मानें।
  • ऋणात्मक और धनात्मक। सिर्फ 0 ट्रिगर करता है। दूसरी भाषाओं के "falsy" विचार न लाएँ।

आम गलतियाँ

१. खोज पास के दौरान शून्य करना। नकली मूल शून्य बनाता है। २. पहली पंक्ति या पहला स्तंभ फ्लैग के रूप में इस्तेमाल से पहले साफ करना। नक्शा खो जाता है। ३. दो बूलियन भूलना और matrix[0][0] पर "पंक्ति ० मरे" और "स्तंभ ० मरे" दोनों बिना सावधानी लादना। ४. वर्ग मैट्रिक्स मानना और दोनों आयामों के लिए एक ही लंबाई इस्तेमाल करना। ५. नई मैट्रिक्स लौटाना जब प्रश्न जगह पर कहता हो (जगह बर्बाद, पहचान जाँच वाले टेस्ट फेल)।

दोस्त को समझाएँ

आपके पास एक ग्रिड है। कोई भी शून्य मतलब "यह पूरी पंक्ति और यह पूरा स्तंभ मार दो"। अगर खोजते-खोजते मारते रहें तो नए शून्य गढ़ लेते हैं और ज्यादा मार देते हैं। इसलिए पहले याद रखें कौन सी पंक्तियाँ और स्तंभ मरने चाहिए। यह दो बूलियन ऐरे में रख सकते हैं, या उन्हीं यादों को ग्रिड की पहली पंक्ति और पहले स्तंभ पर लिख सकते हैं, पहली पंक्ति और पहले स्तंभ के लिए दो छोटे बूलियन के साथ। फिर उन यादों से बीच भरें। अंत में ही, अगर चिह्नित हों तो पहली पंक्ति और पहला स्तंभ साफ करें।

समय सेल की संख्या के अनुपात में है। अगर मैट्रिक्स के किनारे को नोटबुक बना लें तो अतिरिक्त मेमोरी कॉन्स्टेंट रह सकती है।

श्रृंखला

फ्लैग-ऐरे संस्करण ठंडे दिमाग से लिख सकें तब तक अभ्यास करें, फिर बॉर्डर-फ्लैग संस्करण एक बार बिना देखे। दूसरा संस्करण दिखाता है कि दबाव में भी स्टेट सावधानी से संभाल सकते हैं।