कोडिंग इंटरव्यू: इटरेटिव DFS के साथ द्वीपों (Islands) की संख्या गिनना

समस्या और यह कब लागू होती है

केवल भूमि के लिए "1" और पानी के लिए "0" वाले एक m × n ग्रिड को देखते हुए, द्वीपों की संख्या लौटाएं। दो भूमि सेल केवल तभी जुड़े होते हैं जब वे एक क्षैतिज या लंबवत किनारा साझा करते हैं। एक द्वीप भूमि सेल्स का एक अधिकतम कनेक्टेड सेट होता है।

बाध्यताएं 1 <= m, n <= 300 हैं। कॉलर अनुबंध को रनटाइम विफलता में बदलने के बजाय, कार्यान्वयन अभी भी एक खाली ऐरे के खिलाफ सुरक्षा प्रदान करता है। मान लें कि ग्रिड को संशोधित किया जा सकता है। यदि कॉलर को इसे बनाए रखना है, तो इसके बजाय समान आकार के visited मैट्रिक्स का उपयोग करें।

यह सॉफ्टवेयर इंजीनियरिंग कोडिंग राउंड के लिए एक सामान्य एल्गोरिदम प्रश्न है। यह परीक्षण करता है कि क्या कोई उम्मीदवार मैट्रिक्स को एक अंतर्निहित ग्राफ के रूप में मॉडल कर सकता है, कनेक्टेड घटकों को पार कर सकता है, और जटिलता विश्लेषण के साथ कार्यान्वयन को सुसंगत रख सकता है।

इंटरव्यूअर क्या मूल्यांकन करता है

एक मजबूत उत्तर प्रत्येक भूमि सेल को एक शीर्ष (vertex) और प्रत्येक चार-दिशात्मक भूमि निकटता को एक किनारे (edge) के रूप में मानता है। इससे मुख्य नियम बनता है: जब भी स्कैन बिना विज़िट की गई भूमि तक पहुंचता है, तो उसे एक नया कनेक्टेड घटक मिल जाता है। इसे एक बार गिनें, फिर पूरे द्वीप को पार करें और चिह्नित करें ताकि इसे दोबारा न गिना जा सके।

कार्यान्वयन विवरण मायने रखते हैं। किसी पड़ोसी सेल को तब मार्क करें जब उसे पुश किया जाए, न कि तब जब उसे पॉप किया जाए; अन्यथा कई आसन्न सेल एक ही सेल को पुश कर सकते हैं। जब अधिकांश ग्रिड एक ही द्वीप होता है, तो इटरेटिव DFS एक गहरे लैंग्वेज कॉल स्टैक से बचाता है। एक सटीक उत्तर यह भी बताता है कि इन-प्लेस मार्किंग visited मैट्रिक्स को हटा देती है, जबकि स्पष्ट स्टैक अभी भी सबसे खराब स्थिति में O(mn) स्थान घेर सकता है।

एक कमजोर उत्तर कनेक्टिविटी, इनपुट म्यूटेशन, शुद्धता अपरिवर्तनीय (correctness invariant), या प्रतिकूल परीक्षणों को परिभाषित किए बिना केवल "DFS का उपयोग करें" कहता है।

पहले स्पष्ट करने योग्य प्रश्न

• क्या विकर्ण (diagonals) जुड़ते हैं? यह समस्या चार दिशाओं का उपयोग करती है। यदि आठ दिशाएं गिनी जाती हैं, तो दिशा सूची का विस्तार करें और कुछ उत्तरों के बदलने की उम्मीद करें।
• क्या इनपुट को संशोधित किया जा सकता है? यदि हाँ, तो विज़िट किए गए "1" सेल्स को "0" में बदलें। अन्यथा visited का उपयोग करें, समय सीमा को बनाए रखते हुए O(mn) स्टोरेज जोड़ें।
• क्या ग्रिड आयताकार और गैर-रिक्त है? प्रॉम्प्ट दोनों की गारंटी देता है; प्रोडक्शन कोड अभी भी खाली इनपुट के लिए 0 लौटा सकता है। एक असमान ऐरे (jagged array) को प्रत्येक पंक्ति के आधार पर सीमाओं की आवश्यकता होगी।
• क्या यह एक स्थिर गणना है या प्रत्येक भूमि प्रविष्टि के बाद की गणना है? DFS या BFS स्थिर ग्रिड के लिए उपयुक्त है। वृद्धिशील प्रविष्टियाँ डिसजॉइंट सेट यूनियन (disjoint set union) का समर्थन करती हैं।
• आकार और कॉल-स्टैक की सीमाएं क्या हैं? 300×300 का पूरी तरह से भूमि वाला ग्रिड 90,000 रिकर्सिव कॉल्स वाला एक पथ बना सकता है, इसलिए यह समाधान एक स्पष्ट स्टैक का उपयोग करता है।

30-सेकंड उत्तर रूपरेखा

"मैं भूमि सेल्स को एक अंतर्निहित ग्राफ में शीर्षों के रूप में मॉडल करूँगा, जिसमें चार-दिशात्मक निकटता किनारों के रूप में होगी। मैं पंक्ति दर पंक्ति ग्रिड को स्कैन करता हूँ। प्रत्येक शेष 1 एक असंसाधित कनेक्टेड घटक शुरू करता है, इसलिए मैं द्वीप गणना बढ़ाता हूँ और इससे इटरेटिव DFS चलाता हूँ। मैं पुश करते समय भूमि पड़ोसी को 0 में बदल देता हूँ, जो डुप्लिकेट पुश को रोकता है। प्रत्येक सेल को अधिकतम एक बार पुश किया जाता है, और एक स्पष्ट स्टैक गहरे रिकर्शन से बचाता है। समय जटिलता O(mn) है, और सबसे खराब स्थिति में स्टैक O(mn) है। यदि संशोधन निषिद्ध है, तो मैं उसी स्थिति को एक visited मैट्रिक्स में संग्रहीत करूँगा।"

चरण-दर-चरण गहन विश्लेषण

चरण 1: सरल खोज में दोहराए गए कार्य को पहचानें

प्रत्येक भूमि सेल से एक नई खोज शुरू करने से एक ही द्वीप कई बार पार हो जाएगा। पड़ोसियों को खोजना बाधा नहीं है; गायब हिस्सा वह स्थिति है जो खोजों के दौरान बनी रहती है और रिकॉर्ड करती है कि एक सेल पहले से ही गिने गए घटक से संबंधित है।

एक पूर्ण स्कैन और स्थायी विज़िटेशन चिह्न उस पुनरावृत्ति को हटा देते हैं। केवल उस भूमि से ट्रैवर्सल शुरू करें जो अनविज़िटेड रहती है।

चरण 2: गणना अपरिवर्तनीय स्थापित करें

जब स्कैन (r, c) तक पहुंचता है, तो प्रत्येक पिछले DFS ने ठीक एक पूर्ण द्वीप को चिह्नित किया है। यदि वर्तमान सेल अभी भी "1" है, तो उनमें से कोई भी ट्रैवर्सल उस तक नहीं पहुंचा, इसलिए इसे एक नया द्वीप शुरू करना चाहिए और गणना एक से बढ़ जाती है।

DFS केवल चार-दिशात्मक भूमि किनारों का अनुसरण करता है, इसलिए यह पानी को पार नहीं कर सकता है और अलग-अलग द्वीपों को मिला नहीं सकता है। यह अपनी शुरुआत से जुड़े प्रत्येक भूमि सेल तक भी पहुंचता है, इसलिए यह द्वीप बाद में किसी अन्य गणना को ट्रिगर नहीं कर सकता है। ये दो तथ्य साबित करते हैं कि न तो कम गिनती होती है और न ही दोहरी गिनती।

चरण 3: पुश करते समय चिह्नित करें

मान लीजिए कि एक अचिह्नित सेल स्टैक में पहले से मौजूद दो सेल्स को छूता है। यदि मार्किंग पॉप समय तक प्रतीक्षा करती है, तो दोनों पड़ोसी उस सेल को पुश कर सकते हैं। परिणाम अक्सर अभी भी सही होता है, लेकिन स्टैक में डुप्लिकेट काम होता है और सटीक जटिलता तर्क खो जाता है।

एक खोजे गए पड़ोसी को पुश करने से पहले "0" में बदलें। कोई भी बाद का किनारा तब इसे विज़िट किए गए के रूप में देखेगा, यह गारंटी देते हुए कि प्रत्येक भूमि सेल स्टैक में अधिकतम एक बार प्रवेश करता है।

चरण 4: इटरेटिव DFS लागू करें

function numIslands(grid) {
  if (grid.length === 0 || grid[0].length === 0) return 0;

  const rows = grid.length;
  const cols = grid[0].length;
  const directions = [[1, 0], [-1, 0], [0, 1], [0, -1]];
  let islands = 0;

  for (let row = 0; row < rows; row += 1) {
    for (let col = 0; col < cols; col += 1) {
      if (grid[row][col] !== "1") continue;

      islands += 1;
      grid[row][col] = "0";
      const stack = [[row, col]];

      while (stack.length > 0) {
        const [currentRow, currentCol] = stack.pop();

        for (const [rowOffset, colOffset] of directions) {
          const nextRow = currentRow + rowOffset;
          const nextCol = currentCol + colOffset;

          if (
            nextRow >= 0 && nextRow < rows &&
            nextCol >= 0 && nextCol < cols &&
            grid[nextRow][nextCol] === "1"
          ) {
            grid[nextRow][nextCol] = "0";
            stack.push([nextRow, nextCol]);
          }
        }
      }
    }
  }

  return islands;
}

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

चरण 5: सीमाओं और प्रतिकूल मामलों को मान्य करें

कम से कम, परीक्षण करें: एक खाली ऐरे 0 लौटाता है; एक पानी का सेल 0 लौटाता है; एक भूमि सेल 1 लौटाता है; पूरा पानी 0 लौटाता है; पूरी भूमि 1 लौटाती है; केवल तिरछे छूने वाले दो सेल 2 लौटाते हैं; तीन अलग-अलग क्षेत्रों वाला नमूना 3 लौटाता है; और एक 300×300 का सर्व-भूमि ग्रिड रिकर्सिव कॉल स्टैक को ओवरफ्लो नहीं करता है।

म्यूटेशन अनुबंध का भी परीक्षण करें। यदि किसी अन्य दावे को कॉल के बाद मूल ग्रिड की आवश्यकता है, तो पहले इसे कॉपी करें या visited का उपयोग करें। यह विकल्प इंटरफ़ेस अनुबंध में होना चाहिए, न कि एक छिपे हुए कार्यान्वयन विवरण के रूप में।

चरण 6: विकल्पों की तुलना करें

BFS और इटरेटिव DFS में यहाँ समान समय और सबसे खराब स्थिति वाला स्थान होता है। BFS चुनें जब दूरी की परतें मायने रखती हों; जब एकमात्र लक्ष्य किसी घटक को समाप्त करना हो तो दोनों में से कोई भी उपयुक्त है। रिकर्सिव DFS केवल तभी छोटा होता है जब इनपुट काफी छोटा हो या भाषा पर्याप्त गहराई की गारंटी देती हो। डिसजॉइंट सेट यूनियन तब उपयोगी होता है जब भूमि वृद्धिशील रूप से आती है और प्रत्येक प्रविष्टि के बाद गणना का अनुरोध किया जाता है; यह एक स्थिर गणना के लिए अनावश्यक इंडेक्सिंग और सेट रखरखाव जोड़ता है।

उच्च गुणवत्ता वाला नमूना उत्तर

"यह समस्या एक अंतर्निहित अप्रत्यक्ष ग्राफ में कनेक्टेड घटकों की गिनती है। प्रत्येक 1 एक शीर्ष है, और क्षैतिज या लंबवत भूमि पड़ोसी एक किनारा साझा करते हैं। मैं पूरे ग्रिड को स्कैन करता हूँ। यदि कोई स्थिति अभी भी 1 है, तो कोई भी पिछली खोज उस तक नहीं पहुंची है, इसलिए मुझे एक नया द्वीप मिला है और मैं गिनती बढ़ाता हूँ। फिर मैं इटरेटिव DFS चलाता हूँ और उस पूरे द्वीप को 0 में बदल देता हूँ।

मैं पड़ोसियों को पुश करते समय चिह्नित करता हूँ ताकि दो आसन्न सेल एक ही स्थिति को पुश न कर सकें। मैं एक स्पष्ट स्टैक का उपयोग करता हूँ क्योंकि 300×300 का ऑल-लैंड ग्रिड एक बहुत गहरा रिकर्सिव पथ बना सकता है। प्रत्येक सेल को अधिकतम एक बार संसाधित किया जाता है और चार दिशाओं की जांच की जाती है, जिससे O(mn) समय और O(mn) सबसे खराब स्थिति वाला स्टैक स्पेस मिलता है। यह संस्करण इनपुट को म्यूटेट करता है; यदि इंटरफ़ेस को इसे संरक्षित करना चाहिए, तो मैं चिह्नों को O(mn) visited मैट्रिक्स में स्थानांतरित कर दूंगा। मैं विकर्ण गैर-कनेक्टिविटी, ऑल-वाटर, ऑल-लैंड और खाली-इनपुट सीमाओं को सत्यापित करूँगा।"

यह उत्तर याद किए गए लेबल पर निर्भर किए बिना मॉडल, गिनती के तर्क, कार्यान्वयन जोखिम, साइड इफेक्ट और सत्यापन को जोड़ता है।

सामान्य गलतियाँ

• विकर्णों को जुड़ा हुआ मानना → यह समस्या को बदल देता है और द्वीपों की कम गिनती कर सकता है → दिशा सूची में केवल ऊपर, नीचे, बाएं और दाएं रखें।
• केवल पॉप करते समय मार्क करना → कई पड़ोसी एक ही सेल को पुश कर सकते हैं → पुश करने से ठीक पहले एक वैध पड़ोसी को चिह्नित करें।
• यह दावा करना कि इन-प्लेस का अर्थ O(1) स्थान है → यह सबसे खराब स्थिति वाले स्पष्ट स्टैक की उपेक्षा करता है → सबसे खराब स्थिति में O(mn) सहायक स्थान की रिपोर्ट करें।
• गहराई पर चर्चा किए बिना रिकर्सिव DFS का उपयोग करना → एक बड़ा द्वीप भाषा कॉल स्टैक को समाप्त कर सकता है → इटरेशन का उपयोग करें या एक सुरक्षित आकार सीमा स्थापित करें।
• कॉलर डेटा को चुपचाप म्यूटेट करना → बाद का कोड एक साफ़ ग्रिड देखता है → साइड इफेक्ट का दस्तावेजीकरण करें या visited का उपयोग करें।
• प्रत्येक भूमि सेल से फिर से खोजना → एक ही घटक को बार-बार पार किया जाता है → केवल बिना विज़िट की गई भूमि से शुरू करें।
• केवल सामान्य आयतों का परीक्षण करना → खाली, सभी पानी, सभी भूमि और विकर्ण जवाबी उदाहरण अप्रयुक्त रहते हैं → न्यूनतम, चरम और प्रतिकूल मामलों को कवर करें।

फॉलो-अप प्रश्न और उत्तर

फॉलो-अप 1: क्या होगा यदि इनपुट को संशोधित नहीं किया जा सकता है?

एक m × n बूलियन मैट्रिक्स आवंटित करें और इसे पुश करते समय विज़िट किए गए स्थान के रूप में चिह्नित करें। गणना अपरिवर्तनीय और O(mn) समय अपरिवर्तित रहता है; अतिरिक्त स्टोरेज स्पष्ट रूप से O(mn) है। इनपुट की प्रतिलिपि बनाने में समान स्पर्शोन्मुख (asymptotic) स्थान लागत होती है लेकिन शब्दार्थ (semantics) भिन्न होते हैं।

फॉलो-अप 2: क्या होगा यदि विकर्ण भी जुड़ते हैं?

दिशा सूची को चार ऑफसेट से बढ़ाकर आठ करें; ट्रैवर्सल ढांचा अपरिवर्तित रहता है। पहले [[1, 0], [0, 1]] जैसे मामले के साथ नियम की पुष्टि करें: चार-दिशात्मक उत्तर 2 है, जबकि आठ-दिशात्मक उत्तर 1 है।

फॉलो-अप 3: क्या होगा यदि भूमि एक समय में एक सेल जोड़ी जाती है और प्रत्येक गणना का अनुरोध किया जाता है?

स्थिर DFS को दोहराने से काम व्यर्थ होता है। इसके बजाय डिसजॉइंट सेट यूनियन का उपयोग करें: एक नया भूमि सेल शुरू में गणना को बढ़ाता है, फिर प्रत्येक मौजूदा भूमि पड़ोसी के साथ यूनियन करता है। दो अलग-अलग सेटों का प्रत्येक सफल यूनियन गणना को घटाता है। डुप्लिकेट प्रविष्टियों को नजरअंदाज किया जाना चाहिए ताकि वे दो बार न बढ़ें।

फॉलो-अप 4: क्या होगा यदि निर्देशांक सीमा बहुत बड़ी है लेकिन भूमि विरल (sparse) है?

पूरा मैट्रिक्स आवंटित न करें। केवल भूमि निर्देशांक को एक हैश सेट में संग्रहीत करें, उन निर्देशांकों को पार करें, और चार पड़ोसियों की जांच करें। k भूमि सेल्स के साथ, अपेक्षित समय O(k) है, और विज़िट किया गया सेट प्लस स्टैक O(k) है। इस निष्कर्ष के लिए एक विरल निर्देशांक-सूची प्रतिनिधित्व की आवश्यकता होती है; यह एक घने ग्रिड इनपुट से नहीं निकलता है।