Second Largest in an Array: flowchart, algorithm and program
This program reads n distinct numbers and prints the second largest without sorting or storing them. It keeps two variables, largest and second, and updates them as each new number arrives, so it needs only one pass.
▶ Watch the dry run step by step →
Algorithm
- Step 1: Start.
- Step 2: Read n.
- Step 3: Read largest, x.
- Step 4: If x > largest, go to step 5; otherwise go to step 6.
- Step 5: Set second = largest; largest = x. Go to step 7.
- Step 6: Set second = x.
- Step 7: Set i = 2.
- Step 8: If i < n, go to step 9; otherwise go to step 15.
- Step 9: Read x.
- Step 10: If x > largest, go to step 11; otherwise go to step 12.
- Step 11: Set second = largest; largest = x. Go to step 14.
- Step 12: If x > second, go to step 13; otherwise go to step 14.
- Step 13: Set second = x.
- Step 14: Increase i by 1. Go to step 8.
- Step 15: Print second.
- Step 16: Stop.
Pseudocode
BEGIN
READ n
READ largest, x
IF x > largest THEN
second ← largest; largest ← x
ELSE
second ← x
END IF
i ← 2
WHILE i < n DO
READ x
IF x > largest THEN
second ← largest; largest ← x
ELSE
IF x > second THEN
second ← x
END IF
END IF
i++
END WHILE
PRINT second
END
Program in C, Python and Java
Second Largest in an Array program in C
#include <stdio.h>
int main() {
int n, i, x, largest, second;
printf("Enter n: ");
scanf("%d", &n);
printf("Enter %d numbers: ", n);
scanf("%d", &largest);
scanf("%d", &x);
if (x > largest) {
second = largest;
largest = x;
} else {
second = x;
}
for (i = 2; i < n; i++) {
scanf("%d", &x);
if (x > largest) {
second = largest;
largest = x;
} else if (x > second) {
second = x;
}
}
printf("Second largest = %d\n", second);
return 0;
}Second Largest in an Array program in Python
n = int(input("Enter n: "))
nums = list(map(int, input("Enter " + str(n) + " numbers: ").split()))
largest = nums[0]
x = nums[1]
if x > largest:
second = largest
largest = x
else:
second = x
for i in range(2, n):
x = nums[i]
if x > largest:
second = largest
largest = x
elif x > second:
second = x
print("Second largest =", second)Second Largest in an Array program in Java
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("Enter n: ");
int n = sc.nextInt();
System.out.print("Enter " + n + " numbers: ");
int largest = sc.nextInt();
int x = sc.nextInt();
int second;
if (x > largest) {
second = largest;
largest = x;
} else {
second = x;
}
for (int i = 2; i < n; i++) {
x = sc.nextInt();
if (x > largest) {
second = largest;
largest = x;
} else if (x > second) {
second = x;
}
}
System.out.println("Second largest = " + second);
}
}
Sample input: n = 5, numbers = 12 45 7 89 33
Output: Second largest = 45
How it works
- Read the first two numbers to set the starting values: the bigger one goes in largest and the smaller one in second. This avoids guessing a starting value like 0 or -1.
- For each remaining number x (the loop runs from i = 2 to n-1), first check if x > largest. If yes, the old largest becomes second and x becomes the new largest.
- Otherwise, check if x > second. If yes, x sits between the two, so it replaces second. If neither is true, x is ignored.
- On 12 45 7 89 33: after two numbers largest=45, second=12; 7 changes nothing; 89 makes largest=89, second=45; 33 changes nothing. The answer is 45.
- Each number is read and compared once, so the time is O(n) and the extra space is O(1).
Dry run (trace table)
| Step | Line | Box | n | largest | x | second | i | Output |
|---|---|---|---|---|---|---|---|---|
| 1 | 3 | Start | ||||||
| 2 | 6 | Read n | 5 | |||||
| 3 | 9 | Read largest, x | 5 | 12 | 45 | |||
| 4 | 10 | x > largest? | 5 | 12 | 45 | |||
| 5 | 12 | second = largest; largest = x | 5 | 45 | 45 | 12 | ||
| 6 | 16 | i = 2 | 5 | 45 | 45 | 12 | 2 | |
| 7 | 16 | i < n? | 5 | 45 | 45 | 12 | 2 | |
| 8 | 17 | Read x | 5 | 45 | 7 | 12 | 2 | |
| 9 | 18 | x > largest? | 5 | 45 | 7 | 12 | 2 | |
| 10 | 21 | x > second? | 5 | 45 | 7 | 12 | 2 | |
| 11 | 16 | i++ | 5 | 45 | 7 | 12 | 3 | |
| 12 | 16 | i < n? | 5 | 45 | 7 | 12 | 3 | |
| 13 | 17 | Read x | 5 | 45 | 89 | 12 | 3 | |
| 14 | 18 | x > largest? | 5 | 45 | 89 | 12 | 3 | |
| 15 | 20 | second = largest; largest = x | 5 | 89 | 89 | 45 | 3 | |
| 16 | 16 | i++ | 5 | 89 | 89 | 45 | 4 | |
| 17 | 16 | i < n? | 5 | 89 | 89 | 45 | 4 | |
| 18 | 17 | Read x | 5 | 89 | 33 | 45 | 4 | |
| 19 | 18 | x > largest? | 5 | 89 | 33 | 45 | 4 | |
| 20 | 21 | x > second? | 5 | 89 | 33 | 45 | 4 |
Time and space complexity
Time: O(n) · Space: O(1). The loop reads each of the n numbers once and does constant work per number, using only a few variables.
Common mistakes
- Initialising largest and second to 0 (or INT_MIN carelessly). With negative numbers, 0 would wrongly stay as the answer. Starting from the first two inputs is safer.
- Forgetting to move the old largest into second when a new maximum appears. Then second keeps a stale value and the answer is wrong, e.g. it would print 12 instead of 45 in the sample.
- Using only 'if' for the second check instead of 'else if', or skipping the second check entirely, so a number that is between second and largest is never recorded.
Viva questions
Q1. What does this program compute, and how many passes does it make over the data?
It finds the second largest of n numbers. It does it in a single pass, reading each number once and updating 'largest' and 'second' as it goes, without storing the array.
Q2. Why do you read the first two numbers before the loop, and why does the loop start at i = 2?
The first two numbers are used to initialise 'largest' and 'second' with real input values, ordered correctly. Two numbers are already consumed, so the loop handles the remaining n-2 numbers starting from index 2.
Q3. Why not initialise largest and second to 0 instead of reading values from the input?
If all numbers were negative, 0 would wrongly stay as the answer because it is bigger than every input. Starting from actual input values avoids that problem.
Q4. In the loop, what is the purpose of the 'else if (x > second)' branch?
If x is not bigger than largest but is bigger than second, then x is the new second largest, so we update only 'second'. Without this branch, such numbers would be ignored and the answer could be wrong, e.g. 5 9 7 should give 7.
Q5. When x > largest, why do you set second = largest before largest = x?
The old largest becomes the new second largest. If you assigned largest = x first, the old largest value would be overwritten and lost.
Q6. What happens if n is 1, or n is 0 or negative?
The program does not check n. The code reads two numbers unconditionally, so with n = 1 it reads an extra number and prints a meaningless answer, and for n <= 0 it also misbehaves. A check like 'if (n < 2)' with an error message is needed.
Q7. What happens with duplicate values, for example input 5 5 3 or 4 4 4?
The condition uses strict '>', so an equal value does not replace largest or second. For 5 5 3 the program prints 5 (second equals largest), and for 4 4 4 prints 4. If you want the second largest distinct value, you would need to check x != largest as well, and handle the case where none exists.
Q8. What is the time and space complexity, and what would change to find the second smallest?
Time is O(n) since each number is read and compared a constant number of times; space is O(1) as only a few variables are used. For the second smallest, flip the comparisons (use '<' instead of '>') so you track smallest and second smallest.
Frequently asked questions
Why not just sort the array and take the second last element?
Sorting takes O(n log n) time and needs the numbers stored. This one-pass method takes O(n) time and O(1) extra space, and it can work while reading the input.
What happens if the numbers are not distinct?
This code assumes distinct values. With duplicates of the maximum, such as 5 5 3, it would print 5 as the second largest because x > largest is false but x > second can still be true. To get the second distinct largest you would need to skip values equal to largest.
Does this program work when n is less than 2?
No. It reads two numbers before the loop, so it needs n >= 2. For n = 1 there is no second largest, and you should check n first and print a message.