Sorting and taking the second last element works, but costs O(n log n) and fails on duplicates. The interviewer wants one pass with two variables.
One pass, two variables
static Integer secondLargest(int[] a) {
if (a == null || a.length < 2) return null;
long first = Long.MIN_VALUE, second = Long.MIN_VALUE;
for (int x : a) {
if (x > first) {
second = first;
first = x;
} else if (x > second && x < first) {
second = x;
}
}
return second == Long.MIN_VALUE ? null : (int) second;
}
Why it is written this way
- When a new largest arrives, the old largest becomes second: that is the line
second = first. x < firstskips duplicates of the largest, so[5, 5, 3]gives 3, not 5.- Starting from
Long.MIN_VALUEinstead of 0 handles all-negative arrays such as[-4, -2, -9], which gives -4. - Using
longfor the trackers means a realInteger.MIN_VALUEin the array is not confused with “not found”. Returningnullcovers arrays like[7, 7, 7]with no second distinct value.
Time O(n), space O(1).
Dry run on [12, 35, 1, 10, 34, 1]
x=12 first=12 second=-inf
x=35 first=35 second=12
x=1 no change
x=10 no change
x=34 second=34
x=1 no change
answer: 34
Follow-ups
- Find the kth largest: use a min-heap of size k (O(n log k)) or Quickselect (O(n) on average).
- Find the second smallest: flip the comparisons.
- What if the array is a stream you cannot store?
This answer was written by Debugger’s Space as practice material. It is asked in most Indian IT services interviews (TCS, Infosys, Wipro, HCLTech, Tech Mahindra, LTIMindtree, Accenture, Cognizant, Capgemini, IBM). See each company’s hiring steps and practice questions on Debugger’s Space.