Welcome to Subscribe On Youtube

3852. Smallest Pair With Different Frequencies

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.

Among all such pairs:

  • Choose the pair with the smallest possible value of x.
  • If multiple pairs have the same 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 <= 100
  • 1 <= nums[i] <= 100

Solutions

Solution 1: Hash Table

We use a hash table $\textit{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 time complexity is $O(n)$, and the space complexity is $O(n)$, where $n$ is the length of the array $\textit{nums}$.

  • class Solution {
    public int[] minDistinctFreqPair(int[] nums) {
        final int inf = Integer.MAX_VALUE;
        Map<Integer, Integer> cnt = new HashMap<>();
        int x = inf;
        for (int v : nums) {
            cnt.merge(v, 1, Integer::sum);
            x = Math.min(x, v);
        }
        int minY = inf;
        for (int y : cnt.keySet()) {
            if (y < minY && cnt.get(x) != cnt.get(y)) {
                minY = y;
            }
        }
        return minY == inf ? new int[] {-1, -1} : new int[] {x, minY};
    }
}


  • class Solution {
public:
    vector<int> minDistinctFreqPair(vector<int>& nums) {
        const int inf = INT_MAX;
        unordered_map<int, int> cnt;
        int x = inf;

        for (int v : nums) {
            cnt[v]++;
            x = min(x, v);
        }

        int minY = inf;
        for (auto& [y, _] : cnt) {
            if (y < minY && cnt[x] != cnt[y]) {
                minY = y;
            }
        }

        if (minY == inf) {
            return {-1, -1};
        }
        return {x, minY};
    }
};


  • class Solution:
    def minDistinctFreqPair(self, nums: list[int]) -> list[int]:
        cnt = Counter(nums)
        x = min(cnt.keys())
        min_y = inf
        for y in cnt.keys():
            if y < min_y and cnt[x] != cnt[y]:
                min_y = y
        return [-1, -1] if min_y == inf else [x, min_y]


  • func minDistinctFreqPair(nums []int) []int {
	const inf = math.MaxInt
	cnt := make(map[int]int)

	for _, v := range nums {
		cnt[v]++
	}

	x := slices.Min(nums)

	minY := inf
	for y := range cnt {
		if y < minY && cnt[x] != cnt[y] {
			minY = y
		}
	}

	if minY == inf {
		return []int{-1, -1}
	}
	return []int{x, minY}
}


  • function minDistinctFreqPair(nums: number[]): number[] {
    const inf = Number.MAX_SAFE_INTEGER;
    const cnt = new Map<number, number>();

    let x = inf;
    for (const v of nums) {
        cnt.set(v, (cnt.get(v) ?? 0) + 1);
        x = Math.min(x, v);
    }

    let minY = inf;
    for (const [y] of cnt) {
        if (y < minY && cnt.get(x)! !== cnt.get(y)!) {
            minY = y;
        }
    }

    return minY === inf ? [-1, -1] : [x, minY];
}

All Problems

All Solutions