We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Count Almost Equal Pairs II

Difficulty: Hard

Problem Description

You are given an array nums consisting of positive integers. We call two integers x and y almost equal if both integers can become equal after performing the following operation at most twice: Choose either x or y and swap any two digits within the chosen number. Return the number of indices i and j in nums where i < j such that nums[i] and nums[j] are almost equal.

Key Insights

  • Two integers can become equal by swapping digits within them.
  • Each integer can be modified at most twice, allowing for significant flexibility in matching them.
  • The problem can be approached using counting of digit permutations and combinations.

Space and Time Complexity

Time Complexity: O(n^2 * m), where n is the number of elements in nums and m is the maximum number of digits in any number in nums.
Space Complexity: O(n), for storing the transformed representations of the numbers.

Solution

To solve this problem, we can utilize a hashmap to count the occurrences of each unique digit configuration of the numbers. The main idea is to generate a canonical form for each number, which represents its possible digit swaps. The steps are as follows:

  1. For each number in the input array, generate all possible configurations by swapping digits up to two times.
  2. Store these configurations in a hashmap with their counts.
  3. For each unique configuration, calculate the number of almost equal pairs by using the combination formula for pairs (n choose 2).
  4. Sum the counts of pairs for all configurations to get the final result.

This approach leverages the efficiency of hashmaps for counting and allows quick retrieval of the number of pairs.

Code Solutions

def countAlmostEqualPairs(nums):
    from collections import defaultdict
    counts = defaultdict(int)

    for num in nums:
        str_num = str(num)
        digits = list(str_num)
        length = len(digits)
        
        # Generate all configurations by swapping digits
        for i in range(length):
            for j in range(i + 1, length):
                # Swap digits at position i and j
                digits[i], digits[j] = digits[j], digits[i]
                counts[''.join(sorted(digits))] += 1
                # Swap back to original positions
                digits[i], digits[j] = digits[j], digits[i]
        
        # Count the original configuration
        counts[''.join(sorted(str_num))] += 1
    
    result = 0
    for count in counts.values():
        if count > 1:
            result += count * (count - 1) // 2  # n choose 2

    return result
← Back to All Questions