Second Largest

JavaView on GFG

Time: O(n)

Space: O(1)

Intuition

Find second largest element in array without sorting. Single pass tracking max and second max.

Algorithm

1max1 = max2 = INT_MIN. For each num: if num > max1: max2=max1, max1=num. Else if num > max2 and num != max1: max2=num.

Common Pitfalls

•Handle duplicates: second largest must be strictly less than largest. Return -1 if no second largest exists.

Second Largest.java

Java

// Approach: Single pass tracking the largest and second largest distinct values.
// Time: O(n) Space: O(1)
class Solution {
    public int getSecondLargest(int[] arr) {
        int l = arr[0];
        int sl = -1;
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > l) {
                sl = l;
                l = arr[i];
            } else if (arr[i] < l && arr[i] > sl) {
                sl = arr[i];
            }
        }
        return sl;
    }
}

Was this solution helpful?