Second Highest Occurring Element

Given an array of integers, find the element with the second highest frequency. If two elements share the same highest frequency, the one with the smaller value is treated as the highest, apply the same rule for the second highest. If no valid second highest frequency exists, return -1.

Example 1

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

Output: 1

Explanation: Element 2 appears 3 times, so element 2 has the highest frequency. Elements 1 and 3 both appear for 2 times each, and 1 is smaller than 3 so the element 1 is the second highest occurring element.

Example 2

Input: arr = [5, 5, 6, 6]

Output: -1

Explanation:

Elements 5 and 6 both appear 2 times. Only one frequency exists, so no second highest frequency is available.

Brute Force

The goal is to identify the element with the second highest frequency in the array. Since the answer depends on the frequency of every distinct element, the most direct idea is to calculate those frequencies and determine the correct second-ranked element.

Algorithm

If the array is empty, no valid answer exists, so return -1.
Check every distinct element in the array and count how many times it appears in the entire array.
As each frequency becomes available, compare it with the highest and second highest frequencies recorded so far, updating the rankings whenever a better candidate is found.
If two elements have the same frequency, retain the smaller element as the preferred choice.
Continue this process and return the element with the second highest frequency, or -1 if no such element exists.

Dry Run

Brute

Solution

1#include <bits/stdc++.h>
2using namespace std;
3
4class Solution {
5public:
  /*
     * Finds the element with the second highest frequency.
     * Uses direct counting to track the frequency of each element.
 */
  int secondHighestOccurringElement(vector<int> arr) {
      // Empty array has no valid answer
      if (arr.empty()) {
          return -1;
      }
15
      bool hasHighest = false;
      bool hasSecond = false;
      int highestFrequency = 0;
      int secondFrequency = 0;
      int highestElement = 0;
      int secondElement = 0;
22
      // Check each distinct element once
      for (int i = 0; i < arr.size(); i++) {
          bool alreadyCounted = false;
26
          // Look left to avoid counting the same value again
          for (int j = 0; j < i; j++) {
              // Current value was already processed earlier
              if (arr[j] == arr[i]) {
                  alreadyCounted = true;
                  break;
              }
          }
35
          // Skip duplicate values
          if (alreadyCounted) {
              continue;
          }
40
          int currentFrequency = 0;
42
          // Count the frequency of the current distinct value
          for (int j = 0; j < arr.size(); j++) {
              // Same value increases the current frequency
              if (arr[j] == arr[i]) {
                  currentFrequency++;
              }
          }
50
          int currentElement = arr[i];
52
          // First distinct value becomes the highest rank
          if (!hasHighest) {
              highestFrequency = currentFrequency;
              highestElement = currentElement;
              hasHighest = true;
          }
          // Larger frequency creates a new highest rank
          else if (currentFrequency > highestFrequency) {
              secondFrequency = highestFrequency;
              secondElement = highestElement;
              hasSecond = true;
64
              highestFrequency = currentFrequency;
              highestElement = currentElement;
          }
          // Same highest frequency keeps smaller value at highest rank
          else if (currentFrequency == highestFrequency) {
              // Smaller value wins inside the highest rank
              if (currentElement < highestElement) {
                  highestElement = currentElement;
              }
          }
          // Lower frequency can become the second rank
          else {
              // Better second rank is found
              if (!hasSecond ||
                  currentFrequency > secondFrequency ||
                  (currentFrequency == secondFrequency && currentElement < secondElement)) {
                  secondFrequency = currentFrequency;
                  secondElement = currentElement;
                  hasSecond = true;
              }
          }
      }
87
      // No lower frequency level was found
      if (!hasSecond) {
          return -1;
      }
92
      return secondElement;
  }
95};
96
97// Driver code starts
98int main() {
  vector<int> arr = {1, 1, 2, 2, 2, 3, 3, 4};
100
  Solution solution;
  int answer = solution.secondHighestOccurringElement(arr);
103
  cout << answer << "\n";
  return 0;
106}

Complexity Analysis

Time Complexity: O(N²), where N is the number of elements in the array. For every element, the entire array is traversed.

Space Complexity: O(1), as only a fixed number of counters and result values are stored.

Better Approach

The idea is to group equal elements together using sorting so that the frequency of each distinct element can be determined in a single pass. Once the frequency of every group is known, the element with the second highest frequency can be identified applying the tie-breaking rule whenever needed.

Algorithm

If the array is empty, no valid answer exists, so return -1.
The array can be sorted so that all equal elements become part of the same group.
Start processing a group from the position marked by start, and let end move forward until a different value or the end of the array is reached. The distance between start and end gives the frequency of the current element.
Compare the current frequency with the highest and second highest frequencies recorded so far, updating the rankings whenever a better candidate is found. If two elements have the same frequency, retain the smaller element.
Once the current group has been processed, move start to the position of end so the next group can be checked.
Return the element with the second highest frequency, or -1 if no such element exists.

Dry Run

Better

Solution

1#include <bits/stdc++.h>
2using namespace std;
3
4class Solution {
5public:
  // Finds element with second highest frequency after sorting groups
  int secondHighestOccurringElement(vector<int> arr) {
      // Empty array has no valid answer
      if (arr.empty()) {
          return -1;
      }
12
      sort(arr.begin(), arr.end());
14
      bool hasHighest = false;
      bool hasSecond = false;
      int highestFrequency = 0;
      int secondFrequency = 0;
      int highestElement = 0;
      int secondElement = 0;
      int start = 0;
22
      // Process each equal-value group once
      while (start < arr.size()) {
          int end = start;
26
          // Move across the current group
          while (end < arr.size() && arr[end] == arr[start]) {
              end++;
          }
31
          int currentFrequency = end - start;
          int currentElement = arr[start];
34
          // First group becomes the highest rank
          if (!hasHighest) {
              highestFrequency = currentFrequency;
              highestElement = currentElement;
              hasHighest = true;
          }
          // Larger frequency creates a new highest rank
          else if (currentFrequency > highestFrequency) {
              secondFrequency = highestFrequency;
              secondElement = highestElement;
              hasSecond = true;
46
              highestFrequency = currentFrequency;
              highestElement = currentElement;
          }
          // Same highest frequency keeps smaller value at highest rank
          else if (currentFrequency == highestFrequency) {
              // Smaller value wins inside the highest rank
              if (currentElement < highestElement) {
                  highestElement = currentElement;
              }
          }
          // Lower frequency can become the second rank
          else {
              // Better second rank is found
              if (!hasSecond ||
                  currentFrequency > secondFrequency ||
                  (currentFrequency == secondFrequency && currentElement < secondElement)) {
                  secondFrequency = currentFrequency;
                  secondElement = currentElement;
                  hasSecond = true;
              }
          }
68
          start = end;
      }
71
      // No lower frequency level was found
      if (!hasSecond) {
          return -1;
      }
76
      return secondElement;
  }
79};
80
81// Driver code starts
82int main() {
  vector<int> arr = {1, 1, 2, 2, 2, 3, 3, 4};
84
  Solution solution;
  int answer = solution.secondHighestOccurringElement(arr);
87
  cout << answer << "\n";
  return 0;
90}
91

Complexity Analysis

Time Complexity: O(N log(N)), where N is the number of elements in the array. Sorting takes O(N log(N)) time, while the subsequent scan takes O(N) time.

Space Complexity: O(1), as only a fixed number of extra variables are stored.

Optimal Approach

In the previous approach, the array was sorted so that equal elements could be processed as a single group. However, sorting is really not necessary. The only requirement is to know how many times each distinct element appears.

A hash map makes this much simpler by storing the frequency of every element during a single traversal. Once all frequencies have been recorded, the highest and second highest frequency can be identified directly from the stored counts, without modifying the original array.

Algorithm

If the array is empty, no valid answer exists, so return -1.
Count the frequency of every element using a hash map and compare its frequency with the highest and second highest frequencies recorded so far.
Whenever a better candidate is found, update the corresponding rank. If two elements have the same frequency, keep the smaller element as the preferred choice.
Continue until every entry in the frequency map has been examined.
Return the element with the second highest frequency, or -1 if no such element exists.

Dry Run

Optimal

Solution

1#include <bits/stdc++.h>
2using namespace std;
3
4class Solution {
5public:
  // Finds element with second highest frequency using a frequency map
  int secondHighestOccurringElement(vector<int> arr) {
      // Empty array has no valid answer
      if (arr.empty()) {
          return -1;
      }
12
      unordered_map<int, int> frequency;
14
      // Count every value in the array
      for (int value : arr) {
          frequency[value]++;
      }
19
      bool hasHighest = false;
      bool hasSecond = false;
      int highestFrequency = 0;
      int secondFrequency = 0;
      int highestElement = 0;
      int secondElement = 0;
26
      // Choose the highest and second highest frequency ranks
      for (auto entry : frequency) {
          int currentElement = entry.first;
          int currentFrequency = entry.second;
31
          // First map entry becomes the highest rank
          if (!hasHighest) {
              highestFrequency = currentFrequency;
              highestElement = currentElement;
              hasHighest = true;
          }
          // Larger frequency creates a new highest rank
          else if (currentFrequency > highestFrequency) {
              secondFrequency = highestFrequency;
              secondElement = highestElement;
              hasSecond = true;
43
              highestFrequency = currentFrequency;
              highestElement = currentElement;
          }
          // Same highest frequency keeps smaller value at highest rank
          else if (currentFrequency == highestFrequency) {
              // Smaller value wins inside the highest rank
              if (currentElement < highestElement) {
                  highestElement = currentElement;
              }
          }
          // Lower frequency can become the second rank
          else {
              // Better second rank is found
              if (!hasSecond ||
                  currentFrequency > secondFrequency ||
                  (currentFrequency == secondFrequency && currentElement < secondElement)) {
                  secondFrequency = currentFrequency;
                  secondElement = currentElement;
                  hasSecond = true;
              }
          }
      }
66
      // No lower frequency level was found
      if (!hasSecond) {
          return -1;
      }
71
      return secondElement;
  }
74};
75
76// Driver code starts
77int main() {
  vector<int> arr = {1, 1, 2, 2, 2, 3, 3, 4};
79
  Solution solution;
  int answer = solution.secondHighestOccurringElement(arr);
82
  cout << answer << "\n";
  return 0;
85}
86

Complexity Analysis

Time Complexity: O(N) on average, where N is the number of elements in the array. The array is scanned once to build the hash map, and each distinct value is checked once afterward.

Space Complexity: O(K), where K is the number of distinct elements in the array stored in the hash map.

FAQs

Why do we need to keep track of both the highest and second-highest frequencies?

Keeping track of only the highest frequency is not enough because the problem asks for the second highest occurring element. By maintaining both the highest and second-highest frequencies while checking the frequency map, the correct answer can be directly found without sorting the frequencies, making the solution more efficient.

Why do we iterate over the frequency map instead of the original array after counting frequencies?

The frequency map contains only the distinct elements along with their frequencies. By iterating over the map, each element is processed only once, making the solution more efficient than checking the original array again.

Second Highest Occurring Element

Example 1

Example 2

Brute Force

Algorithm

Dry Run

Solution

Complexity Analysis

Better Approach

Algorithm

Dry Run

Solution

Complexity Analysis

Optimal Approach

Algorithm

Dry Run

Solution

Complexity Analysis

FAQs

Read Similar Blogs

Count Distinct Elements

Insert Delete GetRandom O(1)

Hashing in Data Structures: Hash Maps and Collisions