Find the element with the second-highest frequency using a visited array and two leader slots, el1 and el2. Watch it run step by step, see why it prints the wrong value for some inputs, and get a version that works.
01 The problem
Given an array of N non-negative integers, print the element whose frequency is the second highest. If several elements share that frequency, print the smallest. If there is no second frequency (every value appears equally often), print -1.
For [1, 2, 2, 3, 3, 3], the frequencies are 1 → 1, 2 → 2 and 3 → 3. The highest is 3 (value 3), so the answer is 2.
Type an array to compare the code below with the fixed version and the expected answer.
02 The brute-force code
The idea: walk the array with i. The first time a value shows up, mark it in visited and count its occurrences with an inner j loop. Then compare that count against the two leaders: el1 (highest frequency) and el2 (second highest).
import java.util.Scanner;
public class SecondHighestOccuringElementBruteForce {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int[] arr=new int[n];
int max = Integer.MIN_VALUE;
for(int i=0;i<n;i++) {
arr[i] = sc.nextInt();
max = Math.max(max, arr[i]);
}
int[] visited=new int[max+1];
int count = 0;
int el1Freq=0; int el2Freq=0; int el1=-1; int el2=-1;
for (int i = 0; i < n ; i++) {
if(visited[arr[i]]==0){
visited[arr[i]]=1;
for (int j = 0; j < n; j++) {
if (arr[j] == arr[i]) {
count++;
}
}
}
if(count > el1Freq){
el2=el1;
el2Freq=el1Freq;
el1=arr[i];
el1Freq=count;
}
else if(count > el2Freq ){
el2=arr[i];
el2Freq=count;
} else if (count == el1Freq && arr[i]<el1) {
el1=arr[i];
} else if (count == el2Freq && arr[i]<el2) {
el2=arr[i];
}
}
System.out.println(el2);
}
}visited[] skips recounting
Each distinct value runs the inner j loop only once, on its first appearance.
Two leader slots
A count bigger than el1Freq pushes the old leader down into el2. A count between the two replaces el2.
Ties prefer the smaller value
The last two branches keep the smaller element when a count equals a leader's frequency.
-1 means "no second"
el2 starts at -1, which is printed if nothing ever takes second place.
03 Live tracer
This runs exactly the code above, one step at a time. Switch versions to see what each fix changes.
i, teal pointer = j. The beam turns teal on a match and rose on a mismatch. The row below is visited[]. Click any table row to jump to it.| # | i | j | arr[i] | arr[j] | Action | count | el1 (freq) | el2 (freq) |
|---|
04 Why it prints the wrong answer
On [1 2 2 3 3 3] the code prints 3 instead of 2, which is the most frequent value, not the second. Three logic bugs work together, and there is one input limit. Each Trace it button loads the tracer at the step where that bug happens.
count is never reset
int count = 0; sits outside the loop, so each new value's count is added to the total from earlier values. In [5 5 2], value 2 appears once, but count becomes 3 (2 + 1), so 2 wrongly takes first place.
Repeats are re-ranked with a stale count
The el1/el2 comparison sits outside the if(visited…) block, so it also runs for values already seen, using a count left over from earlier. That is how one value can end up in both slots. In [1 2 2 3 3 3], 2 fills both slots, then 3 does the same, and 3 gets printed.
A tie for first lands in second place
If count == el1Freq, the check count > el2Freq is usually true too, and it comes first. So a value that ties for first is put in el2, and the count == el1Freq branch below it almost never runs. With bugs 1–2 fixed, [1 1 2 2] prints 2, but both values have the same frequency, so the answer is -1.
Limit: negatives and huge values
visited has size max + 1. A negative value throws ArrayIndexOutOfBoundsException at visited[arr[i]], and a value like 10⁹ needs about 4 GB. This isn't a logic bug, but it limits which inputs the approach can handle.
05 The fixed version
Same approach, same variable names. Only the three highlighted parts change. I checked it against the expected answer on 600 random arrays with no mismatches.
import java.util.Scanner;
public class SecondHighestOccuringElementBruteForce {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int[] arr=new int[n];
int max = Integer.MIN_VALUE;
for(int i=0;i<n;i++) {
arr[i] = sc.nextInt();
max = Math.max(max, arr[i]);
}
int[] visited=new int[max+1];
int el1Freq=0; int el2Freq=0; int el1=-1; int el2=-1;
for (int i = 0; i < n ; i++) {
if(visited[arr[i]]==1) continue; // fix 2: rank each value once
visited[arr[i]]=1;
int count = 0; // fix 1: fresh count per value
for (int j = 0; j < n; j++) {
if (arr[j] == arr[i]) {
count++;
}
}
if(count > el1Freq){
el2=el1;
el2Freq=el1Freq;
el1=arr[i];
el1Freq=count;
} else if (count == el1Freq) { // fix 3: tie for 1st checked
if (arr[i]<el1) el1=arr[i]; // before 2nd place
} else if(count > el2Freq){
el2=arr[i];
el2Freq=count;
} else if (count == el2Freq && arr[i]<el2) {
el2=arr[i];
}
}
System.out.println(el2);
}
}[1 2 2 3 3 3]. Repeated values now skip straight past the ranking, and the program prints 2.
06 Complexity
Let D be the number of distinct values. Because of visited, the inner loop runs only D times, once per distinct value, and each run does N comparisons.
| Step | Cost |
|---|---|
| Read input, find max | O(N) |
| Allocate visited[max + 1] | O(max) |
| Count each distinct value | O(D × N) |
| Total time | O(D × N + max), worst case O(N² + max) when all values are distinct |
| Extra space | O(max), not O(1): visited grows with the largest value |
You can check this in the tracer: [4 4 4 1 1 2] has D = 3 and N = 6, so it makes exactly 3 × 6 = 18 comparisons. For large inputs, a HashMap<Integer, Integer> of frequencies does the same job in O(N) average time and O(D) space, and it handles negative values.
| Approach | Time | Extra space | Negatives / huge values |
|---|---|---|---|
| Brute force + visited | O(D × N + max) | O(max) | No |
| HashMap of frequencies | O(N) avg | O(D) | Yes |
07 Quick revision
Reset per-item counters inside the loop
A counter declared outside the loop keeps adding up across iterations.
Rank each value exactly once
Put the el1/el2 update inside the first-visit block, or continue on repeats.
Check ties before "greater than second"
Branch order matters: count == el1Freq must come before count > el2Freq.
Watch for el1 == el2
If both slots hold the same value, something is ranking a value twice.
visited costs O(max) space
It grows with the largest value, not with N, and can't handle negative values.
Test the tricky inputs
Try all equal [7 7], a tie for first [1 1 2 2], and the mode appearing last [1 2 2 3 3 3].
Comments
Post a Comment