Smallest Pair With Different Frequencies

Difficulty: Easy | Acceptance: 69.50% | Paid: No Topics: Array, Hash Table, Counting

You are given a 0-indexed integer array nums. A pair of indices (i, j) is called valid if i < j and the frequency of nums[i] in the array is not equal to the frequency of nums[j] in the array.

Return the lexicographically smallest valid pair. If no such pair exists, return [-1, -1].

A pair (i1, j1) is lexicographically smaller than (i2, j2) if either i1 < i2 or i1 == i2 and j1 < j2.

• Examples
• Constraints
• Brute Force
• Hash Map + Nested Loops
• Linear Scan

Examples

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

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

Brute Force

Intuition Check every possible pair (i, j) in the array. For each pair, count the occurrences of nums[i] and nums[j] in the entire array to see if they are different.

Steps

• Iterate i from 0 to n-2.
• Iterate j from i+1 to n-1.
• For each pair, scan the array to count frequency of nums[i] and nums[j].
• If frequencies differ, return [i, j].
• If loop finishes, return [-1, -1].

class Solution:
    def smallestPair(self, nums: list[int]) -> list[int]:
        n = len(nums)
        for i in range(n):
            for j in range(i + 1, n):
                # Count frequencies on the fly
                count_i = 0
                count_j = 0
                for k in range(n):
                    if nums[k] == nums[i]:
                        count_i += 1
                    if nums[k] == nums[j]:
                        count_j += 1
                
                if count_i != count_j:
                    return [i, j]
        return [-1, -1]

Complexity

• Time: O(n³)
• Space: O(1)
• Notes: Inefficient for larger arrays due to repeated counting.

Hash Map + Nested Loops

Intuition Optimize the frequency counting by using a Hash Map to store frequencies of all elements first. Then, check every pair to find the first valid one.

Steps

• Create a frequency map of nums.
• Iterate i from 0 to n-2.
• Iterate j from i+1 to n-1.
• Check if freq[nums[i]] != freq[nums[j]].
• If true, return [i, j].
• If loop finishes, return [-1, -1].

from collections import Counter

class Solution:
    def smallestPair(self, nums: list[int]) -> list[int]:
        freq = Counter(nums)
        n = len(nums)
        for i in range(n):
            for j in range(i + 1, n):
                if freq[nums[i]] != freq[nums[j]]:
                    return [i, j]
        return [-1, -1]

Complexity

• Time: O(n²)
• Space: O(n)
• Notes: Much better than brute force, but still quadratic.

Linear Scan

Intuition We want the lexicographically smallest pair (i, j). This means we want the smallest possible i. The smallest possible i is 0. If there exists any j > 0 such that the frequency of nums[j] is different from nums[0], then (0, j) is the answer (specifically the smallest such j). If no such j exists, it means all elements have the same frequency, so no valid pair exists.

Steps

• Calculate the frequency of all elements in nums.
• Get the frequency of the first element nums[0], call it target_freq.
• Iterate j from 1 to n-1.
• If freq[nums[j]] != target_freq, return [0, j].
• If the loop completes, return [-1, -1].

from collections import Counter

class Solution:
    def smallestPair(self, nums: list[int]) -> list[int]:
        freq = Counter(nums)
        n = len(nums)
        target_freq = freq[nums[0]]
        
        for j in range(1, n):
            if freq[nums[j]] != target_freq:
                return [0, j]
                
        return [-1, -1]

Complexity

• Time: O(n)
• Space: O(n)
• Notes: Optimal solution. We only need to check pairs starting with index 0.