Finding the Second Largest Element in an Array

Quick answer: To find the second largest distinct element in an array, make a single pass while tracking two variables, largest and second. Whenever you see a value bigger than largest, shift largest down into second; whenever you see a value between the two, update second. This runs in O(N) time and O(1) space. If every element is the same (or N is 1) there is no second largest, so return −1.

This problem appears in almost every array practice set, from GeeksforGeeks to campus placement tests, and it is a favourite warm-up question in interviews because the obvious approach (sort it) is not the best one. In this guide you will see the problem statement with two worked examples, three approaches from brute force to optimal, a complexity comparison, complete code in Python and C++, and the edge cases that catch most candidates.

Problem statement

Given an array Arr of size N, find and return the second largest distinct element. If no such element exists — because the array has only one element or all elements are equal — return −1.

The word distinct matters. In {17, 17, 15}, the answer is 15, not 17, because the second largest value must differ from the largest.

Example 1

Input: N = 6, Arr = {11, 30, 17, 8, 40, 21}
Output: 30
40 is the largest; the next highest distinct value is 30.

Example 2

Input: N = 4, Arr = {1, 15, 17, 15}
Output: 15
17 is the largest. 15 appears twice but it is still the second largest distinct value.

Example 3 (edge case)

Input: N = 3, Arr = {9, 9, 9}
Output: −1
There is only one distinct value, so no second largest exists.

Approach 1: Sort the array

The first instinct is to sort in ascending order and look at the second-to-last element. The twist is duplicates: after sorting {1, 15, 17, 15} you get {1, 15, 15, 17}, and the element just before the largest is 15, which happens to be correct here. But for {9, 9, 9} it would wrongly return 9.

1. If N is 1, return −1.
2. Sort the array.
3. Walk backwards from index N−2. Return the first element that is not equal to Arr[N−1].
4. If you reach the start without finding one, return −1.

Time complexity is O(N log N) because of the sort; space depends on the sorting algorithm (Python’s sorted() makes a copy, O(N)). It is correct and easy to explain, but you are doing far more work than the problem requires — you only need the top two values, not a fully ordered list.

Approach 2: Two linear passes

The original version of this post used a clever variation: find the maximum, then scan again for the largest value that is strictly less than the maximum.

1. Find maxi, the maximum element, in one pass.
2. Initialise second to a sentinel such as −1 (valid when all elements are non-negative) or negative infinity.
3. Scan again. For each element strictly less than maxi and greater than second, update second.
4. Return second (−1 if it never changed).

Two passes is still O(N) time and O(1) space. It is a perfectly acceptable interview answer, and it is easier to reason about than the single-pass version because the two concerns — “what is the max?” and “what is the best value below it?” — are separated.

Approach 3: Single pass with two trackers (optimal)

You can merge both passes into one by keeping largest and second at the same time:

• If x > largest: the old largest becomes the second largest, and x is the new largest.
• Else if x > second and x != largest: x is the new second largest.
• Otherwise ignore x (it is a duplicate of the largest or too small).

Dry run on Example 1 ({11, 30, 17, 8, 40, 21}): start with largest = −∞, second = −∞. See 11 → largest = 11. See 30 → second = 11, largest = 30. See 17 → 17 > second, so second = 17. See 8 → nothing. See 40 → second = 30, largest = 40. See 21 → 21 < 30, nothing. Return 30.

One pass, O(N) time, O(1) space, and it works on streams where you cannot go back and read the data a second time. This is the answer interviewers are hoping to hear.

Complexity comparison

Working code in Python

def second_largest_sort(arr: list[int]) -> int:
    n = len(arr)
    if n < 2:
        return -1
    s = sorted(arr)
    for i in range(n - 2, -1, -1):
        if s[i] != s[-1]:
            return s[i]
    return -1


def second_largest_two_pass(arr: list[int]) -> int:
    if len(arr) < 2:
        return -1
    maxi = max(arr)
    second = float("-inf")
    for x in arr:
        if x < maxi and x > second:
            second = x
    return -1 if second == float("-inf") else second


def second_largest_single_pass(arr: list[int]) -> int:
    largest = second = float("-inf")
    for x in arr:
        if x > largest:
            second, largest = largest, x
        elif second < x < largest:
            second = x
    return -1 if second == float("-inf") else second


if __name__ == "__main__":
    tests = [
        [11, 30, 17, 8, 40, 21],   # 30
        [1, 15, 17, 15],           # 15
        [9, 9, 9],                 # -1
        [5],                       # -1
    ]
    for arr in tests:
        print(second_largest_sort(arr),
              second_largest_two_pass(arr),
              second_largest_single_pass(arr))

Output:

30 30 30
15 15 15
-1 -1 -1
-1 -1 -1

The condition second < x < largest in the single-pass version is doing two jobs at once: it rejects duplicates of the largest (because x < largest fails) and it only accepts improvements (because second < x).

Working code in C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    // Approach 1: sort, O(N log N)
    int secondLargestSort(vector<int> arr) {
        int n = arr.size();
        if (n < 2) return -1;
        sort(arr.begin(), arr.end());
        for (int i = n - 2; i >= 0; i--) {
            if (arr[i] != arr[n - 1]) return arr[i];
        }
        return -1;
    }

    // Approach 2: two passes, O(N)
    int secondLargestTwoPass(const vector<int>& arr) {
        if (arr.size() < 2) return -1;
        int maxi = *max_element(arr.begin(), arr.end());
        long long second = LLONG_MIN;
        for (int x : arr) {
            if (x < maxi && x > second) second = x;
        }
        return second == LLONG_MIN ? -1 : static_cast<int>(second);
    }

    // Approach 3: single pass, O(N), O(1) space
    int secondLargestSinglePass(const vector<int>& arr) {
        long long largest = LLONG_MIN, second = LLONG_MIN;
        for (int x : arr) {
            if (x > largest) {
                second = largest;
                largest = x;
            } else if (x > second && x < largest) {
                second = x;
            }
        }
        return second == LLONG_MIN ? -1 : static_cast<int>(second);
    }
};

int main() {
    Solution sol;
    vector<int> a1 = {11, 30, 17, 8, 40, 21};
    vector<int> a2 = {1, 15, 17, 15};
    vector<int> a3 = {9, 9, 9};

    cout << sol.secondLargestSinglePass(a1) << endl;  // 30
    cout << sol.secondLargestSinglePass(a2) << endl;  // 15
    cout << sol.secondLargestSinglePass(a3) << endl;  // -1
    cout << sol.secondLargestTwoPass(a1) << " " << sol.secondLargestSort(a1) << endl;  // 30 30
    return 0;
}

Using LLONG_MIN as the sentinel (rather than −1) keeps the code correct even when the array contains negative numbers. A sibling problem that uses the same “track state in one pass” idea is finding the missing number in an array.

Common mistakes and pitfalls

1. Returning sorted[N−2] directly. Fails whenever the largest value is duplicated, such as {5, 9, 9} where the answer is 5, not 9.
2. Using −1 as the sentinel with negative inputs. For {−3, −7} the correct answer is −7, but a sentinel of −1 would never be updated and you would return −1 by mistake. Use negative infinity or LLONG_MIN.
3. Forgetting the x != largest check. Without it, in {17, 15, 17} the second 17 would overwrite second, and you would return 17 instead of 15.
4. Not handling N = 1 or an empty array. Accessing arr[n−1] on an empty vector is undefined behaviour in C++.
5. Sorting in place when the caller still needs the original order. Take a copy, or use a non-mutating approach.
6. Mixing up “second largest” with “second largest distinct”. Read the problem statement; some platforms want the kth order statistic including duplicates.

Frequently asked questions

Why not just use a built-in like sorted(set(arr))[-2] in Python?

It is a fine one-liner for scripts, and it correctly handles duplicates thanks to set. But it is O(N log N) time and O(N) space, and it crashes with IndexError when there is only one distinct value. In an interview you should be able to write the O(N) single-pass version and explain why it is better.

How do I extend this to the kth largest element?

For small k, keep a min-heap of size k and push every element, popping when the heap exceeds k; the top is the answer in O(N log k). For general k, Quickselect gives average O(N). Python’s heapq.nlargest(k, arr) wraps the heap approach.

Does the single-pass approach work on a data stream?

Yes. That is its main advantage over sorting and over the two-pass method. You only ever store two numbers, so you can process values as they arrive without buffering them.

What should I return if the array has negative numbers only?

The same logic applies; just make sure your sentinel is smaller than any possible input. Returning −1 for “not found” is a convention from the problem statement, so if −1 could be a legitimate answer in your context, use None or an exception instead.

Key takeaways

• The optimal solution tracks largest and second in one O(N) pass with O(1) extra space.
• Sorting works but is O(N log N) and still needs a duplicate check; it is the brute-force baseline, not the final answer.
• “Distinct” means duplicates of the maximum must be skipped — the x != largest condition is essential.
• Use negative infinity (or LLONG_MIN) as the sentinel so negative inputs are handled correctly.
• Return −1 when N < 2 or every element is identical.

Array fundamentals like this are the gateway to harder interview topics. If you want structured practice across data structures, algorithms and system design, with mock interviews and personalised feedback, explore our Interview Preparation program. Prefer video walkthroughs? Follow along on our YouTube channel.