Second highest occurring element
Beginner Problems
Basic Hashing
Easy
- This type of algorithm is quite often used in the world of data analytics and marketing
- Understanding frequency distribution in a dataset is key for identifying trends or patterns
- For example, a streaming service like Netflix or Spotify might use a similar algorithm to identify the second most frequently watched or listened-to genre or artist, to suggest it to their viewers or listeners, enhancing personalization and user experience based on these insights
- It could also be used in text analytics or natural language processing to find the second most frequently used word in a text, which can be instrumental in sentiment analysis, SEO keyword analysis, and more
Given an array of n integers, find the second most frequent element in it. If there are multiple elements that appear a maximum number of times, find the smallest of them. If second most frequent element does not exist return -1.
Examples:
Input: arr = [1, 2, 2, 3, 3, 3]
Output: 2
Explanation: The number 2 appears the second most (2 times) and number 3 appears the most(3 times).
Input: arr = [4, 4, 5, 5, 6, 7]
Output: 6
Explanation: Both 6 and 7 appear second most times, but 6 is smaller.
Input: arr = [10, 9 ,7, 7]
Constraints
- 1 <= n <= 104
- 1 <= arr[i] <= 104
Company Tags
TCS
Cognizant
Accenture
Infosys
Capgemini
Wipro
IBM
HCL
Tech Mahindra
MindTree
Editorial
Intuition:
Imagine you have a bag full of marbles, each with a different number. Your task is to find the marble that appears the second most number of times in the bag. To solve this, we need to keep track of the number of times each marble appears. We should identify the marble with the highest occurrence first and then look for the marble that comes next in terms of frequency. This way, we ensure that we correctly find the second highest occurring marble in the bag.
Approach:
- Create variables to store the highest and second highest frequencies. Also, create variables to store the corresponding elements. Use a visited array of boolean type to mark elements that have already been counted to avoid recounting them.
- Loop through each element in the array. For each element, if it hasn't been counted yet, proceed to count its occurrences. For each element, count how many times it appears in the array. Mark these elements as counted.
- Compare the frequency of the current element with the highest and second highest frequencies. Update the highest and second highest frequencies and their corresponding elements as needed.
- If two elements have the same frequency, choose the smaller one. After processing all elements, return the element with the second highest frequency.
Dry Run:
Solution:
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
/* Function to get the second highest
occurring element in array */
int secondMostFrequentElement(vector<int> &nums) {
// Variable to store the size of array
int n = nums.size();
/* Variable to store maximum frequency
and second Max frequency */
int maxFreq = 0;
int secMaxFreq = 0;
/* Variable to store elements with most
and second most frequency */
int maxEle = -1, secEle = -1;
// Visited array
vector<bool> visited(n, false);
// First loop
for(int i = 0; i < n; i++) {
// Skip second loop if already visited
if(visited[i]) continue;
/* Variable to store frequency
of current element */
int freq = 0;
// Second loop
for(int j = i; j < n; j++) {
if(nums[i] == nums[j]) {
freq++;
visited[j] = true;
}
}
/* Update variables if new element
having highest frequency or second
highest frequency is found */
if(freq > maxFreq) {
secMaxFreq = maxFreq;
maxFreq = freq;
secEle = maxEle;
maxEle = nums[i];
}
else if(freq == maxFreq) {
maxEle = min(maxEle, nums[i]);
}
else if(freq > secMaxFreq) {
secMaxFreq = freq;
secEle = nums[i];
}
else if(freq == secMaxFreq) {
secEle = min(secEle, nums[i]);
}
}
// Return the result
return secEle;
}
};
int main() {
vector<int> nums = {4, 4, 5, 5, 6, 7};
/* Creating an instance of
Solution class */
Solution sol;
/* Function call to get the second
highest occurring element in array */
int ans = sol.secondMostFrequentElement(nums);
cout << "The second highest occurring element in the array is: " << ans;
return 0;
}12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879
import java.util.*;
class Solution {
/* Function to get the second highest
occurring element in array */
public int secondMostFrequentElement(int[] nums) {
// Variable to store the size of array
int n = nums.length;
/* Variable to store maximum frequency
and second Max frequency */
int maxFreq = 0;
int secMaxFreq = 0;
/* Variable to store elements with most
and second most frequency */
int maxEle = -1, secEle = -1;
// Visited array
boolean[] visited = new boolean[n];
// First loop
for(int i = 0; i < n; i++) {
// Skip second loop if already visited
if(visited[i]) continue;
/* Variable to store frequency
of current element */
int freq = 0;
// Second loop
for(int j = i; j < n; j++) {
if(nums[i] == nums[j]) {
freq++;
visited[j] = true;
}
}
/* Update variables if new element
having highest frequency or second
highest frequency is found */
if(freq > maxFreq) {
secMaxFreq = maxFreq;
maxFreq = freq;
secEle = maxEle;
maxEle = nums[i];
}
else if(freq == maxFreq) {
maxEle = Math.min(maxEle, nums[i]);
}
else if(freq > secMaxFreq) {
secMaxFreq = freq;
secEle = nums[i];
}
else if(freq == secMaxFreq) {
secEle = Math.min(secEle, nums[i]);
}
}
// Return the result
return secEle;
}
public static void main(String[] args) {
int[] nums = {4, 4, 5, 5, 6, 7};
/* Creating an instance of
Solution class */
Solution sol = new Solution();
/* Function call to get the second
highest occurring element in array */
int ans = sol.secondMostFrequentElement(nums);
System.out.println("The second highest occurring element in the array is: " + ans);
}
}1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768
class Solution:
"""Function to get the second highest
occurring element in array"""
def secondMostFrequentElement(self, nums):
# Variable to store the size of array
n = len(nums)
"""Variable to store maximum frequency
and second Max frequency"""
maxFreq = 0
secMaxFreq = 0
"""Variable to store elements with most
and second most frequency"""
maxEle = -1
secEle = -1
# Visited array
visited = [False] * n
# First loop
for i in range(n):
# Skip second loop if already visited
if visited[i]:
continue
"""Variable to store frequency
of current element"""
freq = 0
# Second loop
for j in range(i, n):
if nums[i] == nums[j]:
freq += 1
visited[j] = True
"""Update variables if new element
having highest frequency or second
highest frequency is found"""
if freq > maxFreq:
secMaxFreq = maxFreq
maxFreq = freq
secEle = maxEle
maxEle = nums[i]
elif freq == maxFreq:
maxEle = min(maxEle, nums[i])
elif freq > secMaxFreq:
secMaxFreq = freq
secEle = nums[i]
elif freq == secMaxFreq:
secEle = min(secEle, nums[i])
# Return the result
return secEle
if __name__ == "__main__":
nums = [4, 4, 5, 5, 6, 7]
"""Creating an instance of
Solution class"""
sol = Solution()
"""Function call to get the second
highest occurring element in array"""
ans = sol.secondMostFrequentElement(nums)
print(f"The second highest occurring element in the array is: {ans}")123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475
class Solution {
/* Function to get the second highest
occurring element in array */
secondMostFrequentElement(nums) {
// Variable to store the size of array
let n = nums.length;
/* Variable to store maximum frequency
and second Max frequency */
let maxFreq = 0;
let secMaxFreq = 0;
/* Variable to store elements with most
and second most frequency */
let maxEle = -1, secEle = -1;
// Visited array
let visited = new Array(n).fill(false);
// First loop
for (let i = 0; i < n; i++) {
// Skip second loop if already visited
if (visited[i]) continue;
/* Variable to store frequency
of current element */
let freq = 0;
// Second loop
for (let j = i; j < n; j++) {
if (nums[i] === nums[j]) {
freq++;
visited[j] = true;
}
}
/* Update variables if new element
having highest frequency or second
highest frequency is found */
if (freq > maxFreq) {
secMaxFreq = maxFreq;
maxFreq = freq;
secEle = maxEle;
maxEle = nums[i];
}
else if (freq === maxFreq) {
maxEle = Math.min(maxEle, nums[i]);
}
else if (freq > secMaxFreq) {
secMaxFreq = freq;
secEle = nums[i];
}
else if (freq === secMaxFreq) {
secEle = Math.min(secEle, nums[i]);
}
}
// Return the result
return secEle;
}
}
// Example usage
let nums = [4, 4, 5, 5, 6, 7];
/* Creating an instance of
Solution class */
let sol = new Solution();
/* Function call to get the second
highest occurring element in array */
let ans = sol.secondMostFrequentElement(nums);
console.log("The second highest occurring element in the array is: " + ans);Complexity Analysis:
Time Complexity: O(N2) (where N is the size of the array given) – Using two nested loops.
Space Complexity: O(N) – Using a visited array of size N and a couple of variables.
Intuition
An optimal approach to solve this question will be to use a Hashmap, a data structure that stores key-value pairs.
- Key will denote the element in the array.
- Value will store the frequency of the element in the array.
Approach
To solve this problem, follow these steps:
- Initialize variables to keep track of the highest and second-highest frequencies, as well as the corresponding elements.
- Create a hashmap to store the frequency of each element in the array.
- Iterate through the array and update the frequency of each element in the hashmap.
- Iterate through the hashmap to determine the element with the highest frequency and the element with the second highest frequency.
- Return the element with the second highest frequency as the result.
Dry Run:
Solution:
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
/* Function to get the second highest
occurring element in array */
int secondMostFrequentElement(vector<int> &nums) {
// Variable to store the size of array
int n = nums.size();
/* Variable to store maximum frequency
and second maximum frequency */
int maxFreq = 0, secMaxFreq = 0;
/* Variable to store element
with maximum frequency and second
highest frequency */
int maxEle = -1, secEle = -1;
// HashMap
unordered_map<int, int> mpp;
// Iterating on the array
for (int i = 0; i < n; i++) {
// Updating hashmap
mpp[nums[i]]++;
}
// Iterate on the map
for(auto it : mpp) {
int ele = it.first; // Key
int freq = it.second; // Value
/* Update variables if new element
having highest frequency or second
highest frequency is found */
if(freq > maxFreq) {
secMaxFreq = maxFreq;
maxFreq = freq;
secEle = maxEle;
maxEle = ele;
}
else if(freq == maxFreq) {
maxEle = min(maxEle, ele);
}
else if(freq > secMaxFreq) {
secMaxFreq = freq;
secEle = ele;
}
else if(freq == secMaxFreq) {
secEle = min(secEle, ele);
}
}
// Return the result
return secEle;
}
};
int main() {
vector<int> nums = {4, 4, 5, 5, 6, 7};
/* Creating an instance of
Solution class */
Solution sol;
/* Function call to get the second
highest occurring element in array */
int ans = sol.secondMostFrequentElement(nums);
cout << "The second highest occurring element in the array is: " << ans;
return 0;
}123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172
import java.util.*;
class Solution {
/* Function to get the second highest
occurring element in array */
public int secondMostFrequentElement(int[] nums) {
// Variable to store the size of array
int n = nums.length;
/* Variable to store maximum frequency
and second maximum frequency */
int maxFreq = 0, secMaxFreq = 0;
/* Variable to store element
with maximum frequency and second
highest frequency */
int maxEle = -1, secEle = -1;
// HashMap
HashMap<Integer, Integer> mpp = new HashMap<>();
// Iterating on the array
for (int i = 0; i < n; i++) {
// Updating hashmap
mpp.put(nums[i], mpp.getOrDefault(nums[i], 0) + 1);
}
// Iterate on the map
for(Map.Entry<Integer, Integer> it : mpp.entrySet()) {
int ele = it.getKey(); // Key
int freq = it.getValue(); // Value
/* Update variables if new element
having highest frequency or second
highest frequency is found */
if(freq > maxFreq) {
secMaxFreq = maxFreq;
maxFreq = freq;
secEle = maxEle;
maxEle = ele;
}
else if(freq == maxFreq) {
maxEle = Math.min(maxEle, ele);
}
else if(freq > secMaxFreq) {
secMaxFreq = freq;
secEle = ele;
}
else if(freq == secMaxFreq) {
secEle = Math.min(secEle, ele);
}
}
// Return the result
return secEle;
}
public static void main(String[] args) {
int[] nums = {4, 4, 5, 5, 6, 7};
/* Creating an instance of
Solution class */
Solution sol = new Solution();
/* Function call to get the second
highest occurring element in array */
int ans = sol.secondMostFrequentElement(nums);
System.out.println("The second highest occurring element in the array is: " + ans);
}
}123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263
from collections import defaultdict
class Solution:
# Function to get the second highest
# occurring element in array
def secondMostFrequentElement(self, nums):
# Variable to store the size of array
n = len(nums)
# Variable to store maximum frequency
# and second maximum frequency
maxFreq = 0
secMaxFreq = 0
# Variable to store element
# with maximum frequency and second
# highest frequency
maxEle = -1
secEle = -1
# HashMap
mpp = defaultdict(int)
# Iterating on the array
for num in nums:
# Updating hashmap
mpp[num] += 1
# Iterate on the map
for ele, freq in mpp.items():
# Update variables if new element
# having highest frequency or second
# highest frequency is found
if freq > maxFreq:
secMaxFreq = maxFreq
maxFreq = freq
secEle = maxEle
maxEle = ele
elif freq == maxFreq:
maxEle = min(maxEle, ele)
elif freq > secMaxFreq:
secMaxFreq = freq
secEle = ele
elif freq == secMaxFreq:
secEle = min(secEle, ele)
# Return the result
return secEle
# Test the function
if __name__ == "__main__":
nums = [4, 4, 5, 5, 6, 7]
# Creating an instance of
# Solution class
sol = Solution()
# Function call to get the second
# highest occurring element in array
ans = sol.secondMostFrequentElement(nums)
print(f"The second highest occurring element in the array is: {ans}")123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566
class Solution {
/* Function to get the second highest
occurring element in array */
secondMostFrequentElement(nums) {
// Variable to store the size of array
let n = nums.length;
/* Variable to store maximum frequency
and second maximum frequency */
let maxFreq = 0, secMaxFreq = 0;
/* Variable to store element
with maximum frequency and second
highest frequency */
let maxEle = -1, secEle = -1;
// HashMap
let mpp = new Map();
// Iterating on the array
for (let i = 0; i < n; i++) {
// Updating hashmap
mpp.set(nums[i], (mpp.get(nums[i]) || 0) + 1);
}
// Iterate on the map
for (let [ele, freq] of mpp) {
/* Update variables if new element
having highest frequency or second
highest frequency is found */
if (freq > maxFreq) {
secMaxFreq = maxFreq;
maxFreq = freq;
secEle = maxEle;
maxEle = ele;
}
else if (freq == maxFreq) {
maxEle = Math.min(maxEle, ele);
}
else if (freq > secMaxFreq) {
secMaxFreq = freq;
secEle = ele;
}
else if (freq == secMaxFreq) {
secEle = Math.min(secEle, ele);
}
}
// Return the result
return secEle;
}
}
// Test the function
let nums = [4, 4, 5, 5, 6, 7];
/* Creating an instance of
Solution class */
let sol = new Solution();
/* Function call to get the second
highest occurring element in array */
let ans = sol.secondMostFrequentElement(nums);
console.log("The second highest occurring element in the array is: " + ans);Complexity Analysis:
Time Complexity: O(N) (where N is the size of the array given) –
- Using a single loop, performing insertion, and updation operations on HashMap takes O(1) TC resulting in O(N) TC.
- Iterating on HashMap will take O(N) in the worst-case
Space Complexity: O(N) – In the worst-case scenario, the HashMap will store all the elements in the array when array elements are unique.
Notes
Code
✅ Testcase
Input: {'nums': '[1, 2, 2, 3, 3, 3]'}
Expected:
2
2
Actual: -
Time: -
sec
Status: Waiting
Input: {'nums': '[4, 4, 5, 5, 6, 7]'}
Expected:
6
6
Actual: -
Time: -
sec
Status: Waiting
Input: {'nums': '[10, 9 ,7, 7]'}
Expected:
9
9
Actual: -
Time: -
sec
Status: Waiting