Second Largest Number

Your task is to design an algorithm that finds the second largest number in an unsorted list of integers.

The algorithm should run in linear time, i.e. \(O(n)\), where \(n\) is the number of integers in the list.

If the list does not contain at least two distinct numbers, your program should output None.

Examples:

• Input: 10 5 4 3 -1 → Output: 5
• Input: 5 → Output: None
• Input: 8 8 8 8 → Output: None
• Input: 1 2 3 4 5 → Output: 4
• Input: 5 4 3 2 1 → Output: 4
• Input: -10 -20 -30 -40 -50 → Output: -20
• Input: 5 1 5 2 3 → Output: 3
• Input: 1000000000 999999999 1000000000 → Output: 999999999
• Input: -1 0 1 -2 2 3 -3 → Output: 2

inputFormat

The input is given in a single line from stdin containing space-separated integers.

You can assume that there is at least one integer provided.

outputFormat

Output the second largest distinct integer from the input list to stdout. If there is no such number, output None.

10 5 4 3 -1

5