Highest occurring element in an array

Intuition:

A brute-force way to solve this problem will be to use two loops:

First loop to iterate on the array, selecting an element.
Second loop to traverse the remaining array to find the occurrences of the selected element in the first loop.

Maintain a visited array to mark the elements to keep track of duplicate elements that were already taken into account.

Approach:

Initialize a visited array of boolean type having size n, where n is the size of the array with all elements set to false. Also, declare the following variables :
- maxFreq - to store the frequency of the highest occurring element.
- maxEle - to store the highest occurring element in the array.
In the first loop, start iterating on the elements of the array selecting one element at a time.
In the second loop, iterate on the rest portion of the array and count the frequency (number of occurrences) of the selected element. And every time, the same element is found, mark the corresponding index in the visited array as true.
If the frequency of the current element is found greater than maxFreq, update maxFreq and maxEle with the new frequency and new element respectively.
If the frequency of the current element is the same as maxFreq, store the smaller of maxEle and the current element in maxEle.
Before starting the second loop, check if the element is marked as unvisited. Skip the element if it is visited because its frequency has already been taken into consideration.

Dry Run:

Solution:

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    /* Function to get the highest 
    occurring element in array nums */
    int mostFrequentElement(vector<int> &nums) {
        
        // Variable to store the size of array
        int n = nums.size();
        
        // Variable to store maximum frequency
        int maxFreq = 0; 
        
        /* Variable to store element 
        with maximum frequency */
        int maxEle;
        
        // 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 is found */
            if(freq > maxFreq) {
                maxFreq = freq;
                maxEle = nums[i];
            } else if(freq == maxFreq) {
                maxEle = min(maxEle, nums[i]);
            }
        }
        
        // Return the result
        return maxEle;
    }
};

int main() {
    vector<int> nums = {4, 4, 5, 5, 6};
    
    /* Creating an instance of 
    Solution class */
    Solution sol; 
    
    /* Function call to get the
    highest occurring element in array nums */
    int ans = sol.mostFrequentElement(nums);
    
    cout << "The highest occurring element in the array is: " << ans;
    
    return 0;
}
import java.util.*;

class Solution {
    /* Function to get the highest 
    occurring element in array nums */
    public int mostFrequentElement(int[] nums) {
        
        // Variable to store the size of array
        int n = nums.length;
        
        // Variable to store maximum frequency
        int maxFreq = 0; 
        
        /* Variable to store element 
        with maximum frequency */
        int maxEle = 0;
        
        // 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 is found */
            if (freq > maxFreq) {
                maxFreq = freq;
                maxEle = nums[i];
            } else if (freq == maxFreq) {
                maxEle = Math.min(maxEle, nums[i]);
            }
        }
        
        // Return the result
        return maxEle;
    }
    
    public static void main(String[] args) {
        int[] nums = {4, 4, 5, 5, 6};
        
        /* Creating an instance of 
        Solution class */
        Solution sol = new Solution(); 
        
        /* Function call to get the
        highest occurring element in array nums */
        int ans = sol.mostFrequentElement(nums);
        
        System.out.println("The highest occurring element in the array is: " + ans);
    }
}
class Solution:
    # Function to get the highest 
    # occurring element in array nums
    def mostFrequentElement(self, nums):
        
        # Variable to store the size of array
        n = len(nums)
        
        # Variable to store maximum frequency
        maxFreq = 0 
        
        # Variable to store element 
        # with maximum frequency
        maxEle = 0
        
        # 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 is found
            if freq > maxFreq:
                maxFreq = freq
                maxEle = nums[i]
            elif freq == maxFreq:
                maxEle = min(maxEle, nums[i])
        
        # Return the result
        return maxEle

if __name__ == "__main__":
    nums = [4, 4, 5, 5, 6]
    
    # Creating an instance of Solution class
    sol = Solution()
    
    # Function call to get the
    # highest occurring element in array nums
    ans = sol.mostFrequentElement(nums)
    
    print("The highest occurring element in the array is:", ans)
class Solution {
    /* Function to get the highest 
    occurring element in array nums */
    mostFrequentElement(nums) {
        
        // Variable to store the size of array
        let n = nums.length;
        
        // Variable to store maximum frequency
        let maxFreq = 0; 
        
        /* Variable to store element 
        with maximum frequency */
        let maxEle = 0;
        
        // 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 is found */
            if (freq > maxFreq) {
                maxFreq = freq;
                maxEle = nums[i];
            } else if (freq == maxFreq) {
                maxEle = Math.min(maxEle, nums[i]);
            }
        }
        
        // Return the result
        return maxEle;
    }
}

// Input array
let nums = [4, 4, 5, 5, 6];

// Creating an instance of Solution class
let sol = new Solution();

/* Function call to get the
highest occurring element in array nums */
let ans = sol.mostFrequentElement(nums);

console.log("The highest occurring element in the array is: " + ans);

Complexity Analysis:

Time Complexity: O(N²) (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:

Take a HashMap to store the int key-value pairs.
Start iterating on the array.
- If the current element is not present in the HashMap, insert it with a frequency of 1.
- Else, increment the frequency of current element in the HashMap.
Once the iterations are over, all the elements with their frequencies will be stored in the HashMap. Iterate on the HashMap to find the element with the highest frequency.

Dry Run:

Solution:

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    /* Function to get the highest 
    occuring element in array n */
    int mostFrequentElement(vector<int> &nums) {
        
        // Variable to store the size of array
        int n = nums.size();
        
        // Variable to store maximum frequency
        int maxFreq = 0; 
        
        /* Variable to store element 
        with maximum frequency */
        int maxEle;
        
        // 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
            
            if(freq > maxFreq) {
                maxFreq = freq;
                maxEle = ele;
            }
            else if(freq == maxFreq) {
                maxEle = min(maxEle, ele);
            }
        }
        
        // Return the result
        return maxEle;
    }
};

int main() {
    vector<int> nums = {4, 4, 5, 5, 6};
    
    /* Creating an instance of 
    Solution class */
    Solution sol; 
    
    /* Function call to get the
    highest occuring element in array n */
    int ans = sol.mostFrequentElement(nums);
    
    cout << "The highest occurring element in the array is: " << ans;
    
    return 0;
}
import java.util.*;

class Solution {
    /* Function to get the highest
    occurring element in array n */
    public int mostFrequentElement(int[] nums) {
        
        // Variable to store the size of array
        int n = nums.length;
        
        // Variable to store maximum frequency
        int maxFreq = 0; 
        
        /* Variable to store element
        with maximum frequency */
        int maxEle = 0;
        
        // HashMap
        Map<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
            
            if (freq > maxFreq) {
                maxFreq = freq;
                maxEle = ele;
            } else if (freq == maxFreq) {
                maxEle = Math.min(maxEle, ele);
            }
        }
        
        // Return the result
        return maxEle;
    }

    public static void main(String[] args) {
        int[] nums = {4, 4, 5, 5, 6};
        
        /* Creating an instance of
        Solution class */
        Solution sol = new Solution();
        
        /* Function call to get the
        highest occurring element in array n */
        int ans = sol.mostFrequentElement(nums);
        
        System.out.println("The highest occurring element in the array is: " + ans);
    }
}
class Solution:
    # Function to get the highest
    # occurring element in array n
    def mostFrequentElement(self, nums):
        
        # Variable to store the size of array
        n = len(nums)
        
        # Variable to store maximum frequency
        maxFreq = 0
        
        # Variable to store element
        # with maximum frequency
        maxEle = 0
        
        # HashMap
        mpp = {}
        
        # Iterating on the array
        for num in nums:
            # Updating hashmap
            if num in mpp:
                mpp[num] += 1
            else:
                mpp[num] = 1
        
        # Iterate on the map
        for ele, freq in mpp.items():
            if freq > maxFreq:
                maxFreq = freq
                maxEle = ele
            elif freq == maxFreq:
                maxEle = min(maxEle, ele)
        
        # Return the result
        return maxEle

# Input array
nums = [4, 4, 5, 5, 6]

# Creating an instance of Solution class
sol = Solution()

# Function call to get the highest
# occurring element in array n
ans = sol.mostFrequentElement(nums)

print(f"The highest occurring element in the array is: {ans}")
class Solution {
    /* Function to get the highest
    occurring element in array n */
    mostFrequentElement(nums) {
        
        // Variable to store the size of array
        let n = nums.length;
        
        // Variable to store maximum frequency
        let maxFreq = 0;
        
        // Variable to store element
        // with maximum frequency
        let maxEle = 0;
        
        // 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) {
            if (freq > maxFreq) {
                maxFreq = freq;
                maxEle = ele;
            } else if (freq === maxFreq) {
                maxEle = Math.min(maxEle, ele);
            }
        }
        
        // Return the result
        return maxEle;
    }
}

// Input array
let nums = [4, 4, 5, 5, 6];

/* Creating an instance of
Solution class */
let sol = new Solution();

/* Function call to get the
highest occurring element in array n */
let ans = sol.mostFrequentElement(nums);

console.log(`The 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, updation opertion 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.

Problem List

Highest occurring element in an array

Examples:

Constraints

Company Tags

Editorial

Intuition:

Approach:

Dry Run:

Solution:

Complexity Analysis:

Intuition:

Approach:

Dry Run:

Solution:

Complexity Analysis:

Notes

Code