Find the Second Largest Element

Table of Contents +

This looks like a tiny question. But the interviewer is not really asking you to find a number. They want to see if you can walk through an array once and track two things at the same time. So can you keep the biggest and the second biggest in your head while you scan? That is the real test here.

🔍 The Problem

You are given an array of numbers. You have to return the second largest distinct value. Distinct means we count each value only once. So if the biggest number shows up many times, that does not give us the second largest.

Input:  [10, 5, 20, 8, 20]
Output: 10


Here 20 is the largest. The second largest distinct value is 10, not 20 again.

🐢 The Brute Force Way

The first idea most people say out loud is simple. Sort the array. Then look at the end, because the biggest values sit there.

But there is a catch. The largest value can repeat. So you cannot just pick the second-last element. You have to start from the end and walk back until you find a value that is smaller than the largest. That smaller value is your answer.

This works. But sorting costs O(n log n) time. We are doing a lot of work just to find two numbers. The interviewer will likely ask if you can do it faster.

⚡ The Optimal One-Pass Way

Here is the better idea. We do not need to sort at all. We just walk through the array in one pass and remember two values as we go.

  • largest holds the biggest value we have seen so far.
  • secondLargest holds the biggest value that is still smaller than largest.

Now the tricky part is the update logic. So go slow here. For each number we look at:

  • If the number is bigger than largest, then the old largest is now beaten. So the old largest becomes secondLargest, and the new number becomes largest.
  • If the number is not bigger than largest but is bigger than secondLargest and is not equal to largest, then it becomes the new secondLargest.
  • Otherwise we just skip it.

That equal check matters. It keeps duplicates of the largest out of our second place.

Tip

The order of the checks is everything. Always compare with largest first. If you update secondLargest before checking largest, you can overwrite the value you needed.

🪜 Steps to Find It

  1. Start largest and secondLargest at a very small value (negative infinity).
  2. Walk through each number in the array.
  3. If the number is greater than largest, move largest into secondLargest, then set largest to the number.
  4. Else if the number is less than largest and greater than secondLargest, set secondLargest to the number.
  5. After the loop, if secondLargest is still the very small starting value, there was no valid second largest.
second_largest.py
def second_largest(arr):
    """Return the second largest distinct value, or None if none exists."""
    largest = float("-inf")
    second = float("-inf")
    for x in arr:
        if x > largest:
            second = largest   # old largest steps down
            largest = x        # new value takes the top
        elif x < largest and x > second:
            second = x         # a new runner-up
    return None if second == float("-inf") else second




arr = [10, 5, 20, 8, 20]
result = second_largest(arr)
if result is None:
    print("No second largest")
else:
    print("Second largest:", result)

The output of the above code will be:

Second largest: 10

Note

The C, C++, and Java versions use INT_MIN (or Integer.MIN_VALUE) to mean “no second largest”. But INT_MIN is also a real number a user could put in the array. So if the true second largest were INT_MIN, you could not tell it apart from the empty case. A cleaner fix is to return a separate signal, like a boolean flag, the way Python returns None and JavaScript returns null.

⏱️ Time and Space Complexity

Now let us compare the two ways side by side. The sort method scans well but pays for the sorting. The one-pass method touches each element only once, so it runs in O(n) time and O(1) space.

Approach Time Space
Brute force (sort then scan) O(n log n) O(1) or O(n)
Optimal (one pass) O(n) O(1)

Caution

Watch the edge cases. If every value is the same, like [7, 7, 7], there is no distinct second largest. The same is true if the array has fewer than two distinct values. So always handle the case where secondLargest never changed and tell the interviewer what you return then.

🧩 Key Takeaways

  • ✅ The interviewer is testing if you can track two values in a single scan, not just find a maximum.
  • ✅ The brute force sort works but costs O(n log n). The one-pass scan does it in O(n) time and O(1) space.
  • ✅ Always compare with largest first. When a new value beats largest, the old largest becomes secondLargest.
  • ✅ The equal check keeps duplicates of the largest out of second place, so you get a truly distinct value.
  • ✅ Handle the edge case where there is no valid second largest, like all equal values or too few distinct values.

Check Your Knowledge

Test what you learned. Pick an answer for each question, then click Check.

  1. 1

    Why is the brute force sort method slower than the one-pass method?

    Why: Sorting costs O(n log n), but a single scan only needs O(n) time to track the top two values.

  2. 2

    When a new number is greater than `largest`, what should happen?

    Why: The old top value steps down into second place, and the new bigger value takes the top spot.

  3. 3

    Why do we check that a value is not equal to `largest` before making it `secondLargest`?

    Why: Without the not-equal check, a repeated largest value would wrongly fill the second place.

  4. 4

    What should the function do for the input `[7, 7, 7]`?

    Why: All values are equal, so there is no distinct second largest and the function signals that case.

Score: 0 / 4

🚀 What’s Next?

Previous Find the Largest Element in an Array Next Rotate an Array by K Positions

Share & Connect

Share on LinkedIn