बक्सों का ढेर: सख्त घटता सबसे ऊँचा ढेर (जावा)

टीएल;डीआर

समस्या: डेटा संरचनाओं और एल्गोरिदम के लिए समय और स्थान जटिलता (टाइम एंड स्पेस कॉम्प्लेक्सिटी) का अनुकूलन।

दृष्टिकोण: शुरुआती लोगों के लिए सीटीसीआई शैली की समस्या ८.१३: बक्सा तभी ऊपर रखो जब चौड़ाई, गहराई और ऊँचाई तीनों सख्ती से छोटी हों। एक आयाम पर छाँटो, फिर कुल ऊँचाई अधिकतम के लिए मेमो वाला डीपी।

जटिलता: सीमांत मामलों (एज केसेस) के प्रबंधन के साथ इष्टतम समय और मेमोरी संतुलन।

फर्श पर शिपिंग बक्सों का ढेर पड़ा है। हर बक्सा ठोस आयत: चौड़ाई, गहराई, ऊँचाई। सबसे ऊँचा टावर चाहिए, पर नियम कड़ा है। एक बक्सा दूसरे पर तभी बैठे जब वह हर आयाम में सख्ती से छोटा हो: चौड़ाई, गहराई और ऊँचाई। झुकाना नहीं, बीच में घुमाना नहीं, "लगभग ठीक" नहीं। यही बक्सों का ढेर है।

यह पोस्ट जावा में शुरुआती लोगों के लिए मूल शिक्षण है। इंटरव्यू वाली रिकर्शन और डीपी समस्याओं का परिवार, किताब की नकल नहीं। सीटीसीआई जावा सीरीज़ का हिस्सा। अध्याय ८, रिकर्शन और डायनामिक प्रोग्रामिंग, समस्या ८.१३।

१. रोज़मर्रा की उपमा

मात्रयोश्का जैसी पेटियाँ सोचो, फर्क इतना कि तीनों अक्ष सिकुड़ें, सिर्फ एक नहीं।

ऊपर वाली पेटी नीचे वाली से पतली, कम गहरी और नीची हो।
हर पेटी इस्तेमाल जरूरी नहीं। जो ऊँचे टावर को रोकें, उन्हें छोड़ दो।
टावर की ऊँचाई रखी गई पेटियों की ऊँचाई का योग है, पेटियों की गिनती नहीं।

अगर बक्सा ए 4 x 5 x 6 है और बी 3 x 4 x 5, तो बी ए पर बैठ सकता है (तीनों भुजाएँ छोटी)। अगर बी 3 x 6 x 5 है, गहराई फेल, तो बी ए पर नहीं बैठेगा।

पहेली संयोजनात्मक है: हर बक्से पर फैसला, ढेर में आए या नहीं, कहाँ आए। उपसमुच्चय की ब्रूट फोर्स फूट जाती है। छाँटना और मेमो वाली रिकर्शन (या बॉटम-अप डीपी) इसे व्हाइटबोर्ड पर लिखने लायक बनाते हैं।

२. समस्या सादे शब्दों में

इनपुट: n बक्सों की सूची। हर बक्से में धनात्मक पूर्णांक width, height, depth।

आउटपुट: उस ढेर की अधिकतम कुल ऊँचाई जिसमें हर ऊपर वाला बक्सा नीचे वाले से चौड़ाई, गहराई और ऊँचाई में सख्ती से छोटा हो।

नियम:

ढेर के हर पड़ोसी जोड़े पर तीनों आयामों में सख्त असमानता।
कुछ बक्से ढेर से बाहर छोड़ सकते हो।
इनपुट सूची का क्रम ढेर का क्रम नहीं; क्रम तुम चुनते हो।
इस संस्करण में बक्से नहीं घुमाए जाते (दिए गए चौड़ाई, ऊँचाई, गहराई वैसे ही)। इंटरव्यू में बोलो अगर घुमाना माना जाए।
ढेर की ऊँचाई चुने बक्सों के height क्षेत्रों का योग है।

बक्से का आकार:

class Box {
    int width;
    int height;
    int depth;

    Box(int width, int height, int depth) {
        this.width = width;
        this.height = height;
        this.depth = depth;
    }

    /** सही अगर यह बक्सा 'below' के सख्ती से ऊपर बैठ सके। */
    boolean canBeAbove(Box below) {
        return this.width < below.width
            && this.height < below.height
            && this.depth < below.depth;
    }
}

उदाहरण:

बक्से (च, ऊ, ग)	अधिकतम ऊँचाई	क्यों
`(4,6,7), (1,2,3), (4,5,6), (10,12,32)`	`20`	तल `10x12x32` फिर `4x6x7` फिर `1x2x3` → `12+6+2`। `4x5x6` से रास्ता `12+5+2=19`
एक बक्सा `(2,3,4)`	`3`	सिर्फ वही
खाली सूची	`0`	ढेर लगाने को कुछ नहीं
सब बराबर आकार	सबसे ऊँचे अकेले की ऊँचाई	कोई किसी पर नहीं बैठता
पहले से ३ का घोंसला	तीन ऊँचाइयों का योग	एक वैध कुल क्रम

क्लासिक उदाहरण कमरे में साफ करो। सिखाने वाला आम सेट:

(4, 6, 7), (1, 2, 3), (4, 5, 6), (10, 12, 32)

एक वैध ऊँचा ढेर बड़ा बक्सा, फिर फिट मध्य, फिर छोटा इस्तेमाल करता है। कोड से पहले संख्याएँ घुमाकर जवाब पर सहमत हो जाओ।

कोड से पहले साफ करो:

घुमाना मंजूर? (आमतौर पर नहीं, जब तक न कहा जाए।)
सख्त या ढीला? (सख्त: तीनों पर <।)
डुप्लिकेट आकार? (बराबर आयाम पर ढेर नहीं; जुड़े जोड़े में ज्यादातर एक।)
सिर्फ ऊँचाई या बक्सों का क्रम भी? (यहाँ सिर्फ ऊँचाई।)
ऋणात्मक या शून्य आयाम? (अस्वीकार या धनात्मक मानो।)

३. पहले सोचो

शुद्ध उपसमुच्चय खोज क्यों फेल

हर बक्सा छोड़ो या कहीं रखो। सारे उपसमुच्चय और क्रम घातीय हैं। संरचना चाहिए।

अवलोकन: एक आयाम पर छाँटो

बक्सों को ऊँचाई घटते क्रम में छाँटो (सबसे बड़ी ऊँचाई पहले)। फिर वैध ढेर सूची में बड़े से छोटे की ओर चलता दिखता है। अकेला छाँटना वैधता नहीं गारंटी करता: चौड़ाई और गहराई अभी फेल हो सकती हैं। पर स्कैन स्वाभाविक बनता है: तल चुनने के बाद ऊपर के उम्मीदवार अक्सर बाद में आते हैं, या बाकी सब पर canBeAbove चलाओ।

कई हल ऊँचाई घटते क्रम में छाँटते हैं और तल सूचकांक i के लिए सिर्फ j > i वाले बक्से आजमाते हैं। यह सही है अगर ऊँचाई घटती छाँटी गई हो और canBeAbove ऊँचाई सख्ती से छोटी माँगे: तल पर बैठ सकने वाले की ऊँचाई छोटी होगी, इसलिए i के बाद आएगा। चौड़ाई और गहराई canBeAbove में ही जाँचो।

मेमो वाली रिकर्शन (इंटरव्यू कहानी)

परिभाषा:

maxHeightAbove(bottomIndex) =
  bottom.height
  + तल पर बैठ सकने वाले j पर maxHeightAbove(j) का अधिकतम
  (या कोई j न चले तो सिर्फ bottom.height)

हर बक्से को पूरे ढेर का संभावित तल मानकर आजमाओ, वैश्विक अधिकतम लो। bottomIndex पर मेमो करो ताकि हर बक्सा-तल एक बार हल हो।

यह "जोड़े की सबसे लंबी श्रृंखला" या ३डी एलआईएस जैसा ही रूप है।

बॉटम-अप डीपी (एलआईएस शैली)

१. बक्से छाँटो (ऊँचाई के हिसाब से, नियम साफ रखो)। २. dp[i] = बक्सा i तल पर हो तो अधिकतम ढेर ऊँचाई (या शीर्ष; एक परंपरा पकड़ो)। ३. हर i के लिए वैध ऊपर (या नीचे) वाले j देखो: dp[i] = box[i].height + max(dp[j])। ४. उत्तर max(dp[i])।

दोनों रास्तों पर समय ओ(एन²)। मेमो या dp के लिए जगह ओ(एन)।

इस पोस्ट का चुनाव

पहले छाँटना + मेमो रिकर्शन (साफ कहानी: "इस बक्से को तल मानकर सबसे ऊँचा ढेर"), फिर छोटा बॉटम-अप जुड़वाँ।

४. जावा हल

मुख्य: छाँटना + मेमो रिकर्शन

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

class Box {
    int width;
    int height;
    int depth;

    Box(int width, int height, int depth) {
        this.width = width;
        this.height = height;
        this.depth = depth;
    }

    boolean canBeAbove(Box below) {
        return this.width < below.width
            && this.height < below.height
            && this.depth < below.depth;
    }
}

int stackOfBoxes(List<Box> input) {
    if (input == null || input.isEmpty()) {
        return 0;
    }

    Box[] boxes = input.toArray(new Box[0]);
    // सबसे ऊँचा पहले: ऊपर के उम्मीदवार अक्सर बाद में
    Arrays.sort(boxes, Comparator.comparingInt((Box b) -> b.height).reversed());

    int[] memo = new int[boxes.length]; // 0 = अभी नहीं; ऊँचाइयाँ धनात्मक
    int best = 0;
    for (int i = 0; i < boxes.length; i++) {
        best = Math.max(best, maxHeightWithBottom(boxes, i, memo));
    }
    return best;
}

/** जब boxes[bottomIndex] ढेर का तल हो तो अधिकतम ऊँचाई। */
int maxHeightWithBottom(Box[] boxes, int bottomIndex, int[] memo) {
    if (memo[bottomIndex] > 0) {
        return memo[bottomIndex];
    }

    Box bottom = boxes[bottomIndex];
    int bestAbove = 0;
    for (int i = bottomIndex + 1; i < boxes.length; i++) {
        if (boxes[i].canBeAbove(bottom)) {
            bestAbove = Math.max(bestAbove, maxHeightWithBottom(boxes, i, memo));
        }
    }

    memo[bottomIndex] = bottom.height + bestAbove;
    return memo[bottomIndex];
}

ऊँचाई घटते क्रम में चार बक्सों का विचार:

A (10, 12, 32)
B (4, 6, 7)
C (4, 5, 6)
D (1, 2, 3)

ए तल पर: बी, सी, डी आजमाओ। बी फिट। बी को ऊपरी हिस्से का तल मानकर डी तक बढ़ सकते हो। सी ए पर बैठे या नहीं, तीनों आयाम देखो। सबसे अच्छी श्रृंखला रखो।
बी तल पर: शायद डी ऊपर।
जब ऊपर कुछ न बैठे, एक बक्से वाले ढेर आधार हैं।

मेमो का मतलब: एक बार "बी तल पर सबसे अच्छा ढेर" निकला, ए और बाकी उसी नतीजे को दोबारा माँगें तो दोबारा मत गिनो।

बॉटम-अप जुड़वाँ (वही जटिलता)

int stackOfBoxesBottomUp(List<Box> input) {
    if (input == null || input.isEmpty()) {
        return 0;
    }

    Box[] boxes = input.toArray(new Box[0]);
    Arrays.sort(boxes, Comparator.comparingInt((Box b) -> b.height).reversed());

    int n = boxes.length;
    int[] dp = new int[n]; // boxes[i] तल पर अधिकतम ऊँचाई
    int best = 0;

    for (int i = n - 1; i >= 0; i--) {
        int bestAbove = 0;
        for (int j = i + 1; j < n; j++) {
            if (boxes[j].canBeAbove(boxes[i])) {
                bestAbove = Math.max(bestAbove, dp[j]);
            }
        }
        dp[i] = boxes[i].height + bestAbove;
        best = Math.max(best, dp[i]);
    }
    return best;
}

वही पुनरावृत्ति, छाँटी सूची के अंत से भरी ताकि "ऊपर" के परिणाम पहले से मौजूद हों।

वैकल्पिक: असली ढेर वापस

अगर क्रम भी चाहिए, parent[i] रखो या dp[i] की पसंद दोबारा चलाकर बनाओ। आधार समस्या के लिए सिर्फ ऊँचाई काफी।

५. जटिलता तालिका

तरीका	समय	अतिरिक्त जगह	नोट
उपसमुच्चय + क्रमचय	घातीय	स्टैक गहराई	सिर्फ सिखाने को; मत भेजो
छाँटना + मेमो रिकर्शन	ओ(एन²)	ओ(एन) मेमो + ओ(एन) स्टैक	साफ इंटरव्यू जवाब
छाँटना + बॉटम-अप डीपी	ओ(एन²)	ओ(एन)	वही विचार, बिना रिकर्शन
एक आयाम छाँटकर बिना पूरी जाँच	गलत	-	तीनों आयाम जरूरी

छाँटना ओ(एन लॉग एन)। नेस्टेड स्कैन ओ(एन²) चलाते हैं। इंटरव्यू वाले एन (दसियों से कुछ सौ बक्से) पर ठीक।

६. किनारे के मामले और आम गलतियाँ

इंटरव्यूअर ये छेड़ते हैं:

खाली इनपुट → ०।
एक बक्सा → उसकी ऊँचाई।
कोई किसी पर न बैठे → अलग-अलग ऊँचाइयों का अधिकतम (योग नहीं)।
पहले से पूरा घोंसला → सारी ऊँचाइयों का योग।
एक अक्ष पर बराबर आयाम → ढेर नहीं (< फेल)। <= लिखना आसान बग।
समान ऊँचाई, अलग चौड़ाई/गहराई → ऊँचाई छाँटने से पास आते हैं; ऊँचाई सख्ती से छोटी न हो तो canBeAbove फिर भी नकारेगा।
बहुत बक्से, एक लंबी श्रृंखला → मेमो फिर भी ओ(एन²) पर उप-ढेर दोहराता नहीं।
घुमाना → अगर मंजूर हो तो प्रति बक्सा अधिकतम ३ ओरिएंटेशन बनाकर वही डीपी। यहाँ नहीं, जब तक न पूछा जाए।

आम गलतियाँ:

१. एक या दो आयाम ही जाँचना। नियम तीनों का है। २. < की जगह <=। सख्त नियम में बराबर फलक नहीं। ३. हर बक्से को संभावित तल न आजमाना। वैश्विक उत्तर तलों पर अधिकतम है, सिर्फ maxHeightWithBottom(0) नहीं। ४. मेमो गलत आरंभ। ऊँचाइयाँ धनात्मक हों तो 0 = "अभी नहीं" ठीक। शून्य ऊँचाई हो तो अलग बूलियन या Integer नल। ५. छाँटकर मान लेना कि क्रम काफी है। चौड़ाई और गहराई के लिए canBeAbove फिर भी चाहिए। ६. ऊँचाई के योग की जगह बक्सों की गिनती बढ़ाना। दो मोटे ऊँचे पाँच छोटे को हरा सकते हैं।

छोटा धुआँ परीक्षण:

List<Box> boxes = new ArrayList<>();
boxes.add(new Box(4, 6, 7));
boxes.add(new Box(1, 2, 3));
boxes.add(new Box(4, 5, 6));
boxes.add(new Box(10, 12, 32));

System.out.println(stackOfBoxes(boxes)); // सबसे ऊँचे वैध ढेर का ऊँचाई योग
System.out.println(stackOfBoxes(List.of())); // 0
System.out.println(stackOfBoxes(List.of(new Box(2, 3, 4)))); // 3

प्रिंट पर भरोसा करने से पहले इंटरव्यूअर के साथ व्हाइटबोर्ड पर अपेक्षित संख्या हाथ से निकालो।

७. दोस्त को समझाओ: संक्षेप

बक्सों का ढेर पूछता है: अगर हर ऊपर वाला बक्सा चौड़ाई, गहराई और ऊँचाई में सख्ती से छोटा हो, तो सबसे ऊँचा टावर क्या?

१. canBeAbove(below) वाला Box मॉडल करो। २. ऊँचाई घटते क्रम में छाँटो ताकि छोटी ऊँचाई वाले उम्मीदवार बाद में आएँ। ३. "बक्सा आई तल पर अधिकतम ऊँचाई" = height[i] प्लस आई के ऊपर सबसे अच्छा वैध ढेर। ४. उस फलन को मेमो करो (या dp बॉटम-अप भरो)। उत्तर सभी तलों पर अधिकतम। ५. समय ओ(एन²)। सख्त असमानता और बाहरी लूप "हर तल आजमाओ" संभालो।

छाँटना, canBeAbove लिखना, और यह समझाना कि मेमो घातीय खोज को ओ(एन²) बनाता है, अगर ये आते हों तो समस्या ८.१३ तुम्हारी है। आगे बूलियन व्यंजक का मूल्यांकन, स्ट्रिंग पर एक और डीपी।