1. Smallest Pair With Different Frequencies (LeetCode)
Model answer
The task
The title suggests finding a pair of array values whose frequencies differ, then choosing the smallest such pair. The metadata does not specify what “smallest” means, so the code below leaves the pair-ranking rule to the caller.
Key idea
Count each value once, then compare distinct values using their counts. A ranking function lets the caller define “smallest” without assuming whether that means lexicographic order, minimum difference, or something else.
Approach
- Build a frequency table for the array.
- Sort the distinct values so each unordered pair is considered once.
- Skip pairs whose frequencies are equal.
- Keep the eligible pair with the lowest caller-provided ranking.
from collections import Counter
from collections.abc import Callable, Hashable, Sequence
from typing import TypeVar
T = TypeVar("T", bound=Hashable)
def smallest_pair_with_different_frequencies(
values: Sequence[T],
pair_rank: Callable[[tuple[T, T]], object],
) -> tuple[T, T] | None:
"""Return the lowest-ranked value pair with unequal frequencies.
Each pair is ordered by value. The caller supplies the ranking rule.
"""
counts = Counter(values)
distinct = sorted(counts)
best_pair = None
best_rank = None
for i, first in enumerate(distinct):
for second in distinct[i + 1:]:
if counts[first] == counts[second]:
continue
pair = (first, second)
rank = pair_rank(pair)
if best_pair is None or rank < best_rank:
best_pair = pair
best_rank = rank
return best_pair
Complexity:
- Time: O(n + u²), where n is the array length and u is the number of distinct values.
- Space: O(u) for the frequency table.
Common follow-ups
- What does “smallest” mean? Specify whether to rank by values, difference, indices, or another rule.
- Should pairs use values or array positions? That changes which pairs are considered.
- Can the search be faster? It may be, once the exact ranking rule is defined.
- What if no valid pair exists? Return
None, or use the required problem-specific result.