कोडिंग इंटरव्यू: Two Pointers की मदद से Trapping Rain Water को कैसे हल करें?

समस्या और प्रयोज्य परिदृश्य

लंबाई n का एक गैर-ऋणात्मक पूर्णांक ऐरे height दिया गया है, जिसमें height[i] इंडेक्स i पर स्थित बार की ऊँचाई है, और प्रत्येक बार की चौड़ाई 1 है। इन बारों द्वारा रोके गए (trapped) कुल वर्षा जल की गणना करें। उदाहरण के लिए:

height = [4, 2, 0, 3, 2, 5]
result = 9

लक्ष्य O(n) टाइम और O(1) ऑक्जिलरी स्पेस है। मानक प्रतिबंध 1 <= n <= 20000 और 0 <= height[i] <= 100000 हैं। ऊँचाइयाँ कभी ऋणात्मक नहीं होती हैं, और मुख्य समस्या प्रत्येक व्यक्तिगत बार के ऊपर संग्रहीत पानी के बारे में नहीं पूछती है।

इस प्रश्न के प्रत्यक्ष सार्वजनिक इंटरव्यू साक्ष्य मौजूद हैं। Baidu Go बैकएंड इंटर्नशिप इंटरव्यू की जून 2025 की एक रिपोर्ट में Trapping Rain Water को तीन लाइव कोडिंग कार्यों में से एक के रूप में सूचीबद्ध किया गया है। एक अलग सार्वजनिक फोन-स्क्रीन रिपोर्ट एक ऐसा प्रकार जोड़ती है जिसमें एक निश्चित स्थिति पर सीमित मात्रा में पानी डाला जाता है। अंग्रेजी और चीनी LeetCode समस्या पृष्ठ इसे कठिन (hard) के रूप में वर्गीकृत करते हैं और इसे ऐरे, दो पॉइंटर्स, डायनेमिक प्रोग्रामिंग, स्टैक और मोनोटोनिक स्टैक के साथ टैग करते हैं। मुख्य कौशल एक स्थानीय सूत्र से एक रैखिक एल्गोरिदम प्राप्त करना और उसे सिद्ध करना है, इसलिए कार्यान्वयन भाषा या जॉब फैमिली की परवाह किए बिना श्रेणी coding है।

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

पहला, क्या आप एक बार के ऊपर पानी की सही मात्रा बता सकते हैं? इंडेक्स i पर जल स्तर इसके बाईं ओर के सबसे ऊँचे बार और दाईं ओर के सबसे ऊँचे बार में से जो छोटा है, उससे सीमित होता है, न कि केवल दो निकटवर्ती बारों से। यदि leftMax[i] और rightMax[i] दोनों में इंडेक्स i शामिल है, तो मात्रा min(leftMax[i], rightMax[i]) - height[i] होती है।

दूसरा, क्या आप प्रीफिक्स और सफिक्स ऐरे को कॉन्स्टेंट स्पेस में कंप्रेस कर सकते हैं? प्रत्येक बाएँ और दाएँ अधिकतम को संग्रहीत करने से एक आसान O(n)-टाइम समाधान मिलता है। दो पॉइंटर्स इस मजबूत अवलोकन का उपयोग करते हैं कि छोटी ज्ञात सीमा एक समय में एक कॉलम को अंतिम रूप (finalize) देने के लिए पहले से ही पर्याप्त है।

तीसरा, क्या आप वास्तव में मूवमेंट नियम को समझते हैं? केवल "छोटे पॉइंटर को आगे बढ़ाएं" दोहराना कोई प्रमाण नहीं है। एक मजबूत उत्तर लूप इनवेरिएंट्स बताता है और दोनों मामलों को संभालता है: वर्तमान बार या तो अपने पक्ष की सीमा को बढ़ाता है या उसके नीचे रहता है। इस तर्क को यह दिखाना होगा कि बिना स्कैन किया गया क्षेत्र अभी-अभी अंतिम रूप दी गई मात्रा को क्यों नहीं बदल सकता।

अंत में, क्या आप विकल्पों की सटीक तुलना कर सकते हैं? प्रीफिक्स और सफिक्स ऐरे को समझाना सबसे आसान है। एक मोनोटोनिक स्टैक क्षैतिज घाटियों (basins) को हल करता है और संबंधित स्टैक समस्याओं में स्वाभाविक रूप से स्थानांतरित होता है। दो पॉइंटर्स सबसे कम स्थान का उपयोग करते हैं। तीनों सही हो सकते हैं, लेकिन उनके अलग-अलग स्पेस बाउंड, प्रूफ स्टाइल और एक्सटेंशन होते हैं।

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

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

30-सेकंड का उत्तर ढांचा (Answer Framework)

"एक बार के ऊपर का पानी उसके दोनों किनारों के सबसे ऊँचे बारों में से छोटे वाले में से बार की ऊँचाई घटाने पर मिलता है। प्रीफिक्स और सफिक्स ऐरे उन सभी अधिकतमों की गणना रैखिक समय में करते हैं लेकिन O(n) स्पेस का उपयोग करते हैं। मैं उस स्थिति को बाएँ और दाएँ पॉइंटर्स तथा leftMax और rightMax में कंप्रेस कर सकता हूँ, जो प्रत्येक पक्ष से पहले से स्कैन किए गए सबसे ऊँचे बार हैं। जब leftMax <= rightMax होता है, तो ज्ञात दाएँ सीमा पहले से ही कम से कम leftMax जितनी ऊँची होती है। यदि वर्तमान बायाँ बार leftMax को नहीं बढ़ाता है, तो इसकी मात्रा leftMax - height[left] पर तय होती है; यदि यह सीमा बढ़ाता है, तो इसकी मात्रा शून्य होती है। फिर मैं बाएँ पॉइंटर को आगे बढ़ाता हूँ। दूसरा पक्ष सममित (symmetric) है। प्रत्येक इंडेक्स को एक बार अंतिम रूप दिया जाता है, इसलिए समय O(n) है और ऑक्जिलरी स्पेस O(1) है।"

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

चरण 1: एक कॉलम के लिए उत्तर परिभाषित करें।

मान लें:

L[i] = max(height[0..i])
R[i] = max(height[i..n-1])
water[i] = min(L[i], R[i]) - height[i]

L[i] और R[i] दोनों में height[i] शामिल है, इसलिए कोई भी वर्तमान बार से कम नहीं हो सकता है और सूत्र को शून्य पर अतिरिक्त क्लैंप की आवश्यकता नहीं है। कुल सभी water[i] का योग है। यह सूत्र यह भी दिखाता है कि आसन्न बारों की जाँच करना क्यों विफल रहता है: एक दूर की ऊँची सीमा पूरे बेसिन के लिए सतह निर्धारित कर सकती है।

चरण 2: एक सही बेसलाइन स्थापित करें।

प्रीफिक्स समाधान बाएँ से दाएँ L और दाएँ से बाएँ R बनाता है, फिर सूत्र लागू करता है। दो पॉइंटर्स पानी की मात्रा को फिर से परिभाषित नहीं करते हैं। वे L और R के प्रत्येक मान को संग्रहीत करने से पहले एक कॉलम को अंतिम रूप देने के लिए पर्याप्त ज्ञात सीमाओं का उपयोग करते हैं।

चरण 3: लूप इनवेरिएंट्स बताएं।

प्रत्येक पुनरावृत्ति (iteration) की शुरुआत में:

1. left के ठीक बाईं ओर के प्रत्येक इंडेक्स को प्रति-कॉलम सूत्र के अनुसार अंतिम रूप दिया जा चुका है।
2. right के ठीक दाईं ओर के प्रत्येक इंडेक्स को सही ढंग से अंतिम रूप दिया जा चुका है।
3. leftMax स्कैन की गई श्रेणी height[0..left-1] का अधिकतम है, जिसमें खाली अधिकतम 0 है।
4. rightMax, height[right+1..n-1] का अधिकतम है, जो खाली सीमा के लिए फिर से 0 का उपयोग करता है।
5. water सभी अंतिम रूप दिए गए इंडेक्सों का योग है।

असंसाधित अंतराल हमेशा [left, right] होता है। प्रत्येक पुनरावृत्ति को यह साबित करना होगा कि इस अंतराल को छोटा करने से पहले कम से कम एक छोर को स्थायी रूप से अंतिम रूप दिया जा सकता है।

चरण 4: सिद्ध करें कि छोटी ज्ञात सीमा वाला पक्ष क्यों आगे बढ़ सकता है।

मान लें कि leftMax <= rightMax है और height[left] पर विचार करें:

• यदि वर्तमान बार leftMax से ऊँचा है, तो यह नई उच्चतम बायीं सीमा बन जाता है। बार

अपनी स्वयं की बायीं सीमा है, इसलिए इसकी ट्रैप की गई मात्रा 0 है।

• यदि वर्तमान बार leftMax से अधिक ऊँचा नहीं है, तो इसके दाईं ओर का वास्तविक अधिकतम कम से कम

पहले से देखा गया rightMax है, और rightMax >= leftMax है। इसलिए छोटी सीमा leftMax पर तय हो जाती है, जिससे मात्रा बिल्कुल leftMax - height[left] हो जाती है।

किसी भी मामले में बिना स्कैन किए गए मध्य भाग के सटीक आकार की आवश्यकता नहीं होती है, इसलिए बाएँ कॉलम को अंतिम रूप दिया जा सकता है। यदि leftMax > rightMax है, तो प्रमाण दाएँ कॉलम के लिए सममित है। यह ज्ञात अधिकतम सीमाओं की तुलना है, न कि पड़ोसी बारों पर आधारित कोई अनुमान।

चरण 5: दो-पॉइंटर एल्गोरिदम लागू करें।

def trap(height: list[int]) -> int:
    left = 0
    right = len(height) - 1
    left_max = 0
    right_max = 0
    water = 0

    while left <= right:
        if left_max <= right_max:
            left_max = max(left_max, height[left])
            water += left_max - height[left]
            left += 1
        else:
            right_max = max(right_max, height[right])
            water += right_max - height[right]
            right -= 1

    return water

शर्त left <= right है, इसलिए पॉइंटर्स के मिलने पर अंतिम कॉलम को अंतिम रूप दिया जाता है। अंतर जोड़ने से पहले सीमा को अपडेट करने से एक नया अधिकतम शून्य का योगदान देता है और प्रत्येक वृद्धि को गैर-ऋणात्मक रखता है। एक खाली ऐरे के लिए, right, -1 पर शुरू होता है, लूप नहीं चलता है, और फ़ंक्शन 0 लौटाता है।

चरण 6: [4, 2, 0, 3, 2, 5] को ट्रेस करें।

index  height  side   boundary after update  added water  total
0      4       left   leftMax=4              0            0
5      5       right  rightMax=5             0            0
1      2       left   leftMax=4              2            2
2      0       left   leftMax=4              4            6
3      3       left   leftMax=4              1            7
4      2       left   leftMax=4              2            9

ऊँचाई 5 का बार प्रत्येक शेष बाएँ कॉलम के लिए पर्याप्त रूप से ऊँची एक ज्ञात दाएँ सीमा की आपूर्ति करता है, इसलिए एल्गोरिदम बाएँ पक्ष को अंतिम रूप देना जारी रखता है। प्रत्येक कॉलम बिल्कुल एक बार दिखाई देता है, जिसमें किसी भी बेसिन को दो बार नहीं गिना जाता है।

चरण 7: समाप्ति, शुद्धता और जटिलता सिद्ध करें।

प्रारंभ में, दोनों संसाधित श्रेणियां खाली हैं, इसलिए इनवेरिएंट्स बने रहते हैं। चरण 4 साबित करता है कि प्रत्येक पुनरावृत्ति में जोड़े गए कॉलम को बिल्कुल उसकी प्रति-कॉलम मात्रा प्राप्त होती है। leftMax या rightMax को अपडेट करना अगली पुनरावृत्ति के लिए इसकी परिभाषा को बनाए रखता है। प्रत्येक पुनरावृत्ति या तो left को बढ़ाती है या right को घटाती है; सीमित चरणों के बाद, left > right। उस बिंदु पर प्रत्येक इंडेक्स को सही ढंग से अंतिम रूप दिया जा चुका होता है, इसलिए योग सही होता है।

प्रत्येक इंडेक्स पर एक बार जाया जाता है, जिससे O(n) टाइम मिलता है। एल्गोरिदम आउटपुट-मुक्त स्केलर परिणाम से परे इनपुट-आकार का कोई स्टोरेज आवंटित नहीं करता है; दो पॉइंटर्स, दो सीमाएं और एक एक्यूमुलेटर O(1) ऑक्जिलरी स्पेस का उपयोग करते हैं।

चरण 8: एक फॉर्मूला ऑरेकल और प्रतिकूल मामलों (adversarial cases) के विरुद्ध सत्यापित करें।

निश्चित परीक्षणों में एक बार, दो बार, सभी शून्य, कड़ाई से बढ़ते और घटते इनपुट, सभी समान ऊँचाइयाँ, कई अलग-अलग बेसिन, एक सपाट तल वाला बेसिन, मानक उदाहरण और [3, 0, 3] शामिल होने चाहिए। अंतिम मामला एक ऐसे कार्यान्वयन को उजागर करता है जो गलत तरीके से left < right का उपयोग करता है और मिलने वाले इंडेक्स को छोड़ देता है।

लघु यादृच्छिक गैर-ऋणात्मक ऐरे के लिए, L और R बनाएं, प्रति-कॉलम सूत्र को ऑरेकल के रूप में उपयोग करें, और इसकी तुलना दो-पॉइंटर परिणाम से करें। यह भी जांचें कि परिणाम गैर-ऋणात्मक है, ऐरे को उलटने पर कुल योग वही रहता है, और किसी भी बाहरी छोर पर शून्य-ऊँचाई वाला बार जोड़ने से मूल कुल योग नहीं बदलता है। डिफरेंशियल परीक्षण कार्यान्वयन त्रुटियों को खोजते हैं; इनवेरिएंट प्रमाण ही शुद्धता का मुख्य तर्क बना रहता है।

मजबूत नमूना उत्तर

"मैं पहले समस्या को प्रति-इंडेक्स सूत्र में बदलता हूँ। i पर गहराई min(max(height[0..i]), max(height[i..n-1])) - height[i] है। दो प्रीफिक्स ऐरे उस सूत्र को O(n) टाइम और O(n) स्पेस में लागू करते हैं। कॉन्स्टेंट ऑक्जिलरी स्पेस प्राप्त करने के लिए, मैं दो पॉइंटर्स का उपयोग करता हूँ।

लूप के अंदर, leftMax और rightMax दोनों पॉइंटर्स के बाहर पहले से स्कैन किए गए सबसे ऊँचे बार हैं। यदि leftMax <= rightMax है, तो मैं बाएँ पॉइंटर को अंतिम रूप देता हूँ। यदि इसका वर्तमान बार leftMax को बढ़ाता है, तो इसकी मात्रा शून्य होती है। अन्यथा, ज्ञात rightMax पहले से ही कम से कम बायीं सीमा जितना ऊँचा है, इसलिए अज्ञात मध्य भाग छोटी सीमा को leftMax से कम नहीं कर सकता है; मात्रा leftMax - height[left] पर तय होती है। फिर मैं बाएँ को अंदर की ओर ले जाता हूँ। दायाँ पक्ष सममित है।

प्रत्येक पुनरावृत्ति स्थायी रूप से एक कॉलम को संभालती है, इसलिए समाप्ति पर सभी कॉलम पूरे हो जाते हैं। समय O(n) है, और पॉइंटर्स, सीमाएं और एक्यूमुलेटर O(1) ऑक्जिलरी स्पेस का उपयोग करते हैं। मैं छोटे इनपुट, मोनोटोन और समान ऐरे, एकाधिक बेसिन और [3, 0, 3] का परीक्षण करूँगा, फिर प्रीफिक्स-ऐरे फॉर्मूला के साथ छोटे यादृच्छिक मामलों की विभेदक (differentially) तुलना करूँगा।"

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

• दो अधिकतमों में से बड़े वाले से घटाना → पानी छोटी सीमा से बाहर निकल जाता है → हमेशा छोटे अधिकतम का उपयोग करें।
• केवल आसन्न बारों की जाँच करना → एक दूर की सीमा की अनदेखी हो जाती है → पूर्ण बाएँ/दाएँ प्रति-कॉलम सूत्र से शुरुआत करें।
• वर्तमान सीमा को अपडेट करने से पहले जोड़ना → एक नया अधिकतम ऋणात्मक मात्रा उत्पन्न कर सकता है → पहले अपडेट करें, फिर एक गैर-ऋणात्मक अंतर जोड़ें।
• left < right का उपयोग करना → [3, 0, 3] का मध्य भाग असंसाधित रह सकता है → लूप में मिलने की स्थिति को शामिल करें।
• बिना किसी प्रमाण के बड़ी सीमा वाले पक्ष को आगे बढ़ाना → अज्ञात विपरीत पक्ष अभी भी निचली सतह निर्धारित कर सकता है → केवल उस पक्ष को अंतिम रूप दें जिसे एक ज्ञात विपरीत सीमा का समर्थन प्राप्त हो।
• Container With Most Water सूत्र लागू करना → width × boundary height बार और कॉलम की दोहरी गणना करता है → प्रत्येक बार के ऊपर पानी की गहराई का योग करें।
• प्रति पुनरावृत्ति स्थिर कार्य पर ही विश्लेषण रोक देना → यह नहीं समझाता कि भविष्य के बार उत्तर को क्यों नहीं बदल सकते → सीमा इनवेरिएंट्स और दो-केस प्रमाण बताएं।
• यह दावा करना कि मोनोटोनिक स्टैक भी O(1) स्पेस का उपयोग करता है → एक मोनोटोन इनपुट n इंडेक्स बनाए रख सकता है → O(n) सबसे खराब स्थिति स्पेस की रिपोर्ट करें।
• केवल सचित्र उदाहरण का परीक्षण करना → मीटिंग, मोनोटोन और समान-ऊँचाई वाली सीमाएं अनियंत्रित रह जाती हैं → निश्चित मामले और एक प्रीफिक्स-ऐरे ऑरेकल जोड़ें।

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

फॉलो-अप 1: height[left] और height[right] की सीधे तुलना क्यों नहीं करते?

एक अन्य सही सूत्रीकरण वर्तमान समापन बिंदु ऊँचाइयों की तुलना करता है, लेकिन इसे एक मिलान इनवेरिएंट और अपडेट क्रम की आवश्यकता होती है। यह कार्यान्वयन leftMax और rightMax की तुलना करता है क्योंकि वे मान सीधे प्रति-कॉलम सीमा सूत्र से मैप होते हैं। एक सूत्रीकरण की स्थिति को दूसरे सूत्रीकरण के प्रमाण के साथ न मिलाएं; एक चुनें और कोड, स्पष्टीकरण और प्रमाण को सुसंगत रखें।

फॉलो-अप 2: क्या होगा यदि फ़ंक्शन को प्रत्येक बार के ऊपर पानी लौटाना पड़े?

प्रत्येक अंतिम वृद्धि को लंबाई n के एक ऐरे में लिखें, फिर उसका योग करें या उसी समय कुल जमा करें। रनटाइम O(n) बना रहता है, जबकि आउटपुट को स्वयं O(n) स्पेस की आवश्यकता होती है। यदि कोई कॉलर परिणामों को एक स्ट्रीम के रूप में उपभोग करता है, तो ध्यान दें कि दो पॉइंटर्स बाएँ से दाएँ क्रम में इंडेक्स को अंतिम रूप नहीं देते हैं; इंडेक्स शामिल करें या पूर्ण आउटपुट को पुन: व्यवस्थित करें।

फॉलो-अप 3: क्या होगा यदि ऊँचाइयाँ केवल बाएँ से दाएँ स्ट्रीम के रूप में आती हैं?

एक सटीक उत्तर भविष्य की दाएँ सीमा पर निर्भर करता है, इसलिए निश्चित मेमोरी के साथ प्रत्येक कॉलम को तुरंत अंतिम रूप नहीं दिया जा सकता है। एक मोनोटोनिक स्टैक खुले बेसिन को बनाए रख सकता है और पर्याप्त रूप से उच्च दाएँ सीमा आने पर उन्हें हल कर सकता है, लेकिन इसकी सबसे खराब स्थिति मेमोरी अभी भी O(n) है। एक हार्ड मेमोरी बाउंड के लिए एक सन्निकटन (approximation), बाहरी स्टोरेज या दूसरे पास की आवश्यकता होती है; यह मूल सटीक कॉन्स्टेंट-स्पेस वादे को बनाए नहीं रख सकता है।

फॉलो-अप 4: क्या होगा यदि बारों की चौड़ाई अलग-अलग हो?

यदि बार i स्वतंत्र रूप से width[i] में फैला हुआ है, तो सीमा-ऊँचाई तर्क समान रहता है और इसका आयतन waterDepth[i] * width[i] होता है। यदि इनपुट इसके बजाय अनियमित निर्देशांक और अंतराल देता है, तो पहले प्रत्येक क्षैतिज अंतराल पर ऊँचाई को परिभाषित करें। पड़ोसी बार केंद्रों के बीच की दूरी स्वचालित रूप से पूरे बार की चौड़ाई नहीं होती है।

फॉलो-अप 5: आप दो-आयामी ऊँचाई मानचित्र (height map) पर पानी कैसे रोकते हैं?

एक ग्रिड सेल पूरी बाहरी सीमा से विवश होता है, इसलिए दो दिशात्मक पॉइंटर्स अपर्याप्त हैं। एक सामान्य एल्गोरिदम सभी सीमा सेल को एक न्यूनतम-हीप (min-heap) में सम्मिलित करता है और सबसे निचली वर्तमान सीमा से बार-बार अंदर की ओर फैलता है। एक निचला अनदेखा पड़ोसी ऊँचाई के अंतर में योगदान देता है, और बाद के विस्तार के लिए सीमा और पड़ोसी में से जो अधिक हो, वह प्रभावी सीमा बन जाता है। एक विजिटेड सेट के साथ, एक m × n ग्रिड O(mn log(mn)) टाइम और O(mn) स्पेस लेता है।

फॉलो-अप 6: मोनोटोनिक-स्टैक समाधान कब बेहतर होता है?

स्टैक तब स्वाभाविक होता है जब कोई फॉलो-अप बाएँ और दाएँ सीमाओं द्वारा बंद किए गए प्रत्येक बेसिन के लिए, एक क्षैतिज चौड़ाई स्पष्टीकरण के लिए, या हिस्टोग्राम-शैली की मोनोटोनिक-स्टैक समस्याओं में संक्रमण के लिए पूछता है। यह घटती-ऊँचाई के क्रम में इंडेक्स संग्रहीत करता है। एक उच्च बार बेसिन के निचले भाग को पॉप करता है; नया स्टैक टॉप और वर्तमान बार इसकी सीमाएं बनाते हैं, और एल्गोरिदम effective width × new water-layer depth जोड़ता है। कुल समय अभी भी O(n) है, जिसमें O(n) सबसे खराब स्थिति ऑक्जिलरी स्पेस है।