कोडिंग इंटरव्यू: डुप्लिकेट्स के साथ k-वां सबसे बड़ा एलिमेंट खोजने के लिए Quickselect का उपयोग करें

प्रश्न और दायरा

एक अनसॉर्टेड इंटीजर ऐरे nums और 1 ≤ k ≤ nums.length दिए जाने पर, गैर-बढ़ते (non-increasing) क्रम में k-वां एलिमेंट लौटाएं। डुप्लिकेट्स अलग-अलग पोज़ीशन लेते हैं: [5, 5, 4] में दूसरा सबसे बड़ा मान 5 है, न कि दूसरा विशिष्ट (distinct) मान। जब ऐरे को म्यूटेट करने की अनुमति हो, तो लक्षित औसत समय O(n) के साथ O(1) अतिरिक्त स्पेस है; कोडिंग करने से पहले इस धारणा को स्पष्ट रूप से बताएं।

इंटरव्यूअर क्या जांच रहा है

एक मजबूत उत्तर "k-th largest" को आरोही (ascending) इंडेक्स target = n-k पर मैप करता है, फिर यह समझाता है कि पार्टीशन को केवल पिवट के चारों ओर एक सीमा स्थापित करने की आवश्यकता होती है; दूसरी साइड को कभी भी सॉर्ट करने की आवश्यकता नहीं होती है। यह डुप्लिकेट्स, k=1, k=n, ऑर्डर्ड इनपुट्स, और रैंडमाइज़्ड औसत कॉम्प्लेक्सिटी और वर्स्ट-केस गारंटी के बीच के अंतर को संभालता है।

कोडिंग से पहले स्पष्टीकरण

1. क्या इनपुट को संशोधित किया जा सकता है? इन-प्लेस पार्टीशन O(1) अतिरिक्त स्पेस लेता है; इसे सुरक्षित रखने के लिए एक O(n) कॉपी की आवश्यकता होती है।
2. क्या यह k-वीं पोज़ीशन है या k-वां विशिष्ट (distinct) मान है? पोज़ीशन की गणना सामान्य समस्या कथन है; विशिष्ट चयन के लिए अलग डुप्लिकेट हैंडलिंग की आवश्यकता होती है।
3. क्या डेटा स्ट्रीम के रूप में आ रहा है? Quickselect एक ही मटीरियलाइज़्ड ऐरे के लिए है; साइज़-k का min-heap एक स्ट्रीम के लिए O(n log k) प्रोसेसिंग प्रदान करता है।
4. क्या एक डिटर्मिनिस्टिक वर्स्ट-केस बाउंड अनिवार्य है? रैंडमाइज़्ड Quickselect का औसत O(n) होता है; एक सख्त वर्स्ट-केस दावे के लिए मीडियन-ऑफ-मीडियंस (median-of-medians) या लाइब्रेरी गारंटी की आवश्यकता होती है।

अनुशंसित समाधान और व्युत्पत्ति

पिवट से छोटे, बराबर और बड़े मानों में थ्री-वे पार्टीशनिंग का उपयोग करें। रूपांतरित आरोही इंडेक्स target के लिए, जब टारगेट lt के बाईं ओर स्थित हो तो बाएं अंतराल के साथ जारी रखें, जब यह gt के दाईं ओर स्थित हो तो दाएं अंतराल के साथ जारी रखें, और जब यह [lt, gt] में स्थित हो तो पिवट लौटाएं। बराबर तत्वों का यह बैंड (equal band) बार-बार एक आइटम को हटाने के बजाय सभी-बराबर इनपुट को एक ही स्कैन में पूरा कर देता है।

import random

def kth_largest(nums: list[int], k: int) -> int:
    if not 1 <= k <= len(nums):
        raise ValueError("k out of range")
    target = len(nums) - k
    left, right = 0, len(nums) - 1
    while left <= right:
        pivot = nums[random.randint(left, right)]
        lt, i, gt = left, left, right
        while i <= gt:
            if nums[i] < pivot:
                nums[lt], nums[i] = nums[i], nums[lt]
                lt += 1; i += 1
            elif nums[i] > pivot:
                nums[i], nums[gt] = nums[gt], nums[i]
                gt -= 1
            else:
                i += 1
        if target < lt:
            right = lt - 1
        elif target > gt:
            left = gt + 1
        else:
            return pivot
    raise RuntimeError("unreachable")

प्रत्येक इटरेशन अपने वर्तमान अंतराल को एक बार स्कैन करता है। यदि पिवट अंतराल को एक स्थिर अंश (constant fraction) से घटाता है, तो T(n)=T(cn)+O(n) का औसत O(n) प्राप्त होता है; वर्स्ट केस में बार-बार किसी एक्सट्रीम एलिमेंट का चयन करने से अभी भी O(n²) ही मिलता है। इटरेटिव रूप रिकर्सन डेप्थ से बचाता है और O(1) अतिरिक्त स्पेस का उपयोग करता है।

विकल्प और ट्रेड-ऑफ़

पूरी सॉर्टिंग को सत्यापित करना सबसे आसान है, इसमें O(n log n) की लागत आती है, और यह तब समझदारी भरा होता है जब ऐरे छोटा हो या बाद में पूर्ण क्रम की आवश्यकता हो। साइज़-k का min-heap इनपुट को सुरक्षित रखता है और इसमें O(n log k) समय और O(k) स्पेस की लागत आती है, जो स्ट्रीम्स के लिए उपयुक्त है या जब k, n से बहुत छोटा हो। C++ का std::nth_element औसत-रेखीय (average-linear) कॉम्प्लेक्सिटी के साथ समान पार्टीशन सेमांटिक्स को प्रदर्शित करता है; यह चयनित पोज़ीशन के किसी भी तरफ को सॉर्ट नहीं करता है।

विफलता के मोड, सीमाएं और प्रति-उदाहरण

• target = k-1 लिखने से k-वां सबसे छोटा मान मिलता है, जो अनुरोधित क्रम को उलट देता है।
• एक टू-वे पार्टीशन जो केवल एक बराबर आइटम को हटाता है, वह [7, 7, 7, ...] पर O(n²) समय ले सकता है; थ्री-वे पार्टीशन बराबर बैंड को एक साथ प्रोसेस कर लेता है।
• हमेशा अंतिम एलिमेंट को चुनने से सॉर्ट किए गए और उल्टे-सॉर्ट किए गए (reverse-sorted) इनपुट्स पर परफॉर्मेंस खराब हो सकती है। रैंडमाइज़ेशन संभावना को कम करता है, न कि एसिम्प्टोटिक वर्स्ट-केस बाउंड को।
• "k-th distinct largest" बराबर बैंड की गिनती किए बिना या उसे हटाए बिना स्टॉप कंडीशन का पुन: उपयोग नहीं कर सकता है।
• एक खाली ऐरे, k=0, या k>n को सीमा पर ही अस्वीकार कर दें, बजाय इसके कि किसी इंडेक्स एरर को एक अमान्य प्रश्न को छिपाने की अनुमति दी जाए।

परीक्षण और सत्यापन चेकलिस्ट

रैंडमाइज़्ड मामलों की तुलना sorted(nums)[-k] से करें; सभी-बराबर मान, ऋणात्मक और डुप्लिकेट्स, k=1, k=n, सॉर्ट किए गए इनपुट, और रिवर्स-सॉर्ट किए गए इनपुट शामिल करें। जब म्यूटेशन की अनुमति हो, तो पूरे ऐरे के क्रम के बजाय केवल परिणाम को असर्ट (assert) करें। पुनरुत्पादकता (reproducibility) के लिए रैंडम सीड को फिक्स करें और n बढ़ने पर तुलनाओं की संख्या रिकॉर्ड करें; एक भाग्यशाली रन कॉम्प्लेक्सिटी का प्रमाण नहीं होता है।

फॉलो-अप सवाल

वर्स्ट केस को लीनियर होने की गारंटी कैसे दी जा सकती है?

मीडियन-ऑफ-मीडियंस (median-of-medians) पिवट चुनें ताकि प्रत्येक राउंड एक निश्चित अंश को हटा दे, जिससे वर्स्ट-केस समय O(n) प्राप्त हो। इसके कॉन्स्टैंट्स अधिक होते हैं, इसलिए प्रोडक्शन कोड आमतौर पर रैंडमाइज़्ड चयन या मानक-लाइब्रेरी कार्यान्वयन को चुनता है।

आप इसे k-वें सबसे छोटे में कैसे बदलेंगे?

आरोही पार्टीशन को बनाए रखते हुए target = k-1 का उपयोग करें। सबसे बड़े एलिमेंट के फॉर्मूलेशन को target=n-k के रूप में रखना अक्सर ऐरे को उलटने की तुलना में अधिक स्पष्ट होता है।

आप इन्सर्ट्स और कई रैंक प्रश्नों का समर्थन कैसे करते हैं?

वन-शॉट Quickselect प्रत्येक क्वेरी पर फिर से स्कैन करता है। एक निश्चित k के लिए, साइज़-k का min-heap बनाए रखें; आर्बिट्रेरी रैंक क्वेरीज़ के लिए, सब-ट्री साइज़ से ऑगमेंटेड एक बैलेंस्ड ट्री पर विचार करें और अपडेट-टू-क्वेरी अनुपात के आधार पर चयन करें।