Find the element with the second-highest frequency using a visited array and two leader slots, el1 and el2. Read the code, then watch it run step by step on your own input.
01 The problem
Given an array of N non-negative integers, print the element that occurs the second most times. If no element takes second place, print -1.
For [1, 2, 2, 3, 3, 3], the frequencies are 1 → 1, 2 → 2 and 3 → 3. Value 3 occurs most, so the answer is 2.
Type an array to see what the program prints and how often each value occurs.
02 The code
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 with 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 el1Freq=0; int el2Freq=0; int el1=-1; int el2=-1;
for (int i = 0; i < n ; i++) {
int count = 0;
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);
}
}03 How it works
Find max, size visited[]
The first loop reads the input and tracks max, so visited can have one slot per possible value.
Fresh count for every i
int count = 0; sits inside the outer loop, so every index starts counting from zero.
Count each value once
Only a value's first appearance runs the inner j loop. A repeat keeps count = 0, so it doesn't change the leaders.
Push the old leader down
If count > el1Freq, the old el1 moves into el2 and arr[i] becomes the new el1.
Or take second place
If the count doesn't beat el1Freq but beats el2Freq, arr[i] becomes the new el2.
Ties and -1
The last two branches prefer the smaller value on a tie. el2 starts at -1, which is printed if nothing takes second place.
04 Live tracer
This runs exactly the code above, one step at a time.
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) |
|---|
05 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 |
06 Quick revision
visited[] avoids recounting
The inner loop runs once per distinct value, not once per index.
count resets every iteration
Declaring count inside the outer loop means a repeat has count = 0 and leaves the leaders alone.
Two slots, one pass
You don't need to sort frequencies. el1 and el2 are updated as each value is counted.
Demote before replacing
When a new leader appears, copy el1 into el2 first, then overwrite el1.
visited costs O(max) space
It grows with the largest value, not with N, and needs non-negative input.
-1 is the "none" answer
If every value occurs equally often, nothing takes second place and -1 is printed.
Comments
Post a Comment