Find the second largest distinct element in an array in a single pass, with no sorting and no extra array. Watch largest and secondLargest update step by step on your own input.
01 The problem
Given an array of N integers, print the second largest distinct value. Duplicates of the largest don't count. If there is no second distinct value, print -1.
For [10, 20, 20, 15, 5], the largest is 20. The next distinct value below it is 15. For [7, 7, 7] there is no second value, so the answer is -1.
Type an array to see what the program prints. Negative numbers work too.
02 The code
Keep two variables while walking the array once: largest and secondLargest. A boolean, isSLargestFound, records whether a real second value was ever seen.
package Day9;
import java.util.Scanner;
public class SecondMaxElement {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n=scanner.nextInt();
int[] arr=new int[n];
for (int i = 0; i < arr.length; i++) {
arr[i]= scanner.nextInt();
}
int largest=Integer.MIN_VALUE;
int secondLargest=Integer.MIN_VALUE;
boolean isSLargestFound=false;
for (int i = 0; i < arr.length; i++) {
int current=arr[i];
if (current > largest) {
if (largest != Integer.MIN_VALUE) {
secondLargest = largest;
isSLargestFound = true;
}
largest = current;
} else if (current < largest && current > secondLargest) {
secondLargest = current;
isSLargestFound = true;
}
}
if (isSLargestFound) {
System.out.println(secondLargest);
} else {
System.out.println(-1);
}
}
}03 How it works
Start below everything
Both trackers start at Integer.MIN_VALUE, so the first element always becomes largest.
New maximum: demote, then replace
If current > largest, the old largest drops to secondLargest, and current takes the top spot.
In between: update second
If current is below largest but above secondLargest, it becomes the new second.
Duplicates are ignored
A value equal to largest fails both checks, so [20, 20] never makes 20 the second largest.
Guard on the first demotion
largest != Integer.MIN_VALUE stops the starting placeholder from being treated as a real second value.
The flag decides the output
If isSLargestFound is still false, every value was equal (or there was one value), so it prints -1.
04 Live tracer
This runs the code above one element at a time.
i. The violet cell is the current largest and the rose cell is secondLargest. Click any table row to jump to it.| # | i | current | Branch | largest | secondLargest | found |
|---|
05 Three ways to solve it
The single-pass version is the one interviewers look for, but it helps to know where it sits next to the other common approaches.
| Approach | Idea | Time | Extra space |
|---|---|---|---|
| Sort | Sort the array, then walk back from the end to the first value smaller than the last | O(N log N) | O(1) to O(N) |
| Two passes | Pass 1 finds the largest, pass 2 finds the biggest value below it | O(2N) = O(N) | O(1) |
| One pass (this post) | Track largest and secondLargest together | O(N) | O(1) |
One limit to know: the code uses Integer.MIN_VALUE as "not set yet", so an input that actually contains −2,147,483,648 is treated as empty. For example, [-2147483648, 5] prints -1. Also, if the real second largest is -1, the output looks the same as "not found". The flag tells them apart inside the program.
06 Quick revision
Distinct means distinct
Second largest of [20, 20, 15] is 15, not 20.
Demote before you replace
Copy largest into secondLargest first, then overwrite largest.
Strict comparisons
> and <, never >=, so equal values are skipped.
One pass, two variables
O(N) time and O(1) space. No sorting, no extra array.
Use a flag for "not found"
isSLargestFound separates "no second value" from a real answer.
Test the edge inputs
Try one element, all equal, the max first [7 3], the max last [3 7], and negatives.
Comments
Post a Comment