Problem

Given an integer array arr, compute the frequency of every distinct element, then return the sum of the highest frequency and the lowest frequency.

Input / Output

• Input: integer array arr.
• Output: integer.

Examples

Example 1 Input: arr = [1, 2, 2, 3, 3, 3] Output: 4 Explanation: Frequencies are 1, 2, 3. Highest 3 + lowest 1 = 4.

Example 2 Input: arr = [7, 7, 7] Output: 6 Explanation: Only one distinct element with frequency 3; highest and lowest are both 3.

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

Constraints

• 1 <= n <= 10^5

Approach

1. Build a frequency map in one pass.
2. Scan the map's values once, tracking the maximum and the minimum.
3. Return max + min.

The problem is deliberately simple; what interviewers check is that you don't sort the whole array (O(n log n)) when a hash map gives O(n), and that you handle the single-distinct-value case where max and min coincide.

If elements are bounded (e.g. 0 <= arr[i] <= 10^5) a counting array replaces the hash map and avoids hashing overhead entirely.

Complexity

• Time: O(n)
• Space: O(k) for k distinct values.

Reference solution (Python)

from collections import Counter

def sum_high_low_freq(arr):
    freq = Counter(arr).values()
    return max(freq) + min(freq)

Test cases

Input	Expected
[1,2,2,3,3,3]	4
[7,7,7]	6
[1,2,3,4]	2
[5,5,9]	3