Find the element with the second-highest frequency by counting every value once in a hash[] array, then scanning it with two leader slots. 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. Rank values by frequency. On a tie, the value that appears first in the array ranks higher. If there is only one distinct value, print -1.
For [1, 2, 2, 3, 3, 3], the frequencies are 1 → 1, 2 → 2 and 3 → 3. Value 3 is first, so the answer is 2.
Type an array to see what the code prints and how often each value occurs.
02 The hashing code
This is a faster alternative to the brute-force version. It avoids recounting each value with an inner loop: one pass fills hash[v] with the frequency of every value v. A second loop over arr reads each element's frequency from hash and keeps two leaders, el1 (highest frequency) and el2 (second highest).
import java.util.Scanner;
public class SecondMostOccurringElementOfTheArrayByHashing {
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 hash[] = new int[max + 1];
for (int i = 0; i < n; i++) {
hash[arr[i]]++;
}
int el1Freq=0; int el2Freq=0; int el1=-1; int el2=-1;
for (int i = 0; i < n ; i++) {
int count = hash[arr[i]];
if (count > el1Freq) {
el2 = el1;
el2Freq = el1Freq;
el1 = arr[i];
el1Freq = hash[arr[i]];
} else if (count > el2Freq && arr[i] != el1) {
el2 = arr[i];
el2Freq = hash[arr[i]];
}
}
System.out.println(el2);
}
}Count in one pass
hash[arr[i]]++ gives every frequency in O(N), with no inner loop.
Loop bound matches the array
The scan runs i < n and reads arr[i], so it can never go out of bounds.
Demote, then replace
A count bigger than el1Freq pushes the old el1 down into el2 first.
arr[i] != el1 blocks duplicates
Later copies of the leader can't sneak into second place. Strict > keeps repeats of el2 out too.
03 Live tracer
This runs the code above one step at a time.
arr while the teal pointer bumps hash[arr[i]]. Then the scan walks arr again and reads each frequency. The violet cell is el1 and the rose cell is el2. Click any table row to jump to it.| # | Phase | i | Action | el1 (freq) | el2 (freq) |
|---|
04 Complexity
| Step | Cost |
|---|---|
| Read input, find max | O(N) |
| Fill hash | O(N) |
| Allocate hash[max + 1] | O(max) |
| Scan arr for the two leaders | O(N) |
| Total time | O(N + max) |
| Extra space | O(max), not O(1): hash grows with the largest value |
The loops run one after another, so their costs add. Because hash has max + 1 slots, this approach needs non-negative values that aren't too large (10⁹ would need about 4 GB). Compare this with the brute-force version, which runs an inner loop for every distinct value: O(D × N + max), or O(N²) in the worst case.
| Approach | Time | Extra space | Negatives / huge values |
|---|---|---|---|
| Brute force + visited | O(D × N + max) | O(max) | No |
| Array hashing (this post) | O(N + max) | O(max) | No |
| HashMap of frequencies | O(N) avg | O(D) | Yes |
05 Quick revision
Count first, rank second
Fill hash in one pass, then pick the two leaders in a second pass.
Loop bound matches the array
The scan uses i < n because it reads arr[i].
Guard the second slot
arr[i] != el1 stops a repeat of the leader from becoming second.
Ties go to the first appearance
Strict > never replaces an equal count, so the value seen first keeps its place.
O(N + max) time, O(max) space
This is faster than brute force, but memory grows with the largest value.
Test the edge inputs
Try [5 5 2], [1 1 1 1] (one value) and [2 2 1 1 3] (a tie).
Comments
Post a Comment