Watch 4 video solutions for Smallest Pair With Different Frequencies, a easy level problem involving Array, Hash Table, Counting. This walkthrough by CodingHelp has 119 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an integer array nums.
Consider all pairs of distinct values x and y from nums such that:
x < yx and y have different frequencies in nums.Among all such pairs:
x.x, choose the one with the smallest possible value of y.Return an integer array [x, y]. If no valid pair exists, return [-1, -1].
Example 1:
Input: nums = [1,1,2,2,3,4]
Output: [1,3]
Explanation:
The smallest value is 1 with a frequency of 2, and the smallest value greater than 1 that has a different frequency from 1 is 3 with a frequency of 1. Thus, the answer is [1, 3].
Example 2:
Input: nums = [1,5]
Output: [-1,-1]
Explanation:
Both values have the same frequency, so no valid pair exists. Return [-1, -1].
Example 3:
Input: nums = [7]
Output: [-1,-1]
Explanation:
There is only one value in the array, so no valid pair exists. Return [-1, -1].
Constraints:
1 <= nums.length <= 1001 <= nums[i] <= 100Problem 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.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Pair Checking | O(n²) | O(1) | Useful for understanding the problem or when the array size is extremely small |
| Hash Table Frequency Counting | O(n) | O(n) | General case. Best approach when you need fast frequency comparisons |