📘 Lesson · Lesson 58

Second Largest in Array

समस्या

{10, 5, 20, 8, 15} जैसे array में, second largest element 15 है (largest 20 है)। हम इसे बस दो variables इस्तेमाल करके एक pass में ढूँढ सकते हैं — कोई sorting नहीं चाहिए। यह आम interview सवाल है।

💡 चलते-चलते दो values track कीजिए: अब तक का largest और अब तक का second largest।

दो-variable विचार

first (largest) और second (second largest) रखिए, दोनों सबसे छोटी संभव value से शुरू। हर element को:

अगर वो first को हराए, पुराना first second बन जाता है, और यह first।
वरना अगर वो second को हराए (पर first को नहीं), वो second बन जाता है।

Java program

public class SecondLargest {
    public static void main(String[] args) {
        int[] a = {10, 5, 20, 8, 15};
        int first = Integer.MIN_VALUE;
        int second = Integer.MIN_VALUE;

        for (int x : a) {
            if (x > first) {
                second = first;   // पुराना max नीचे खिसकता है
                first = x;
            } else if (x > second && x != first) {
                second = x;
            }
        }
        System.out.println("Second largest: " + second);
    }
}

Second largest: 15

दोनों Integer.MIN_VALUE से शुरू होते हैं। हर नया maximum पुराने को second में धकेलता है। दोनों के बीच की values सिर्फ़ second update करती हैं।

Dry run

Dry Run — Second largest, array {10,5,20,8,15}

x	x > first?	first	second
Start	—	−∞	−∞
10	haan	10	−∞
5	nahi (5>−∞ second)	10	5
20	haan	20	10
8	nahi	20	10
15	nahi (15>10)	20	15
Second largest = 15

💡 ऐसे समझिए

जब नया सबसे बड़ा आए (20), पुराना सबसे बड़ा (10) second में खिसक जाता है। 15 जैसी values जो second को हराएँ पर first को नहीं, बस second update करती हैं। अंत में second = 15।

एक pass क्यों काफ़ी है

चूँकि हम largest और second largest एक साथ track करते हैं, एक loop हर value एक बार देखता है और जिन दो की हमें परवाह है उन्हें update रखता है। यह O(n) है — बस दूसरा element देखने को पूरा array sort करने (O(n log n)) से तेज़, और यह array नहीं बदलता।

आम गलतियाँ

Variables को 0 से शुरू करना। Integer.MIN_VALUE इस्तेमाल कीजिए, वरना negative arrays टूटते हैं।
first को second में खिसकाना भूलना। नए max पर, पुराना max नीचे ले जाइए।
Duplicate maxes गिनना। distinct second चाहिए तो x != first जोड़िए।
अनावश्यक sorting। एक pass तेज़ है और array अछूता रखता है।

सारांश

Second largest maximum के बाद सबसे बड़ी value है।
एक pass में first और second track कीजिए।
नया maximum पुराने को second में धकेलता है।
सुरक्षा को दोनों Integer.MIN_VALUE से शुरू कीजिए।
यह O(n) है — sorting से तेज़ और array नहीं बदलता।

आगे, array sort कीजिए bubble sort से, या दोहराव हटाइए remove duplicates from an array में।

अक्सर पूछे जाने वाले प्रश्न (FAQ)

Array में second largest element कैसे ढूँढूँ?

दो variables रखिए, first और second, दोनों बहुत छोटे से शुरू। Array में एक बार loop कीजिए: अगर value first को हराए, first को second में ले जाइए और first update कीजिए; वरना अगर second को हराए (पर first को नहीं), second update कीजिए। अंत में, second जवाब रखता है।

क्या second largest एक pass में ढूँढ सकता हूँ?

हाँ। largest और second largest track करते दो variables से, array में एक loop काफ़ी है — O(n)। आपको array sort नहीं करना पड़ता, जो धीमा होता।

बस array sort करके दूसरा element क्यों न लूँ?

Sorting चलती पर O(n log n) है और array order बदलती है। दो-variable तरीका O(n) पर तेज़ है और array नहीं बदलता, तो बस second largest ढूँढने को बेहतर।

Variables को बहुत छोटी values से क्यों शुरू करूँ?

first और second को सबसे छोटी संभव value (जैसे Integer.MIN_VALUE) से शुरू करना पक्का करता है कि पहले असली elements हमेशा बड़े होंगे, तो तुलनाएँ शुरू से सही चलती हैं।

अगर array में largest values duplicate हों तो?

आप शायद second largest distinct value चाहें। उस स्थिति में, second update करते समय first के बराबर values skip कीजिए, ताकि maximum के duplicates second largest न गिने जाएँ।

← Back to Java Tutorial

💻 लाइव कोड एडिटर

इस पेज के प्रोग्राम यहीं तैयार हैं — चलाएँ, बदलें और सीखें। कुछ भी इंस्टॉल किए बिना।

OneCompiler द्वारा संचालित। कोड एडिटर में अपने आप आ जाता है — Run दबाकर आउटपुट देखें। अगर एडिटर न खुले तो नए टैब में खोलें.