Smallest Pair With Different Frequencies - Solution & Explanation

Problem Overview: You are given an integer array and need to return the smallest pair of values whose frequencies in the array are different. The key idea is that the pair must contain two numbers that appear a different number of times, while still producing the smallest possible pair by value.

Approach 1: Brute Force Pair Checking (O(n²) time, O(1) extra space)

The most direct approach checks every possible pair in the array. For each pair (i, j), compute the frequency of nums[i] and nums[j] by scanning the array and compare them. If the frequencies differ, update the answer if the pair is smaller than the current best. This approach works but is inefficient because frequency computation is repeated many times. With nested loops and repeated counting, the time complexity grows to O(n²) or worse depending on how frequencies are calculated. It mainly serves as a baseline to demonstrate the need for preprocessing.

Approach 2: Hash Table Frequency Counting (O(n) time, O(n) space)

The optimal solution uses a hash table to count how often each value appears. First iterate through the array and build a frequency map using a dictionary or map structure. This preprocessing step runs in O(n) time and avoids repeated counting later.

Next, work with the unique values and their frequencies. Track candidate values while ensuring their frequencies differ. Since the goal is the smallest pair by value, you compare numbers in increasing order and choose the smallest combination where the frequency counts are not equal. The frequency comparison becomes constant time thanks to the map lookup. This reduces the overall complexity to O(n) time with O(n) additional space for the frequency map.

This approach is common in problems involving value frequency analysis. Hash-based counting allows quick lookups and eliminates repeated work. Many array problems with constraints on occurrences rely on the same pattern, often categorized under counting techniques.

Recommended for interviews: The hash table counting approach is what interviewers expect. It demonstrates that you recognize repeated work in the brute force method and eliminate it using preprocessing. Mentioning the brute force idea first shows problem exploration, but implementing the hash map solution shows practical optimization skills and familiarity with frequency-based patterns.