कोडिंग इंटरव्यू: हिस्टोग्राम में सबसे बड़ा आयत (Largest Rectangle) कैसे खोजें?

समस्या और लागू होने वाले परिदृश्य

heights दिए जाने पर, प्रत्येक मान चौड़ाई 1 के एक हिस्टोग्राम बार को दर्शाता है। एक मान्य आयत एक या अधिक लगातार बार में फैला होता है, बेसलाइन से शुरू होता है, और उस विस्तार में सबसे छोटे बार से अधिक ऊँचा नहीं हो सकता। इसका अधिकतम क्षेत्रफल लौटाएँ।

heights = [2, 1, 5, 6, 2, 3]
answer = 10

सबसे अच्छा आयत इंडेक्स 2..3 को कवर करता है: इसकी ऊँचाई 5 है, चौड़ाई 2 है, और क्षेत्रफल 10 है। मानक प्रतिबंध 1 <= heights.length <= 100000 और 0 <= heights[i] <= 10000 हैं। यह लेख एक खाली इनपुट के लिए 0 लौटाने के रूप में भी परिभाषित करता है। मानक सीमाओं के तहत, क्षेत्रफल अधिकतम 10^9 है, जिसे जावास्क्रिप्ट के number प्रकार द्वारा सटीक रूप से दर्शाया जा सकता है।

वर्तमान अंग्रेजी साक्षात्कार-तैयारी सामग्री और एक स्वतंत्र चीनी सार्वजनिक समाधान दोनों इस सटीक समस्या को एक मोनोटोनिक-स्टैक अभ्यास के रूप में प्रस्तुत करते हैं। मूल समस्या और एक वर्तमान DSA गाइड समान चौड़ाई-1 मॉडल और प्रतिबंधों का उपयोग करते हैं। यह इसे किसी कंपनी के नाम का श्रेय दिए बिना या किसी असत्यापनीय आवृत्ति का दावा किए बिना एक प्रतिनिधि coding प्रश्न के रूप में मानने का समर्थन करता है।

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

पहला संकेत यह है कि क्या आप सीमाओं के प्रत्येक जोड़े की गणना किए बिना प्रत्येक संभावित आयत को मॉडल कर सकते हैं। किसी भी चुनी गई ऊँचाई के लिए, सबसे अच्छा आयत प्रत्येक तरफ पहले कड़ाई से छोटे (strictly shorter) बार तक फैलता है। यह एक ज्यामितीय दिखने वाली समस्या को निकटतम-छोटे-सीमा (nearest-smaller-boundary) प्रश्नों में बदल देता है।

दूसरा संकेत यह है कि क्या आप डेटा संरचना को प्राप्त कर सकते हैं। बढ़ती ऊँचाइयों का एक स्टैक उन बार्स को रखता है जिनकी दाहिनी सीमा अभी भी अज्ञात है। जब एक छोटा बार आता है, तो यह उन आयतों में से एक या अधिक को बंद कर देता है। वर्तमान इंडेक्स दाईं ओर उनकी पहली छोटी स्थिति है; प्रत्येक बार के साथ संग्रहीत प्रारंभ (start) पहले से ही यह एनकोड करता है कि यह बाईं ओर कितनी दूर तक फैल सकता है।

तीसरा संकेत डुप्लिकेट और सीमाओं के तहत शुद्धता है। समान ऊँचाइयों को अलग-अलग शुरुआत के साथ प्रतिस्पर्धी प्रविष्टियाँ नहीं बनानी चाहिए। अंत में स्टैक पर बचे बार्स को अभी भी एक दाहिनी सीमा की आवश्यकता होती है। एक मजबूत कार्यान्वयन याद किए गए चौड़ाई सूत्र पर निर्भर रहने के बजाय दोनों नियमों को स्पष्ट बनाता है।

अंत में, नेस्टेड while लूप को एमॉर्टाइज्ड विश्लेषण की आवश्यकता होती है। एक पुनरावृत्ति (iteration) कई प्रविष्टियों को पॉप कर सकती है, लेकिन प्रत्येक प्रविष्टि को एक बार पुश किया जाता है और एक बार पॉप किया जाता है। स्टैक संचालन की कुल संख्या रैखिक (linear) है।

उत्तर देने से पहले स्पष्ट करने वाले प्रश्न

• क्या प्रत्येक बार की चौड़ाई 1 है? हाँ। परिवर्तनीय चौड़ाई संग्रहीत बाईं सीमा और क्षेत्रफल सूत्र दोनों को बदल देती है।
• क्या आयत को लगातार बार्स का उपयोग करना चाहिए? हाँ। एक आयत बीच में किसी छोटे बार को छोड़ नहीं सकता है।
• क्या ऊँचाइयाँ शून्य या दोहराई जा सकती हैं? हाँ। शून्य सकारात्मक आयतों को अलग करता है; समान ऊँचाइयों के लिए एक सुसंगत स्टैक नियम की आवश्यकता होती है।
• क्या इनपुट खाली हो सकता है? मानक समस्या इसे बाहर रखती है, जबकि यह कार्यान्वयन एक प्रलेखित विस्तार के रूप में 0 लौटाता है।
• क्या हम केवल क्षेत्रफल लौटाते हैं? हाँ। निर्देशांक लौटाने के लिए विजेता शुरुआत, अंत और ऊँचाई के साथ-साथ एक टाई नियम को बनाए रखने की आवश्यकता होती है।
• क्या फ़ंक्शन इनपुट को म्यूटेट (परिवर्तित) कर सकता है? किसी म्यूटेशन की आवश्यकता नहीं है; सेंटिनल को अपेंड करने के बजाय वर्चुअल रखा गया है।
• क्या क्षेत्रफल ओवरफ्लो हो सकता है? बताए गए प्रतिबंधों के तहत नहीं। एक बड़े प्रोडक्शन अनुबंध को अपनी सीमा की गणना करनी चाहिए और जहाँ आवश्यक हो bigint या एक व्यापक पूर्णांक का उपयोग करना चाहिए।
• क्या लीनियर समय आवश्यक है? हाँ। एक O(n^2) आधार रेखा व्युत्पत्ति और परीक्षण के लिए उपयोगी है, लेकिन लक्ष्य प्रतिबंधों के लिए पर्याप्त नहीं है।

30-सेकंड उत्तर ढांचा

"ऊँचाई h के एक बार के लिए, इसका सबसे चौड़ा मान्य आयत प्रत्येक तरफ पहले छोटे बार से ठीक पहले समाप्त होता है। मैं कड़ाई से बढ़ती ऊँचाई के क्रम में जोड़े (start, height) के एक स्टैक के साथ बाएं से दाएं स्कैन करता हूँ। जब वर्तमान ऊँचाई स्टैक के शीर्ष से कम होती है, तो वर्तमान इंडेक्स उस शीर्ष बार की दाईं ओर पहली छोटी सीमा होती है, इसलिए मैं इसे पॉप करता हूँ और height * (right - start) की गणना करता हूँ। मैं पॉप किए गए start को बाईं ओर ले जाता हूँ क्योंकि वर्तमान छोटा बार अभी हटाए गए प्रत्येक लंबे बार में फैल सकता है। ऊँचाइयाँ समान होने पर मैं पहले वाली प्रविष्टि को बनाए रखता हूँ। अंत में एक वर्चुअल शून्य सभी शेष आयतों को बंद कर देता है। प्रत्येक प्रविष्टि को अधिक से अधिक एक बार पुश और पॉप किया जाता है, इसलिए समय और सहायक स्थान O(n) और O(n) हैं।"

स्टेप-बाय-स्टेप डीप डाइव

स्टेप 1: एक सही आधार रेखा (baseline) स्थापित करें।

प्रत्येक अंतराल [left, right] के लिए, उसकी न्यूनतम ऊँचाई को ट्रैक करें। इसके सबसे बड़े पूर्ण-चौड़ाई वाले आयत का क्षेत्रफल है:

min(heights[left..right]) * (right - left + 1)

रनिंग न्यूनतम को बनाए रखते हुए right का विस्तार करने से एक O(n^2)-समय, O(1)-स्थान ओरेकल बनता है। यह n = 100000 के लिए बहुत धीमा है, लेकिन छोटे यादृच्छिक इनपुट पर एक अनुकूलित समाधान की जाँच के लिए उत्कृष्ट है।

स्टेप 2: गणना (enumeration) को उलट दें।

प्रत्येक अंतराल के न्यूनतम के लिए पूछने के बजाय, आयत की सीमित ऊँचाई के रूप में एक बार चुनें। यदि निकटतम कड़ाई से छोटी स्थितियाँ leftShorter और rightShorter हैं, तो बार कवर कर सकता है:

(leftShorter + 1) .. (rightShorter - 1)
width = rightShorter - leftShorter - 1

यह उस सीमित ऊँचाई के लिए सबसे चौड़ा आयत है। वैश्विक उत्तर ऐसे सभी उम्मीदवारों में से अधिकतम है।

स्टेप 3: अनसुलझे बार्स को बढ़ते क्रम में रखें।

स्टैक { start, height } को स्टोर करता है। ऊँचाइयाँ कड़ाई से बढ़ रही हैं। start वह सबसे पहला इंडेक्स है जिससे पहले से बंद सभी लंबे बार्स को हटा दिए जाने के बाद वह ऊँचाई मान्य बनी रही है। एक नया लंबा बार अपने स्वयं के इंडेक्स से शुरू होता है। एक नया छोटा बार लंबी प्रविष्टियों को बंद करता है और सबसे पहले पॉप किए गए स्टार्ट को इनहेरिट करता है।

[2, 1, 5, 6, 2, 3] के लिए, इंडेक्स 4 पर ऊँचाई 2 पहले 6 को पॉप करती है, जिससे 6 * 1 बनता है, फिर 5 को पॉप करती है, जिससे 5 * 2 = 10 बनता है। यह स्टार्ट 2 को इनहेरिट करता है, क्योंकि ऊँचाई 2 दो लंबे बार्स को कवर कर सकती है। मौजूदा ऊँचाई 1 इसके नीचे रहती है और आगे के विस्तार को रोकती है।

स्टेप 4: समानता और पूर्णता को परिभाषित करें।

यदि वर्तमान ऊँचाई शीर्ष ऊँचाई के बराबर है, तो पुरानी प्रविष्टि रखें। दोनों बार समान ऊँचाई प्रदान करते हैं, लेकिन पुराने वाले की शुरुआत पहले होती है और इसलिए यह कभी भी संकरा सबसे अच्छा आयत नहीं देता है। इंडेक्स n पर एक वर्चुअल ऊँचाई 0 इनपुट को म्यूटेट किए बिना या क्लीनअप लॉजिक की नकल किए बिना सभी सकारात्मक प्रविष्टियों को बंद कर देती है।

स्टेप 5: इनवेरिएंट को लागू करें और पॉप गणना को सिद्ध करें।

interface StackBar {
  start: number
  height: number
}

export function largestRectangleArea(heights: number[]): number {
  const stack: StackBar[] = []
  let maxArea = 0

  for (let right = 0; right <= heights.length; right += 1) {
    const height = right === heights.length ? 0 : heights[right]
    let start = right

    while (stack.length > 0 && stack[stack.length - 1].height > height) {
      const bar = stack.pop()!
      maxArea = Math.max(maxArea, bar.height * (right - bar.start))
      start = bar.start
    }

    const top = stack[stack.length - 1]
    if (height > 0 && (!top || top.height < height)) {
      stack.push({ start, height })
    }
  }

  return maxArea
}

प्रमाण प्रत्येक स्कैन चरण से पहले तीन इनवेरिएंट का अनुसरण करता है:

1. स्टैक की ऊँचाइयाँ कड़ाई से बढ़ रही हैं।
2. प्रत्येक प्रविष्टि के लिए, start से right - 1 तक प्रत्येक संसाधित बार कम से कम उसकी ऊँचाई का है।
3. उस अंतराल के अंदर कोई भी कड़ाई से छोटा संसाधित बार नहीं है; अन्यथा प्रविष्टि पहले ही पॉप हो चुकी होती।

जब एक छोटी ऊँचाई आती है, तो इनवेरिएंट 2 और 3 दिखाते हैं कि पॉप की गई प्रविष्टि right - 1 तक फैल सकती है, जबकि वर्तमान बार साबित करता है कि यह right तक नहीं फैल सकती है। इसलिए इसकी अधिकतम चौड़ाई सटीक रूप से right - start है, इसलिए परिकलित क्षेत्रफल पूर्ण है। पॉप किए गए स्टार्ट को वर्तमान ऊँचाई पर पास करना सुरक्षित है क्योंकि वर्तमान ऊँचाई प्रत्येक हटाई गई ऊँचाई से छोटी है। समान ऊँचाई को छोड़ना सुरक्षित है क्योंकि बनाए रखी गई समान प्रविष्टि बाद में शुरू नहीं होती है। सेंटिनल प्रत्येक प्रविष्टि को बंद कर देता है जिसके दाईं ओर कोई छोटा वास्तविक बार नहीं है। इस प्रकार प्रत्येक संभावित सीमित ऊँचाई के अधिकतम आयत पर विचार किया जाता है, और maxArea इष्टतम (optimum) है।

स्टेप 6: एज केस और कॉम्प्लेक्सिटी सत्यापित करें।

निश्चित मामलों का उपयोग करें जो विभिन्न इनवेरिएंट पर परीक्षण करते हैं:

मजबूत साक्ष्य के लिए, कई छोटे यादृच्छिक ऐरे पर द्विघात ओरेकल के साथ स्टैक परिणाम की तुलना करें। ऊपर दिए गए कार्यान्वयन की सात निश्चित मामलों और लंबाई 0..8 और ऊँचाइयों 0..7 वाले 20,000 यादृच्छिक ऐरे के खिलाफ जाँच की गई थी। यह निष्पादन योग्य साक्ष्य है, प्रमाण का प्रतिस्थापन नहीं; इनवेरिएंट सभी संभावित इनपुट की व्याख्या करते हैं।

प्रत्येक सकारात्मक ऊँचाई को अधिक से अधिक एक बार पुश किया जाता है और अधिक से अधिक एक बार पॉप किया जाता है, इसलिए कुल समय O(n) है। एक कड़ाई से बढ़ता इनपुट सेंटिनल तक सभी n प्रविष्टियों को बनाए रखता है, जिससे O(n) सबसे खराब स्थिति में सहायक स्थान मिलता है।

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

"मैं पहले एक द्विघात ओरेकल स्थापित करूँगा: प्रत्येक बाईं सीमा के लिए, दाईं सीमा का विस्तार करें और न्यूनतम ऊँचाई बनाए रखें। यह प्रत्येक संभावित अंतराल की जाँच करता है, लेकिन यह 100,000 बार्स के लिए बहुत धीमा है। बार-बार पूछा जाने वाला प्रश्न यह है कि एक चुनी गई ऊँचाई एक छोटे बार द्वारा अवरुद्ध होने से पहले कितनी दूर तक फैल सकती है, जो निकटतम-छोटे सीमाओं और एक मोनोटोनिक स्टैक की ओर संकेत करता है।

मेरा स्टैक प्रत्येक अनसुलझी ऊँचाई के साथ सबसे प्रारंभिक मान्य शुरुआत को संग्रहीत करता है, और इसकी ऊँचाइयाँ कड़ाई से बढ़ रही हैं। इंडेक्स right पर, मैं तब तक पॉप करता हूँ जब तक कि शीर्ष वर्तमान बार से लंबा हो। वर्तमान इंडेक्स पॉप किए गए बार की पहली अमान्य स्थिति है, इसलिए इसका अधिकतम क्षेत्रफल bar.height * (right - bar.start) है। मैं इसकी शुरुआत को वर्तमान ऊँचाई पर पास करता हूँ क्योंकि वह छोटा बार अभी हटाए गए सभी लंबे बार्स को कवर कर सकता है। यदि ऊँचाई स्टैक के शीर्ष के बराबर है, तो मैं डुप्लिकेट पुश करने के बजाय पहले वाली प्रविष्टि रखता हूँ। अंत में एक वर्चुअल शून्य शेष प्रत्यय (suffix) को बंद कर देता है।

स्टैक इनवेरिएंट गारंटी देता है कि प्रविष्टि की शुरुआत और वर्तमान स्थिति के बीच का प्रत्येक बार पर्याप्त रूप से लंबा है। छोटा वर्तमान बार परिकलित दाईं सीमा को अंतिम बनाता है। प्रत्येक प्रविष्टि को अधिक से अधिक एक बार पुश और पॉप किया जाता है, जिससे O(n) समय और O(n) सबसे खराब स्थिति में स्थान मिलता है। मैं समान ऊँचाइयों, बढ़ते और घटते ऐरे, शून्य, इस विस्तारित अनुबंध के तहत एक खाली इनपुट का परीक्षण करूँगा, और द्विघात ओरेकल के साथ यादृच्छिक छोटे मामलों की तुलना करूँगा।"

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

प्रत्येक विफलता का एक विशिष्ट कारण और सुधार होता है:

• पॉप के बाद right - start + 1 का उपयोग करना → right पहले से ही पहली अमान्य स्थिति है → right - start का उपयोग करें।
• अंतिम फ्लश को भूल जाना → बढ़ते प्रत्ययों का कभी मूल्यांकन नहीं किया जाता है → एक वर्चुअल शून्य को स्कैन करें।
• प्रत्येक समान ऊँचाई को पुश करना → शुद्धता अधिक नाजुक पॉप नियम से जुड़ जाती है → सबसे प्रारंभिक समान प्रविष्टि रखें।
• यह दावा करना कि आंतरिक लूप समय को द्विघात बनाता है → प्रत्येक प्रविष्टि को केवल एक बार पॉप किया जा सकता है → एमॉर्टाइज्ड गणना दें।
• heights में एक सेंटिनल जोड़ना (append) → कॉलर म्यूटेशन देखते हैं → सेंटिनल की गणना वर्चुअली करें।

फॉलो-अप डीप डाइव

फॉलो-अप 1: आप आयत की सीमाओं को कैसे लौटाते हैं?

जब भी किसी क्षेत्रफल में सुधार होता है, तो { start: bar.start, end: right - 1, height: bar.height } को सहेजें। कोडिंग से पहले टाई को परिभाषित करें: सबसे बाएं आयत, सबसे चौड़े आयत, या सबसे लंबे आयत को प्राथमिकता दें। अकेले क्षेत्रफल एक अद्वितीय उत्तर निर्धारित नहीं करता है।

फॉलो-अप 2: क्या होगा यदि बार्स की चौड़ाई परिवर्तनीय हो?

इंडेक्स चौड़ाई को भौतिक चौड़ाई के प्रीफिक्स योग से बदलें। स्टैक प्रविष्टियों को सबसे प्रारंभिक क्षैतिज निर्देशांक बनाए रखना चाहिए, और एक पॉप किया गया क्षेत्रफल height * (currentX - startX) बन जाता है। शून्य-चौड़ाई वाले बार्स और अमान्य नकारात्मक चौड़ाई के लिए एक स्पष्ट अनुबंध की आवश्यकता होती है।

फॉलो-अप 3: यह बाइनरी मैट्रिक्स तक कैसे फैलता है?

प्रत्येक पंक्ति को हिस्टोग्राम के आधार के रूप में मानें। प्रत्येक कॉलम के लिए, जब वर्तमान सेल 1 हो तो उसकी ऊँचाई बढ़ाएँ, अन्यथा इसे 0 पर रीसेट करें; प्रत्येक पंक्ति के बाद हिस्टोग्राम एल्गोरिदम चलाएँ। एक m × n मैट्रिक्स के लिए, समय O(mn) है और सहायक स्थान O(n) है।

फॉलो-अप 4: क्या किसी स्ट्रीम के लिए सटीक उत्तर बनाए रखा जा सकता है?

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

फॉलो-अप 5: क्या होगा यदि इनपुट एक मशीन की मेमोरी के लिए बहुत बड़ा है?

स्वतंत्र चंक मैक्सिमा अपर्याप्त हैं क्योंकि जीतने वाला आयत चंक सीमाओं को पार कर सकता है। एक वितरित सारांश को आसन्न चंक्स को मर्ज करने के लिए पर्याप्त सीमा ऊँचाई संरचना को संरक्षित करना चाहिए, जो एक मोनोटोन चंक में स्वयं लीनियर हो सकता है। स्थिर-आकार के मर्ज सारांश का वादा करने से पहले उस निचली-सीमा के जोखिम का उल्लेख करें।

फॉलो-अप 6: एक अलग दृष्टिकोण कब बेहतर होता है?

द्विघात ओरेकल छोटे-इनपुट सत्यापन के लिए सबसे अच्छा है। न्यूनतम के आसपास डिवाइड एंड कॉन्कर पुनरावृत्ति (recurrence) प्राप्त करने के लिए उपयोगी है, लेकिन प्रत्येक न्यूनतम के लिए एक लीनियर स्कैन सॉर्ट किए गए इनपुट पर O(n^2) बन जाता है। एक रेंज-मिनिमम डेटा संरचना अन्य बार-बार होने वाले प्रश्नों का समर्थन कर सकती है, फिर भी इस एक स्थिर अधिकतम के लिए, मोनोटोनिक स्टैक सरल और स्पर्शोन्मुख रूप से इष्टतम (asymptotically optimal) है।