3852. Smallest Pair With Different Frequencies

EasyArrayHash TableCounting

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given an integer array nums.

Consider all pairs of distinct values x and y from nums such that:

x < y
x and y have different frequencies in nums (the frequency of a value is the number of times it appears in the array).

Among all such valid pairs:

Choose the pair with the smallest possible value of x.
If multiple pairs share the same x, choose the one with the smallest possible value of y.

Return an integer array [x, y] representing the chosen pair. If no valid pair exists, return [-1, -1].

In other words, you first count how many times each distinct value occurs in nums. The value x is fixed as the smallest distinct value in nums. Then you look for the smallest value y that is greater than x and whose occurrence count differs from that of x. If such a y can be found, return [x, y]; otherwise, return [-1, -1].

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Hash Table / Counting?

This problem maps to Hash Table / Counting through a short path in the full flowchart.

Uses hash table to count element frequencies, then finds smallest value with a different count.

Open in Flowchart

Intuition

The first thing we need is the frequency of every distinct value in nums. A natural tool for this is a hash table (or counter) that maps each value to how many times it appears. Once we have these counts, every condition in the problem can be checked directly.

Next, notice that the rules for picking the pair are very strict about ordering. We must pick the smallest possible x first, and only then the smallest possible y. Since x < y, and we want x to be as small as it can be, the best candidate for x is simply the smallest distinct value in the array. There is no benefit to choosing a larger x, because a smaller x always takes priority in the tie-breaking rules.

With x fixed as the minimum value, the problem reduces to finding the smallest value y that satisfies two conditions: y > x and y has a different frequency from x. Because x is already the smallest distinct value, any other distinct value y automatically satisfies y > x, so we only need to check the frequency condition cnt[x] != cnt[y].

So we scan through all distinct values, and among those whose frequency differs from cnt[x], we keep track of the smallest one. If we find such a value, that is our y and the answer is [x, y]. If every other value shares the same frequency as x (or there are no other values at all), then no valid pair exists and we return [-1, -1].

Solution Approach

Solution 1: Hash Table

We use a hash table cnt to count the frequency of each value in the array. Then we find the smallest value x, and the smallest value y that is greater than x and has a different frequency from x. If no such y exists, return [-1, -1].

The implementation follows these steps:

Count frequencies. We build a Counter over nums, producing the hash table cnt where cnt[v] is the number of times value v appears in the array. This lets us look up any value's frequency in O(1) time.
Fix x as the minimum value. Since the rules require x to be as small as possible and x < y, the optimal choice for x is the smallest distinct value. We compute this with x = min(cnt.keys()).
Search for the smallest valid y. We initialize min_y = inf and iterate over every distinct value y in cnt.keys(). For each y, we check two things at once: y < min_y (so we keep only the smallest candidate seen so far) and cnt[x] != cnt[y] (so y has a different frequency from x). Because x is already the smallest distinct value, the condition y > x is automatically satisfied for any other key, so it does not need an explicit check. Whenever both conditions hold, we update min_y = y.
Return the result. After the loop, if min_y is still inf, no value with a different frequency was found, so we return [-1, -1]. Otherwise, the pair is [x, min_y].

The time complexity is O(n), where n is the length of nums, since building the counter and scanning the distinct keys each take linear time. The space complexity is O(n) for storing the hash table cnt.

Example Walkthrough

Let's trace through the solution approach with a small example.

Input: nums = [1, 3, 1, 4, 4, 3, 4]

Step 1: Count frequencies.

We build a hash table cnt by counting how many times each value appears:

Value	Count
1	2
3	2
4	3

So cnt = {1: 2, 3: 2, 4: 3}.

Step 2: Fix x as the minimum value.

The smallest distinct value is x = min(cnt.keys()) = 1. Its frequency is cnt[1] = 2. This x is fixed because the rules demand the smallest possible x, and a smaller x always wins the tie-breaking.

Step 3: Search for the smallest valid y.

Initialize min_y = inf. Now iterate over every distinct value y and check both y < min_y and cnt[x] != cnt[y] (where cnt[x] = 2):

y = 1: cnt[1] = 2, which equals cnt[x] = 2. Frequencies match, so skip. (This is x itself.)
y = 3: cnt[3] = 2, which equals cnt[x] = 2. Frequencies match, so skip.
y = 4: cnt[4] = 3, which differs from cnt[x] = 2. ✅ And 4 < inf, so update min_y = 4.

After the loop, min_y = 4.

Step 4: Return the result.

Since min_y is no longer inf, a valid pair was found. The answer is [x, min_y] = [1, 4].

Why this is correct: x = 1 is the smallest distinct value (so it has the highest priority), and among all values greater than 1, the value 3 shares the same frequency as 1 (both appear twice), while 4 has a different frequency (appears 3 times). Thus 4 is the smallest valid y, giving the final answer [1, 4].

Edge case note: If instead all values shared the same frequency — for example nums = [2, 5, 2, 5] where cnt = {2: 2, 5: 2} — then no y would satisfy the frequency condition, min_y would remain inf, and the result would be [-1, -1].

Solution Implementation

1from collections import Counter
2from math import inf
3
4
5class Solution:
6    def minDistinctFreqPair(self, nums: list[int]) -> list[int]:
7        # Count the frequency of every distinct value in nums.
8        count = Counter(nums)
9
10        # Choose x as the smallest distinct value present in nums.
11        x = min(count.keys())
12
13        # Search for the smallest value y whose frequency differs from x's.
14        # Initialize with infinity so we can detect the "not found" case later.
15        min_y = inf
16        for y in count.keys():
17            # y must be smaller than the current best candidate,
18            # and its frequency must differ from x's frequency.
19            # Note: y == x is naturally excluded since count[x] == count[x].
20            if y < min_y and count[x] != count[y]:
21                min_y = y
22
23        # If min_y was never updated, no valid pair exists.
24        return [-1, -1] if min_y == inf else [x, min_y]
25

1class Solution {
2    public int[] minDistinctFreqPair(int[] nums) {
3        // Sentinel value representing "not found" / positive infinity.
4        final int inf = Integer.MAX_VALUE;
5
6        // Map each number to its frequency in the array.
7        Map<Integer, Integer> countMap = new HashMap<>();
8
9        // Track the minimum value present in the array.
10        int minX = inf;
11
12        // First pass: build the frequency map and record the smallest value.
13        for (int value : nums) {
14            countMap.merge(value, 1, Integer::sum);
15            minX = Math.min(minX, value);
16        }
17
18        // Second pass: find the smallest value whose frequency
19        // differs from the frequency of minX.
20        int minY = inf;
21        for (int candidate : countMap.keySet()) {
22            if (candidate < minY
23                    && !countMap.get(minX).equals(countMap.get(candidate))) {
24                minY = candidate;
25            }
26        }
27
28        // If no valid partner was found, return {-1, -1}; otherwise {minX, minY}.
29        return minY == inf ? new int[] {-1, -1} : new int[] {minX, minY};
30    }
31}
32

1class Solution {
2public:
3    vector<int> minDistinctFreqPair(vector<int>& nums) {
4        const int kInf = INT_MAX;
5
6        // Map each distinct value to its occurrence count.
7        unordered_map<int, int> countMap;
8
9        // Track the smallest value in the array.
10        int minValue = kInf;
11
12        for (int value : nums) {
13            countMap[value]++;
14            minValue = min(minValue, value);
15        }
16
17        // Find the smallest value whose frequency differs
18        // from the frequency of the overall minimum value.
19        int candidateValue = kInf;
20        for (const auto& [value, frequency] : countMap) {
21            if (value < candidateValue &&
22                countMap[minValue] != frequency) {
23                candidateValue = value;
24            }
25        }
26
27        // No value with a distinct frequency was found.
28        if (candidateValue == kInf) {
29            return {-1, -1};
30        }
31
32        return {minValue, candidateValue};
33    }
34};
35

1function minDistinctFreqPair(nums: number[]): number[] {
2    // Sentinel value representing "not found" / positive infinity.
3    const INF = Number.MAX_SAFE_INTEGER;
4
5    // Map each number to how many times it appears in the array.
6    const frequency = new Map<number, number>();
7
8    // The smallest value in the array.
9    let minValue = INF;
10    for (const value of nums) {
11        // Increment this value's frequency (default 0 if unseen).
12        frequency.set(value, (frequency.get(value) ?? 0) + 1);
13        // Track the minimum value encountered.
14        minValue = Math.min(minValue, value);
15    }
16
17    // The smallest value whose frequency differs from minValue's frequency.
18    let minOther = INF;
19    const minValueFreq = frequency.get(minValue)!;
20    for (const [value] of frequency) {
21        // Pick the smallest candidate with a different frequency than minValue.
22        if (value < minOther && frequency.get(value)! !== minValueFreq) {
23            minOther = value;
24        }
25    }
26
27    // If no qualifying value was found, return [-1, -1]; otherwise the pair.
28    return minOther === INF ? [-1, -1] : [minValue, minOther];
29}
30

Time and Space Complexity

Time Complexity: O(n), where n is the length of the array nums. Building the Counter requires iterating over all elements once, costing O(n). Finding the minimum key with min(cnt.keys()) takes O(k), and the subsequent loop over the counter's keys also takes O(k), where k is the number of distinct elements. Since k ≤ n, the overall time complexity is O(n).
Space Complexity: O(n). The Counter object stores up to n distinct keys along with their frequencies. In the worst case (all elements distinct), it holds n entries, so the space complexity is O(n).

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Assuming `y` is automatically greater than `x` without considering edge cases

A subtle issue arises from the optimization that skips the explicit y > x check. The reasoning is that since x = min(count.keys()), any other key must be greater than x. While this is correct, the comment "y == x is naturally excluded since count[x] == count[x]" relies on this fact in a fragile way. If the code is ever refactored — for example, if x is no longer guaranteed to be the minimum, or if the comparison logic changes — this implicit assumption breaks silently, and y could equal or be less than x.

Solution: Make the y > x constraint explicit. This costs nothing in performance and protects the logic against future refactoring:

for y in count.keys():
    if y > x and y < min_y and count[x] != count[y]:
        min_y = y

Pitfall 2: Empty input array causing `min()` to crash

If nums is empty, then count is also empty, and the call x = min(count.keys()) raises a ValueError: min() arg is an empty sequence. The code never reaches the [-1, -1] return path because it crashes before the loop.

Solution: Guard against the empty case (or a single distinct value) before computing the minimum:

count = Counter(nums)
if len(count) < 2:
    return [-1, -1]
x = min(count.keys())

A single distinct value also can never form a valid pair, so checking len(count) < 2 handles both situations at once.

Pitfall 3: Misreading the problem as "any pair with minimum x" rather than "fixed x = global minimum"

A common misinterpretation is to search over all pairs (x, y) and minimize x among only those pairs that have differing frequencies. One might worry that the true smallest distinct value could be excluded if it has the same frequency as every other value, forcing a larger x.

In fact, the problem statement clarifies that x is always the smallest distinct value. If that value shares its frequency with every other distinct value, then no valid pair exists at all — you do not fall back to a larger x. The answer is [-1, -1], not a pair built from the second-smallest value.

Solution: Trust that x is fixed as the global minimum. The current code does this correctly, but be careful not to "fix" it into iterating over all possible x values, which would produce wrong answers on inputs like nums = [1, 1, 2, 2, 3, 3] (all frequencies equal → correct answer [-1, -1]).

Pitfall 4: Using a fragile sentinel comparison with `inf`

Comparing min_y == inf works, but mixing inf (a float) with integer values can lead to subtle type confusion if the result is later used in integer-only contexts. The returned list could inadvertently contain a float.

Solution: Use a boolean flag or None as the sentinel to keep types clean:

min_y = None
for y in count.keys():
    if y > x and count[x] != count[y]:
        if min_y is None or y < min_y:
            min_y = y
return [-1, -1] if min_y is None else [x, min_y]

This avoids any chance of returning a float and makes the "not found" intent more readable.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)

Optimal substructure

Overlapping subproblems

Non-overlapping subproblems

Constant time subproblems

Core Learning

LLD/OOP Interview

Additional Resources

AI Engineering