Problem Statement

Given an array of n integers, find the sum of the frequencies of the highest occurring number and lowest occurring number.

Examples

Example 1:

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

Explanation: The highest frequency is 3 (element 3), and the lowest frequency is 1 (elment 1). Their sum is 3 + 1 = 4.

Example 2:

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

Explanation: The highest frequenc is 2 (element 4 and 5), and the lowest frquency is 1 (element 6). Their sum is 2 + 1 = 3

Different Approaches

1️⃣ Brute Force Approach

Intuition:

The brute force way to solve this problem will be to count the frequency of each element in the array, and once found, this frequency can be compared with the highest and the lowest frequency. Accordingly, the highest and the lowest frequency can be set.

Approach:

1. Determine the size of the array. Initialize two variables: one to keep track of the highest frequency and another for the lowest frequency.
2. Initially, set the highest frequency to zero (to ensure any actual frequency found will be higher and update this value.) and the lowest to the size of the array (to ensure any actual frequency found will be lower and update this value).
3. Create a visited array to avoid counting the same number multiple times.
4. Loop through each element in the array. For each element:
   1. If the element has already been counted (visited), skip it.
   2. Otherwise, count how many times this element appears in the array by comparing it with every other element.
   3. Update the highest and lowest frequency variables based on the count of the current element.
   4. Mark all occurrences of this element as visited.
5. Finally, add the highest and lowest frequencies together and return the result.

Code:

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

class Solution {
public:
    /* Function to get the sum of highest
    and lowest frequency in array */
    int sumHighestAndLowestFrequency(vector<int> &nums) {
        
        // Variable to store the size of array
        int n = nums.size();
        
        /* Variable to store maximum 
        and minimum frequency */
        int maxFreq = 0;
        int minFreq = n;

        // 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 maximum and 
            minimum frequencies */
            maxFreq = max(maxFreq, freq);
            minFreq = min(minFreq, freq);
        }
        
        // Return the required sum
        return maxFreq+minFreq;
    }
};

int main() {
    vector<int> nums = {1, 2, 2, 3, 3, 3};
    
    /* Creating an instance of 
    Solution class */
    Solution sol; 
    
    /* Function call to get the sum of highest
    and lowest frequency in array */
    int ans = sol.sumHighestAndLowestFrequency(nums);
    
    cout << "The sum of highest and lowest frequency in the array is: " << ans;
    
    return 0;
}

Complexity Analysis:

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

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:

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

Code:

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

class Solution {
public:
    /* Function to get the sum of highest
    and lowest frequency in array */
    int sumHighestAndLowestFrequency(vector<int> &nums) {
        
        // Variable to store the size of array
        int n = nums.size();
        
        /* Variable to store maximum 
        and minimum frequency */
        int maxFreq = 0, minFreq = n; 
        
        // 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 freq = it.second;
            
            /* Update maximum and 
            minimum frequencies */ 
            maxFreq = max(maxFreq, freq);
            minFreq = min(minFreq, freq);
            
        }
        
        // Return the required sum
        return maxFreq + minFreq;
    }
};

int main() {
    vector<int> nums = {1, 2, 2, 3, 3, 3};
    
    /* Creating an instance of 
    Solution class */
    Solution sol; 
    
    /* Function call to get the sum of highest
    and lowest frequency in array */
    int ans = sol.sumHighestAndLowestFrequency(nums);
    
    cout << "The sum of highest and lowest frequency in the array is: " << ans;
    
    return 0;
}

Complexity Analysis:

• Time Complexity:O(N), where N is the size of the array.
  • O(N): For inserting the frequency in the map.
  • O(k): For iterating over the map, where k is the number of unique elements.
    • In the worst case, k = n, when all the elements are unique.
• Space Complexity:O(k), where k is the number of unique elements.
  • In worst case k = n, when all the elements are unique.