Problem Statement

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

Example 1:

Input: arr = [1, 2, 2, 3, 3, 3]
Output: 2

Explanation: The number 2 appears the second most (2 times) and the number 3 appears the most (3 times).

Example 2:

Input: arr = [4, 4, 5, 5, 6, 7]
Output: 6

Explanation: Both 6 and 7 appear second most times (1 time), but 6 is smaller.

Example 3:

Input: arr = [10, 9, 7, 7]
Output: 9

Different Approaches

1️⃣ Brute Force Approach

Approach:

• Initialization:
  • n: Size of the array.
  • maxFreq and secMaxFreq: Start at 0 (no frequency counted yet).
  • maxEle and secEle: Initially set to -1 (or any invalid value to indicate they haven’t been assigned).
  • visited: A Boolean vector of size n initialized to false to mark whether an element's frequency has already been computed.
• Outer Loop (for (int i = 0; i < n; i++)):
  • Skip Already Visited:
    If visited[i] is true, it means this element has already been counted, so we continue to the next iteration.
  • Counting Frequency:
    Initialize freq to 0 for the current element nums[i].
  • Inner Loop (for (int j = i; j < n; j++)):
    Compare nums[i] with every element from index i onward:
    • If nums[i] equals nums[j], increment freq and mark visited[j] as true to avoid recounting later.
• Updating Maximum and Second Maximum Frequencies:
  • If freq > maxFreq:
    • Update secMaxFreq to the previous maxFreq and secEle to the previous maxEle.
    • Set maxFreq to freq and maxEle to nums[i].
  • Else if freq == maxFreq:
    • Update maxEle with the smaller of the current maxEle and nums[i] (tie-breaker for the most frequent element).
  • Else if freq > secMaxFreq:
    • Update secMaxFreq to freq and secEle to nums[i].
  • Else if freq == secMaxFreq:
    • Update secEle with the smaller of the current secEle and nums[i] (tie-breaker for the second most frequent element).
• Return Result:
  • After all elements are processed, the function returns secEle, which holds the second highest occurring element.

Code:

#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) {
        
        // Step 1: Get the size of the array
        int n = nums.size();
        
        // Step 2: Initialize frequency trackers
        int maxFreq = 0;      // Highest frequency so far
        int secMaxFreq = 0;   // Second highest frequency so far
        
        // Step 3: Variables to store elements with highest and second highest frequencies
        int maxEle = -1;      // Element with highest frequency
        int secEle = -1;      // Element with second highest frequency
        
        // Step 4: Boolean array to mark elements that have already been counted
        vector<bool> visited(n, false);
        
        // Step 5: Iterate through each element in the array
        for (int i = 0; i < n; i++) {
            // If this element was already counted in a previous pass, skip it
            if (visited[i]) continue;
            
            // Step 6: Count the frequency of nums[i]
            int freq = 0;  // Frequency counter for current element

            // Step 7: Start from current index and count occurrences
            for (int j = i; j < n; j++) {
                if (nums[i] == nums[j]) {
                    freq++;            // Count this occurrence
                    visited[j] = true; // Mark this index as visited
                }
            }
            
            // Step 8: Update max and second max frequencies and their elements

            // Case 1: New max frequency found
            if (freq > maxFreq) {
                secMaxFreq = maxFreq;  // Update second max freq before overwriting maxFreq
                maxFreq = freq;        // Update max frequency
                secEle = maxEle;       // Update second most frequent element
                maxEle = nums[i];      // Update most frequent element
            } 
            // Case 2: Tie for max frequency — pick the smaller value
            else if (freq == maxFreq) {
                maxEle = min(maxEle, nums[i]);
            } 
            // Case 3: New second max frequency
            else if (freq > secMaxFreq) {
                secMaxFreq = freq;     // Update second max frequency
                secEle = nums[i];      // Update second most frequent element
            }
            // Case 4: Tie for second max — pick the smaller value
            else if (freq == secMaxFreq) {
                secEle = min(secEle, nums[i]);
            }
        }
        
        // Step 9: Return the second most frequent element
        return secEle;
    }
};

int main() {
    // Step 10: Define an example array
    vector<int> nums = {4, 4, 5, 5, 6, 7};
    
    // Step 11: Create an object of Solution class
    Solution sol; 
    
    // Step 12: Call the function and store the result
    int ans = sol.secondMostFrequentElement(nums);
    
    // Step 13: Print the result
    cout << "The second highest occurring element in the array is: " << ans;
    
    return 0;
}

Complexity Analysis:

• Time Complexity:O(N^2), where N is the size of the array.
  • Using two nested loops.
• Space Complexity:O(N)
  • We are using visited array of size N.

2️⃣ Hashing (unordered_map)

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:

1. Initialize variables to keep track of the highest and second-highest frequencies, as well as the corresponding elements.
2. Create a hashmap to store the frequency of each element in the array.
3. Iterate through the array and update the frequency of each element in the hashmap.
4. Iterate through the hashmap to determine the element with the highest frequency and the element with the second highest frequency.
5. Return the element with the second highest frequency as the result.

Code:

#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) {
        
        // Step 1: Get the size of the array
        int n = nums.size();
        
        // Step 2: Initialize frequency trackers
        int maxFreq = 0;       // Maximum frequency
        int secMaxFreq = 0;    // Second maximum frequency
        
        // Step 3: Initialize element trackers
        int maxEle = -1;       // Element with maximum frequency
        int secEle = -1;       // Element with second maximum frequency
        
        // Step 4: Create a hashmap to count frequencies of elements
        unordered_map<int, int> mpp;
        
        // Step 5: Iterate over the array and populate the frequency map
        for (int i = 0; i < n; i++) {
            mpp[nums[i]]++;  // Increment frequency count for nums[i]
        }
            
        // Step 6: Iterate over the frequency map to determine max and second max
        for (auto it : mpp) {
            int ele = it.first;   // Current element
            int freq = it.second; // Its frequency
            
            // Case 1: New max frequency found
            if (freq > maxFreq) {
                secMaxFreq = maxFreq; // Move current max to second max
                maxFreq = freq;       // Update max frequency
                secEle = maxEle;      // Move max element to second element
                maxEle = ele;         // Update max element
            }
            // Case 2: Tie with current max frequency (pick smaller element)
            else if (freq == maxFreq) {
                maxEle = min(maxEle, ele);
            }
            // Case 3: New second max frequency found
            else if (freq > secMaxFreq) {
                secMaxFreq = freq;  // Update second max frequency
                secEle = ele;       // Update second element
            }
            // Case 4: Tie with second max frequency (pick smaller element)
            else if (freq == secMaxFreq) {
                secEle = min(secEle, ele);
            }
        }
        
        // Step 7: Return the second most frequent element
        return secEle;
    }
};

int main() {
    // Step 8: Define the input array
    vector<int> nums = {4, 4, 5, 5, 6, 7};
    
    // Step 9: Create an instance of the Solution class
    Solution sol; 
    
    // Step 10: Call the function to get the second most frequent element
    int ans = sol.secondMostFrequentElement(nums);
    
    // Step 11: Print the result
    cout << "The second highest occurring element in the array is: " << ans;
    
    return 0;
}

Complexity Analysis:

• Time Complexity:O(N), where N is the size of the array.
  • O(N), loop for filling the map.
  • O(k), for iterating over the map (where k is the number of unique elements).
    • In worst case, k = n (If all the elements are unique).
• Space Complexity:O(k), where k is the number of unique elements.
  • In worst case, k = n (If all elements are unique).