Easy–medium · edge cases

Second Largest

Find the largest number you already know how to find. The second largest is the same problem with one extra variable — and a trap about what happens when every number is identical.

At a glanceTrack the largest and the second-largest distinct value in one pass; when every element is equal there is no second largest, and the answer is the word none.

Problem

Input: The first line is an integer n (2 ≤ n ≤ 1000). The second line holds n integers separated by spaces (−1000 ≤ ai ≤ 1000).

Output: The second largest distinct value. If every number is the same, print none.

Samples:

InputOutput
5
3 9 2 9 7		7
4
1 1 1 1		none
3
-5 -3 -9		-5

"Distinct" is the whole difficulty. With 3 9 2 9 7 the answer is 7, not 9 — 9 appears twice but it is still just one value.

Your solution

main.cpp — your solution
Custom input for "Run my input"

Judging runs in your browser against hidden tests. A runaway loop is cut off after 3 seconds — still, make sure every loop has an exit. Your code is saved in this browser as you type.

Stuck? Hints

Hint 1 — Start from the maximum you already know

One variable big holds the largest seen so far. Add a second one, second. Every time a new number beats big, the old big gets demoted into second — that single line is the entire trick.

Hint 2 — Two branches, not one

If x > big, shift. Otherwise, if x is smaller than big but bigger than second, it becomes the new second. That second branch is what makes duplicates harmless: when x == big neither branch fires, so a repeated maximum never overwrites the runner-up.

Hint 3 — Where do you start the two variables?

Not 0. The inputs can be negative, so 0 would look like a valid "largest" that never existed. Use a value below any legal input — -1000000000 — and at the end check whether second is still that sentinel: if it is, there was no second distinct value.

Solution (try it first!) 
#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int big = -1000000000, second = -1000000000;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        if (x > big) {
            second = big;
            big = x;
        } else if (x < big && x > second) {
            second = x;
        }
    }
    if (second == -1000000000) cout << "none" << endl;
    else cout << second << endl;
    return 0;
}

Notice what you did not do: nothing was stored, nothing was sorted. One pass, two variables, done — O(n) time and O(1) memory. The same demote-and-shift shape gives you the third largest, the two smallest, and the best two scores in a game. Next, put that O(1) memory to work on a problem where the array must actually be reordered: Bubble Sort.

Deep dive

Why this works

One pass, two variables, and the job is done — no array, no sorting. That demote-and-shift shape is the skeleton of every Top-K problem you will meet.

The cost

O(n) time, O(1) memory. Sorting first and taking the runner-up is O(n log n) plus a copy of the data — spreading the whole deck to read one card.

Where it goes wrong

  • Starting second at 0 prints 0 for all-negative input — an answer that does not exist in the data.
  • Writing only the x > big branch and forgetting x < big && x > second leaves second stuck on the old maximum when values repeat.

Next step

Now let a rule run itself and watch where it lands: Collatz Steps.

Two things to remember

  • Two variables, one demotion: when the new king takes the throne, the old one becomes second.
  • The sentinel must be smaller than any legal input, or it will masquerade as an answer.
🐞 This version fails — open it and try

second starts at 0 — with all-negative input it prints 0

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int big = 0, second = 0;   // assumes the input is positive
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        if (x > big) {
            second = big;
            big = x;
        } else if (x < big && x > second) {
            second = x;
        }
    }
    cout << second << endl;
    return 0;
}