Second Largest

Given an array of integers nums, return the second-largest element in the array. If the second-largest element does not exist, return -1.

Array can have duplicates.

Brute Force#

Sort the array so the largest element sits at the end. Then walk backwards from the second-to-last position until we find an element strictly smaller than nums[n-1], which is the second largest (handling duplicates). Sorting takes O(n log n) and the idea is straightforward, but it is wasteful — we only need two values, not a fully sorted array.

• Sort the array
• Traverse from second last element, when element != last element (coz of duplicates) return element

Time Complexity: O(nlogn)

Space Complexity: O(1)

Better Approach#

Use two separate linear scans. The first pass finds the absolute largest element. The second pass finds the largest element strictly smaller than it — that is the second largest. Each pass is O(n) and requires O(1) extra space. This is already much better than sorting, but we can collapse both passes into one.

• Traversal 1: Find largest element
• Traversal 2: Find element that is just smaller than largest (element < largest)

Time Complexity: O(n) + O(n)

Space Complexity: O(1)

Optimal Approach#

Maintain two variables, largest and sec_largest, initialized to INT_MIN. In a single pass, when the current element exceeds largest, we demote the old largest to sec_largest before updating largest. When the current element is between the two, we update sec_largest directly. This collapses the two-pass better approach into one loop, keeping the same O(n) time and O(1) space.

class Solution {
public:
    int secondLargestElement(vector<int>& nums) {

        int largest = INT_MIN, sec_largest = INT_MIN;
        for(int i=0;i<nums.size();i++){
            if(nums[i]>largest){
                sec_largest = largest;
                largest = nums[i];
            }
            else if(nums[i] < largest && nums[i]>sec_largest){
                sec_largest = nums[i];
            }
        }
        return sec_largest == INT_MIN ? -1 : sec_largest;
    }
};

Time Complexity: O(n)

Space Complexity: O(1)