LeetCode Problem 3852

Difficulty: 🟢 Easy
Topics: Array, Hash Table, Counting

Solution

LeetCode 3852 - Smallest Pair With Different Frequencies

Problem Understanding

This problem gives us an integer array nums and asks us to find a pair of distinct values [x, y] that satisfies two conditions:

1. x < y
2. The frequency of x in the array is different from the frequency of y.

Among all valid pairs, we must choose the one with the smallest possible value of x. If there are multiple valid pairs that share the same smallest x, we then choose the one with the smallest possible value of y.

The input array may contain duplicate values, so the first step is naturally to determine how many times each distinct value appears. Once we know the frequencies, we can examine pairs of distinct values and identify which pairs have different frequencies.

The output is an array containing the selected pair [x, y]. If no such pair exists, we return [-1, -1].

The constraints are quite small:

• 1 <= nums.length <= 100
• 1 <= nums[i] <= 100

This means there can be at most 100 elements and at most 100 distinct values. Even quadratic algorithms over the distinct values are completely acceptable.

Several edge cases are important:

• An array containing only one distinct value, such as [7], cannot form any pair.
• An array where all distinct values have the same frequency, such as [1, 5], has no valid answer.
• The smallest value in the array might not participate in any valid pair if every larger value has the same frequency.
• Multiple valid pairs may exist, requiring careful enforcement of the lexicographic ordering rule: smallest x first, then smallest y.

Approaches

Brute Force

A straightforward approach is to first count frequencies using a hash map. Then, generate every possible pair of distinct values (x, y) where x < y.

For each pair, check whether their frequencies differ. If they do, compare the pair against the best answer found so far according to the problem's ordering rules.

This approach is correct because it explicitly examines every candidate pair and chooses the lexicographically smallest valid one.

If there are k distinct values, there are O(k²) pairs to examine.

Key Observation

The problem's ordering rule is very specific:

• Minimize x.
• For that chosen x, minimize y.

Therefore, if we sort the distinct values, we can simply examine pairs in lexicographic order.

The first valid pair encountered is automatically the answer.

Why is this true?

After sorting:

• The outer loop visits values from smallest to largest, guaranteeing that the first valid pair uses the smallest possible x.
• The inner loop visits larger values from smallest to largest, guaranteeing that for that x, the first valid y is the smallest possible one.

As soon as we find a frequency mismatch, we can immediately return the pair.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(k²)	O(k)	Check every pair and track the best answer
Optimal	O(k²)	O(k)	Sort distinct values and return the first valid pair found

Here, k is the number of distinct values.

Algorithm Walkthrough

1. Create a frequency map that stores how many times each value appears in nums.
2. Extract all distinct values from the frequency map and sort them in ascending order.
3. Iterate through the sorted values using an outer loop. The current value becomes the candidate x.
4. For each x, iterate through all larger values using an inner loop. Each value becomes a candidate y.
5. Compare the frequencies of x and y.
6. If the frequencies are different, immediately return [x, y]. Because the values are being examined in lexicographic order, this is guaranteed to be the required answer.
7. If all pairs have been examined and none have different frequencies, return [-1, -1].

Why it works

The sorted order guarantees that pairs are examined in increasing order of x. For a fixed x, candidates are examined in increasing order of y. Therefore, the first valid pair encountered is exactly the lexicographically smallest valid pair required by the problem. Since every possible pair is considered in that order, no smaller valid answer can be missed.

Python Solution

class Solution:
    def minDistinctFreqPair(self, nums: list[int]) -> list[int]:
        freq = {}

        for num in nums:
            freq[num] = freq.get(num, 0) + 1

        values = sorted(freq.keys())

        n = len(values)

        for i in range(n):
            x = values[i]

            for j in range(i + 1, n):
                y = values[j]

                if freq[x] != freq[y]:
                    return [x, y]

        return [-1, -1]

The implementation begins by building a frequency map. Each number is counted once, allowing constant-time frequency lookups later.

Next, all distinct values are extracted and sorted. This sorting is crucial because the problem requires the lexicographically smallest valid pair.

The nested loops then examine pairs in sorted order. The outer loop selects the smallest possible x, while the inner loop searches for the smallest valid y.

Whenever a frequency mismatch is found, the pair is immediately returned. Because of the ordering of the loops, this pair is guaranteed to be the correct answer.

If no mismatch is ever found, all distinct values share the same frequency or there are fewer than two distinct values, so [-1, -1] is returned.

Go Solution

func minDistinctFreqPair(nums []int) []int {
	freq := make(map[int]int)

	for _, num := range nums {
		freq[num]++
	}

	values := make([]int, 0, len(freq))
	for value := range freq {
		values = append(values, value)
	}

	sort.Ints(values)

	n := len(values)

	for i := 0; i < n; i++ {
		x := values[i]

		for j := i + 1; j < n; j++ {
			y := values[j]

			if freq[x] != freq[y] {
				return []int{x, y}
			}
		}
	}

	return []int{-1, -1}
}

The Go implementation follows exactly the same logic as the Python version. A map stores frequencies, a slice stores distinct values, and sort.Ints is used to enforce ascending order. The nested loops examine pairs in lexicographic order and return the first valid pair found.

There are no integer overflow concerns because frequencies are at most 100. The function always returns a slice of length two, either containing the answer or [-1, -1].

Worked Examples

Example 1

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

Frequency Map

Value	Frequency
1	2
2	2
3	1
4	1

Sorted Distinct Values

Index	Value
0	1
1	2
2	3
3	4

Pair Checking

x	y	freq(x)	freq(y)	Valid?
1	2	2	2	No
1	3	2	1	Yes

The first valid pair encountered is [1, 3].

Output: [1, 3]

Example 2

Input: nums = [1,5]

Frequency Map

Value	Frequency
1	1
5	1

Pair Checking

x	y	freq(x)	freq(y)	Valid?
1	5	1	1	No

No valid pair exists.

Output: [-1, -1]

Example 3

Input: nums = [7]

Frequency Map

Value	Frequency
7	1

Sorted Distinct Values

Index	Value
0	7

There are fewer than two distinct values, so no pair can be formed.

Output: [-1, -1]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(k²)	Examine pairs of distinct values after counting frequencies
Space	O(k)	Frequency map and sorted distinct values

Here, k is the number of distinct values. Since k ≤ 100, the quadratic pair search is very small in practice. The frequency map and sorted value list each store at most k elements.

Test Cases

s = Solution()

assert s.minDistinctFreqPair([1, 1, 2, 2, 3, 4]) == [1, 3]  # example 1
assert s.minDistinctFreqPair([1, 5]) == [-1, -1]  # example 2
assert s.minDistinctFreqPair([7]) == [-1, -1]  # single value

assert s.minDistinctFreqPair([1, 1, 2]) == [1, 2]  # simplest valid pair
assert s.minDistinctFreqPair([1, 2, 3]) == [-1, -1]  # all frequencies equal
assert s.minDistinctFreqPair([5, 5, 5, 1]) == [1, 5]  # smallest value participates

assert s.minDistinctFreqPair([1, 1, 2, 2, 3, 3, 4]) == [1, 4]  # valid pair appears later
assert s.minDistinctFreqPair([2, 2, 3, 3, 4, 4]) == [-1, -1]  # all frequencies identical

assert s.minDistinctFreqPair([4, 4, 4, 1, 2, 2]) == [1, 2]  # lexicographically smallest answer
assert s.minDistinctFreqPair([10, 10, 20, 30, 30, 30]) == [10, 20]  # multiple frequencies

assert s.minDistinctFreqPair([100]) == [-1, -1]  # upper value boundary
assert s.minDistinctFreqPair([1] * 100) == [-1, -1]  # maximum length with one distinct value

Test Summary

Test	Why
[1,1,2,2,3,4]	Official example with valid answer
[1,5]	Two values with equal frequencies
[7]	Single distinct value
[1,1,2]	Smallest possible valid pair
[1,2,3]	Every value appears once
[5,5,5,1]	Different frequencies with smaller value first
[1,1,2,2,3,3,4]	Valid partner appears later in sorted order
[2,2,3,3,4,4]	No frequency differences exist
[4,4,4,1,2,2]	Verifies lexicographic ordering
[10,10,20,30,30,30]	Multiple frequency groups
[100]	Boundary value for element size
[1] * 100	Maximum array length with no answer

Edge Cases

Only One Distinct Value

An input such as [7] contains only one distinct number. Since a pair requires two distinct values, no candidate pair exists. A careless implementation might assume at least two distinct values are present and attempt invalid indexing. The algorithm handles this naturally because the nested loops never execute, leading to a return value of [-1, -1].

All Distinct Values Have Equal Frequencies

Consider [1, 2, 3, 4]. Every value appears exactly once. Although many pairs exist, none satisfy the requirement that frequencies differ. The algorithm checks every possible pair and finds no mismatch, eventually returning [-1, -1].

The First Few Pairs Are Invalid

Consider [1,1,2,2,3,3,4]. The pairs involving (1,2) and (1,3) are invalid because the frequencies match. A buggy implementation might incorrectly return the first pair involving the smallest value. The correct algorithm continues searching until it reaches (1,4), whose frequencies differ, and returns [1,4].

Lexicographic Ordering Requirements

Consider [4,4,4,1,2,2]. The valid pairs are (1,2) and (1,4). Even though both are valid, the problem requires the smallest possible y once x is fixed. Sorting the distinct values and checking pairs in ascending order guarantees that (1,2) is returned instead of (1,4).