Second Largest Element in Array

Given an integer array nums, return the second largest distinct element in the array.

The answer must be strictly smaller than the largest element. Return -1 if fewer than two distinct values exist.

Brute Force: Sorting

Sort a copy of the array, then look for the first value smaller than the largest.

1. If the array has fewer than 2 elements, return -1.
2. Make a copy of the array and sort it. The largest value is now at the end.
3. Start from the second last index and move backward.
4. Skip every value equal to largest, because duplicates of the maximum are not distinct.
5. Return the first value smaller than largest.
6. If no such value exists, return -1.

class Solution {
    public:
    int secondLargest(vector<int>& nums) {
        int n = nums.size();

        if (n < 2) {
            return -1;
        }

        vector<int> sortedNums = nums;
        sort(sortedNums.begin(), sortedNums.end());

        int largest = sortedNums[n - 1];

        for (int index = n - 2; index >= 0; index--) {
            if (sortedNums[index] < largest) {
                return sortedNums[index];
            }
        }

        return -1;
    }
};

• Time: O(n log n). Sorting is the slow part.
• Space: O(n). We keep a sorted copy of the array.

Better Approach: Two Passes

Sorting is not needed. We only care about the largest and the second largest. So we use two simple loops.

1. If the array has fewer than 2 elements, return -1.
2. Pass 1: find the largest value.
3. Pass 2: look only at values strictly smaller than largest, and keep the biggest one as secondLargest.
4. Use a flag hasSecond, so we do not depend on a fake value like -1 or INT_MIN.
5. If hasSecond is true, return secondLargest. Otherwise return -1.

class Solution {
    public:
    int secondLargest(vector<int>& nums) {
        int n = nums.size();

        if (n < 2) {
            return -1;
        }

        int largest = nums[0];

        for (int index = 1; index < n; index++) {
            if (nums[index] > largest) {
                largest = nums[index];
            }
        }

        int secondLargest = 0;
        bool hasSecond = false;

        for (int current : nums) {
            if (current < largest) {
                if (!hasSecond || current > secondLargest) {
                    secondLargest = current;
                    hasSecond = true;
                }
            }
        }

        if (!hasSecond) {
            return -1;
        }

        return secondLargest;
    }
};

• Time: O(n). Two passes, which is still linear.
• Space: O(1). We only use a few variables.

Optimal Approach: Single Pass

We can track both values in one pass.

1. If the array has fewer than 2 elements, return -1.
2. Set largest = nums[0]. Keep secondLargest and a flag hasSecond = false.
3. Loop from index 1. For each current:
   • If current > largest: the old largest becomes secondLargest, then largest = current. Set hasSecond = true.
   • Else if current < largest: if hasSecond is false or current > secondLargest, update secondLargest = current and set hasSecond = true.
   • If current == largest: ignore it, because the answer must be distinct.
4. If hasSecond is true, return secondLargest. Otherwise return -1.

class Solution {
    public:
    int secondLargest(vector<int>& nums) {
        int n = nums.size();

        if (n < 2) {
            return -1;
        }

        int largest = nums[0];
        int secondLargest = 0;
        bool hasSecond = false;

        for (int index = 1; index < n; index++) {
            int current = nums[index];

            if (current > largest) {
                secondLargest = largest;
                largest = current;
                hasSecond = true;
            } else if (current < largest) {
                if (!hasSecond || current > secondLargest) {
                    secondLargest = current;
                    hasSecond = true;
                }
            }
        }

        if (!hasSecond) {
            return -1;
        }

        return secondLargest;
    }
};

Dry Run

Take nums = [12, 35, 1, 10, 34, 1] with the single pass approach.

1Start: largest = 12, secondLargest = none, hasSecond = false
2 
3Step | current | what happens                           | largest | secondLargest
4-----|---------|----------------------------------------|---------|--------------
5  1  |  35     | 35 > largest, old largest moves down   |  35     |  12
6  2  |  1      | 1 < largest, but 1 > 12? No            |  35     |  12
7  3  |  10     | 10 < largest, but 10 > 12? No          |  35     |  12
8  4  |  34     | 34 < largest, and 34 > 12? Yes         |  35     |  34
9  5  |  1      | 1 < largest, but 1 > 34? No            |  35     |  34
10 
11hasSecond = true, so return secondLargest.
12 
13Return: 34

Comparison of All Approaches

Complexity

How to Explain It in an Interview