Skip to content

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

Thinking

We want \(x<y\) with different frequencies, minimizing \(x\) then \(y\). Both length and values are at most \(100\).

The smallest array value must be \(x\), because \(x\) is minimized first.

Count frequencies, take the smallest key as \(x\), then among other keys pick the smallest \(y\) with a different count.

If none exists, return \([-1,-1]\).

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}\).

1
2
3
4
5
6
7
8
9
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]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
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};
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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};
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
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}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
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];
}

Comments