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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count Almost Equal Pairs II

Number: 3544

Difficulty: Hard

Paid? No

Companies: N/A

Problem Description

Given an array of positive integers, we say that two integers x and y are “almost equal” if it is possible to obtain the same integer value (ignoring any leading zeros) by performing at most two operations on one of the numbers. In one operation you can choose either x or y and swap any two digits in its decimal representation. Note that after a swap, the resulting number may have leading zeros (which are ignored when comparing integer values). The task is to count the number of ordered pairs (i, j) with i < j such that nums[i] and nums[j] are almost equal.

Key Insights

  • The transformation by swapping digits does not change the multiset (frequency/count) of digits. Hence, if two numbers are not anagrams of each other (when viewed as strings), they cannot be almost equal.
  • Since only up to two swaps are allowed, only a few positions (at most four positions can be “incorrect”) can differ in the padded representations.
  • When numbers have different lengths, the shorter number cannot be padded arbitrarily. Instead, think of the swap operations on a number’s actual digits and then compare the integer value (so that leading zeros are effectively dropped).
  • We can “simulate” the allowed operations on one number by generating all reachable numbers (by performing 0, 1, or 2 swaps) and check if the other number’s integer value is among these.
  • Because the digits length of a number is at most eight (given the bound 10^7) the total number of states reachable from a number by up to two swaps is small (≈ 1 + C(n,2) + C(n,2)^2). We can precompute (and cache) these reachable values for each unique starting number.
  • The relation is not symmetric: It might be that x can be transformed to y in ≤2 swaps, while y cannot be transformed into x in ≤2 swaps. Therefore, when checking a pair, we must consider transforming either number.

Space and Time Complexity

Time Complexity: O(n^2 * f(L)) where f(L) is the constant cost of checking the transformation possibility (L is the number of digits, up to ~8). Grouping and caching by the unique string representation (of a number’s digits) helps to avoid repeated work. Space Complexity: O(U * S) where U is the number of unique numbers (represented as strings) and S is the size of the reachable set (at most 800 elements); additionally O(n^2) is needed for the pair counting, though it is done on the fly.

Solution

We solve the problem by defining a helper function that—given a number (represented as a string)—computes the set of integer values that can be reached by performing at most two swaps of its digits. (Note that swapping only rearranges digits so the multiset remains the same; however, the order matters since a swap can fix only a few misplacements.) We use breadth-first search (BFS) with a depth limit of 2 in order to generate the reachable states. Because two different swaps (or even different numbers with the same digits) might be queried many times, we cache the result by the original string representation. For each pair (i,j) in the array (with i<j), we check if either: – transforming the first number (with at most two swaps) can yield the second number (when interpreted as an integer), or – transforming the second number can yield the first. If either is true the pair is counted.

Key data structures and techniques:

  • Use a dictionary to cache the reachable set (as a set of integers) for each number’s string form.
  • Use BFS/DFS (given the small state space) to enumerate all states from a given string with at most two swaps.
  • Iterate over all pairs and use the cache to determine almost-equality.

Code Solutions

# Python solution with detailed line-by-line comments

from collections import deque

def countAlmostEqualPairs(nums):
    # Cache for reachable integer values from a given string representation.
    reachable_cache = {}
    
    def get_reachable(num_str):
        # If already computed, return the cached set.
        if num_str in reachable_cache:
            return reachable_cache[num_str]
        
        # Use BFS to compute all states reachable by <= 2 swaps.
        # Each state is a tuple: (state_string, number_of_swaps_used)
        seen = {num_str: 0}
        queue = deque()
        queue.append((num_str, 0))
        # Set to hold integer values reachable (we convert by int to drop any leading zeros)
        reachable_ints = {int(num_str)}
        
        while queue:
            state, swaps = queue.popleft()
            # Only proceed if we have not exceeded 2 swaps
            if swaps == 2:
                continue
            n = len(state)
            # Try all possible swaps between two positions
            state_list = list(state)
            for i in range(n):
                for j in range(i+1, n):
                    # Swap digits at positions i and j
                    new_list = state_list.copy()
                    new_list[i], new_list[j] = new_list[j], new_list[i]
                    new_state = ''.join(new_list)
                    # If we have not seen this state or we reached it with a higher swap count, then add it.
                    if new_state not in seen or seen[new_state] > swaps + 1:
                        seen[new_state] = swaps + 1
                        reachable_ints.add(int(new_state))
                        queue.append((new_state, swaps+1))
        # Cache the computed reachable set.
        reachable_cache[num_str] = reachable_ints
        return reachable_ints

    n = len(nums)
    count = 0
    # Precompute string representation for every number
    num_strs = [str(num) for num in nums]
    
    # Iterate over all pairs (i, j) with i < j
    for i in range(n):
        for j in range(i+1, n):
            a = nums[i]
            b = nums[j]
            # They must be anagrams (same multiset of digits) to be transformable.
            if sorted(num_strs[i]) != sorted(num_strs[j]):
                continue
            # Check if b can be obtained from a by <=2 swaps.
            if b in get_reachable(num_strs[i]):
                count += 1
            # Otherwise, check if a can be obtained from b by <=2 swaps.
            elif a in get_reachable(num_strs[j]):
                count += 1
                
    return count

# Example Usage:
print(countAlmostEqualPairs([1023, 2310, 2130, 213]))  # Expected output: 4
print(countAlmostEqualPairs([1, 10, 100]))              # Expected output: 3
← Back to All Questions