Sum of highest and lowest frequency
Beginner Problems
Basic Hashing
Easy
Given an array of n integers, find the sum of the frequencies of the highest occurring number and lowest occurring number.
Examples:
Input: arr = [1, 2, 2, 3, 3, 3]
Output: 4
Explanation: The highest frequency is 3 (element 3), and the lowest frequency is 1 (element 1). Their sum is 3 + 1 = 4.
Input: arr = [4, 4, 5, 5, 6]
Output: 3
Explanation: The highest frequency is 2 (elements 4 and 5), and the lowest frequency is 1 (element 6). Their sum is 2 + 1 = 3.
Input: arr = [10, 9, 7, 7, 8, 8, 8]
Constraints
- 1 <= n <= 104
- 1 <= arr[i] <= 104
Company Tags
TCS
Cognizant
Accenture
Infosys
Capgemini
Wipro
IBM
HCL
Tech Mahindra
MindTree
Editorial
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:
- Determine the size of the array. Initialize two variables: one to keep track of the highest frequency and another for the lowest frequency.
- 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).
- Create a visited array to avoid counting the same number multiple times.
- Loop through each element in the array. For each element:
- If the element has already been counted (visited), skip it.
- Otherwise, count how many times this element appears in the array by comparing it with every other element.
- Update the highest and lowest frequency variables based on the count of the current element.
- Mark all occurrences of this element as visited.
- Finally, add the highest and lowest frequencies together and return the result.
Dry Run:
Solution:
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263
#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;
}123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960
import java.util.*;
class Solution {
/* Function to get the sum of highest
and lowest frequency in array */
public int sumHighestAndLowestFrequency(int[] nums) {
// Variable to store the size of array
int n = nums.length;
/* Variable to store maximum
and minimum frequency */
int maxFreq = 0;
int minFreq = n;
// 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 maximum and
minimum frequencies */
maxFreq = Math.max(maxFreq, freq);
minFreq = Math.min(minFreq, freq);
}
// Return the required sum
return maxFreq + minFreq;
}
public static void main(String[] args) {
int[] nums = {1, 2, 2, 3, 3, 3};
/* Creating an instance of
Solution class */
Solution sol = new Solution();
/* Function call to get the sum of highest
and lowest frequency in array */
int ans = sol.sumHighestAndLowestFrequency(nums);
System.out.println("The sum of highest and lowest frequency in the array is: " + ans);
}
}12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152
class Solution:
""" Function to get the sum of highest
and lowest frequency in array """
def sumHighestAndLowestFrequency(self, nums):
# Variable to store the size of array
n = len(nums)
""" Variable to store maximum
and minimum frequency """
max_freq = 0
min_freq = n
# 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 maximum and
minimum frequencies """
max_freq = max(max_freq, freq)
min_freq = min(min_freq, freq)
# Return the required sum
return max_freq + min_freq
# Example usage
nums = [1, 2, 2, 3, 3, 3]
""" Creating an instance of
Solution class """
sol = Solution()
""" Function call to get the sum of highest
and lowest frequency in array """
ans = sol.sumHighestAndLowestFrequency(nums)
print("The sum of highest and lowest frequency in the array is:", ans)123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657
class Solution {
/* Function to get the sum of highest
and lowest frequency in array */
sumHighestAndLowestFrequency(nums) {
// Variable to store the size of array
let n = nums.length;
/* Variable to store maximum
and minimum frequency */
let maxFreq = 0;
let minFreq = n;
// Visited array
let visited = 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 maximum and
minimum frequencies */
maxFreq = Math.max(maxFreq, freq);
minFreq = Math.min(minFreq, freq);
}
// Return the required sum
return maxFreq + minFreq;
}
}
// Example usage
let nums = [1, 2, 2, 3, 3, 3];
/* Creating an instance of
Solution class */
let sol = new Solution();
/* Function call to get the sum of highest
and lowest frequency in array */
let ans = sol.sumHighestAndLowestFrequency(nums);
console.log("The sum of highest and lowest frequency 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:
- 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 highest frequency and the lowest frequency whose sum can be returned as answer.
Dry Run:
Solution:
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657
#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;
}
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950
import java.util.HashMap;
class Solution {
/* Function to get the sum of highest
and lowest frequency in array */
public int sumHighestAndLowestFrequency(int[] nums) {
// Variable to store the size of array
int n = nums.length;
/* Variable to store maximum
and minimum frequency */
int maxFreq = 0, minFreq = n;
// 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 (int freq : mpp.values()) {
/* Update maximum and
minimum frequencies */
maxFreq = Math.max(maxFreq, freq);
minFreq = Math.min(minFreq, freq);
}
// Return the required sum
return maxFreq + minFreq;
}
public static void main(String[] args) {
int[] nums = {1, 2, 2, 3, 3, 3};
/* Creating an instance of
Solution class */
Solution sol = new Solution();
/* Function call to get the sum of highest
and lowest frequency in array */
int ans = sol.sumHighestAndLowestFrequency(nums);
System.out.println("The sum of highest and lowest frequency in the array is: " + ans);
}
}
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748
class Solution:
# Function to get the sum of highest
# and lowest frequency in array
def sumHighestAndLowestFrequency(self, nums):
# Variable to store the size of array
n = len(nums)
# Variable to store maximum
# and minimum frequency
maxFreq = 0
minFreq = n
# 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 freq in mpp.values():
# Update maximum and
# minimum frequencies
maxFreq = max(maxFreq, freq)
minFreq = min(minFreq, freq)
# Return the required sum
return maxFreq + minFreq
# Test the solution
if __name__ == "__main__":
nums = [1, 2, 2, 3, 3, 3]
# Creating an instance of
# Solution class
sol = Solution()
# Function call to get the sum of highest
# and lowest frequency in array
ans = sol.sumHighestAndLowestFrequency(nums)
print(f"The sum of highest and lowest frequency in the array is: {ans}")
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051
class Solution {
/* Function to get the sum of highest
and lowest frequency in array */
sumHighestAndLowestFrequency(nums) {
// Variable to store the size of array
const n = nums.length;
/* Variable to store maximum
and minimum frequency */
let maxFreq = 0, minFreq = n;
// HashMap
const mpp = new Map();
// Iterating on the array
nums.forEach(num => {
// Updating hashmap
if (mpp.has(num)) {
mpp.set(num, mpp.get(num) + 1);
} else {
mpp.set(num, 1);
}
});
// Iterate on the map
for (let freq of mpp.values()) {
/* Update maximum and
minimum frequencies */
maxFreq = Math.max(maxFreq, freq);
minFreq = Math.min(minFreq, freq);
}
// Return the required sum
return maxFreq + minFreq;
}
}
// Test the solution
const nums = [1, 2, 2, 3, 3, 3];
// Creating an instance of
// Solution class
const sol = new Solution();
// Function call to get the sum of highest
// and lowest frequency in array
const ans = sol.sumHighestAndLowestFrequency(nums);
console.log(`The sum of highest and lowest frequency in the array is: ${ans}`);
Complexity Analysis:
Time Complexity: O(N) (where N is the size of the array given) –
- Iterating the array results in O(N) TC. In every iteration, the hashmap is updated, which is a constant time operation. This results in overall 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:
4
4
Actual: -
Time: -
sec
Status: Waiting
Input: {'nums': '[4, 4, 5, 5, 6]'}
Expected:
3
3
Actual: -
Time: -
sec
Status: Waiting
Input: {'nums': '[10, 9, 7, 7, 8, 8, 8]'}
Expected:
4
4
Actual: -
Time: -
sec
Status: Waiting
Facts
- • This programming problem is conceptually related to data analysis and statistics, often used in the software industry for user behavior analysis, trend identification, and recommendation systems
- • The identification of the most and least frequent values (modal and anti-modal values) is commonly used in sectors like e-commerce and social media to understand user preferences and trends, such as the highest and lowest selling products, or the most and least liked posts