Practice › Arrays
Second Largest Element
Easy · Arrays · Asked at TCS, Infosys, Wipro, Accenture, Cognizant
Print the second largest distinct value in the array, or -1 if it does not exist.
Input
First line: n. Second line: n space-separated integers.
Output
The second largest distinct value, or -1.
Constraints
- 1 ≤ n ≤ 10^5
- 0 ≤ a[i] ≤ 10^9
Try to do it in a single pass.
Example 1
Input
6 12 35 1 10 34 1
Output
34
Example 2
Input
3 10 10 10
Output
-1
Hints
- Track two values while scanning: the largest and the second largest.
- Only update "second" with values strictly smaller than "largest", so duplicates of the maximum don't count.
Approach
Scan once keeping first and second (both start at -1, since values are ≥ 0). For each x: if x > first, the old first becomes second and x becomes first; else if first > x > second, x becomes second. If second is still -1 at the end, no second distinct value exists.
Complexity: O(n) time · O(1) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
long long first = -1, second = -1, x;
for (int i = 0; i < n; i++) {
cin >> x;
if (x > first) {
second = first;
first = x;
} else if (x < first && x > second) {
second = x;
}
}
cout << second << "\n";
return 0;
}Python solution
import sys
data = list(map(int, sys.stdin.read().split()))
n, a = data[0], data[1:]
first = second = -1
for x in a[:n]:
if x > first:
first, second = x, first
elif first > x > second:
second = x
print(second)Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long first = -1, second = -1;
for (int i = 0; i < n; i++) {
long x = sc.nextLong();
if (x > first) {
second = first;
first = x;
} else if (x < first && x > second) {
second = x;
}
}
System.out.println(second);
}
}