🔹 Finding the Second Largest Element (Deep Dive, Interview-Ready)

"Find the second largest element in an array" is a classic, foundational algorithm question. While it seems simple, interviewers use it to test your understanding of Time Complexity ($O(N)$ vs $O(N \log N)$), Space Complexity, and your ability to optimize from a naive solution to an optimal one.

📌 1. Approach 1: The Naive Way (Sorting)

The most intuitive approach is to simply sort the array and pick the second-to-last element.

public int findSecondLargest(int[] arr) {
    if (arr.length < 2) throw new IllegalArgumentException("Array too small");
    
    Arrays.sort(arr); // Mutates the array
    return arr[arr.length - 2];
}

🔸 Complexity Analysis

• Time Complexity: $O(N \log N)$. Sorting the entire array is massive overkill just to find one element.
• Space Complexity: $O(1)$ or $O(\log N)$ depending on the underlying sorting algorithm (Java uses Dual-Pivot Quicksort for primitives).
• Drawback: It mutates (changes the order of) the original array, which is often unacceptable in production code unless a copy is made.

📌 2. Approach 2: The Generic Way (Min-Heap)

If the interviewer changes the question to "Find the K-th largest element," sorting still works, but a PriorityQueue (Min-Heap) is the standard, scalable answer. We maintain a heap of size $K$ (in this case, 2).

public int findSecondLargest(int[] arr) {
    // A Min-Heap that will hold exactly 2 elements
    PriorityQueue<Integer> minHeap = new PriorityQueue<>(2);
    
    for (int num : arr) {
        minHeap.offer(num);
        // If heap grows beyond size 2, remove the smallest element
        if (minHeap.size() > 2) {
            minHeap.poll(); 
        }
    }
    // The root of the Min-Heap is now the 2nd largest element overall
    return minHeap.peek();
}

🔸 Complexity Analysis

• Time Complexity: $O(N \log K)$. Since $K=2$, $\log(2)$ is a constant, so this is effectively $O(N)$.
• Space Complexity: $O(K)$. Since $K=2$, this is effectively $O(1)$.
• Advantage: Scalable to any $K$. Does not mutate the original array.

📌 3. Approach 3: The Optimal Way (Single Pass)

For specifically the 1st, 2nd, or 3rd largest elements, you don't need a heap. You can track the largest and second-largest values simultaneously in a single pass over the array.

public int findSecondLargest(int[] arr) {
    if (arr.length < 2) throw new IllegalArgumentException("Array too small");

    int first = Integer.MIN_VALUE;
    int second = Integer.MIN_VALUE;

    for (int num : arr) {
        if (num > first) {
            // Demote the current largest to second largest
            second = first; 
            // Update the new largest
            first = num; 
        } else if (num > second && num != first) {
            // Update second largest only (ignoring duplicates of the first)
            second = num;
        }
    }
    
    if (second == Integer.MIN_VALUE) {
        throw new RuntimeException("No second largest element found (all elements were equal)");
    }
    
    return second;
}

🔸 Complexity Analysis

• Time Complexity: $O(N)$. We look at each element exactly once.
• Space Complexity: $O(1)$. We only use two integer variables.

📊 4. Complexity Comparison Summary

🔥 Interview Gold Statement

"To find the second largest element, the naive approach is to sort the array in $O(N \log N)$ time, but this is overkill and mutates the source data. A more scalable approach is using a PriorityQueue (Min-Heap) of size $K=2$, which drops the time complexity to $O(N \log K)$. However, the absolute optimal solution for exactly the second largest is a Single-Pass algorithm tracking highest and secondHighest variables. This achieves $O(N)$ time and strict $O(1)$ space without altering the original array."