Problem Description

You are given an array nums consisting of positive integers.

Two integers x and y are considered almost equal if they can become equal after performing the following operation at most once:

• Choose either x or y
• Swap any two digits within the chosen number

Your task is to count the number of pairs of indices (i, j) where i < j such that nums[i] and nums[j] are almost equal.

For example:

• Numbers 123 and 321 are almost equal because swapping the first and last digits of 123 gives 321
• Numbers 123 and 123 are almost equal because they're already equal (no swap needed)
• Numbers 12 and 21 are almost equal because swapping the two digits of either number makes them equal

Important notes:

• Leading zeros are allowed after performing a swap operation (e.g., 100 can become 001 by swapping)
• The operation can be performed at most once, meaning you can also choose not to swap at all
• You need to count pairs where the first index is less than the second index (i < j)

The solution involves:

1. Sorting the array first to handle cases where smaller numbers might be obtained through swapping
2. For each number, generating all possible numbers that can be obtained by swapping any two digits (or keeping it unchanged)
3. Using a counter to track previously seen numbers and checking how many of them match the current number's possible variations
4. Accumulating the count of valid pairs

Intuition

The key insight is that for each number, we need to find all other numbers in the array that can become equal to it through at most one digit swap. A naive approach would be to compare every pair of numbers and check if they're almost equal, but this would be inefficient.

Instead, we can think about it differently: for each number, what are all the possible values it could transform into with at most one swap? If we generate all these possibilities and store them in a set, we can then check if any previously seen numbers match these possibilities.

Why do we need to sort the array first? Consider numbers like 100 and 1. When we swap digits in 100, we can get 001 which equals 1. However, if we process 100 before 1, we won't find 1 in our count of previously seen numbers, missing this valid pair. By sorting the array, we ensure smaller numbers are processed first, so when we encounter 100, the number 1 has already been counted.

The approach becomes:

1. For each number x, generate all possible numbers by swapping any two digits (including not swapping at all, which keeps the original number)
2. Check how many of these generated numbers we've already seen before in our traversal
3. Add the current number to our count for future comparisons

This way, we avoid checking every pair explicitly. Instead, we leverage a hash table to track previously seen numbers and efficiently find matches. The time complexity improves because generating all swap variations for a single number is bounded by the number of digit pairs, which is at most O(d²) where d is the number of digits, typically small.

The sorting step ensures we don't miss pairs where a larger number can transform into a smaller one through digit swapping.

Learn more about Sorting patterns.

Solution Approach

The implementation follows these steps:

1. Sort the array: We start by sorting nums in ascending order. This ensures that when we process a number, all smaller numbers that it could potentially match with have already been processed.

2. Initialize data structures:

   • ans: Counter for the number of valid pairs
   • cnt: A defaultdict(int) that tracks how many times each number has been seen so far

3. Process each number: For each number x in the sorted array:

   a. Generate all possible variations: Create a set vis to store all numbers that can be obtained by swapping at most one pair of digits:

   • Start by adding the original number x to vis (representing no swap)
   • Convert the number to a list of characters: s = list(str(x))
   • Use nested loops to try swapping every pair of digits:

     for j in range(len(s)):
         for i in range(j):
             s[i], s[j] = s[j], s[i]  # Swap digits at positions i and j
             vis.add(int("".join(s)))  # Add the new number to vis
             s[i], s[j] = s[j], s[i]  # Swap back to restore original

   b. Count matches with previously seen numbers:

   • For each number in vis, check how many times it has appeared before in cnt
   • Add the total count to ans: ans += sum(cnt[x] for x in vis)

   c. Update the counter: Add the current number x to cnt for future comparisons: cnt[x] += 1

4. Return the result: The final value of ans represents the total number of valid pairs.

Example walkthrough: Consider nums = [1, 10, 100]:

• Process 1: vis = {1}, no previous matches, cnt[1] = 1
• Process 10: vis = {10, 1} (swapping gives 01 = 1), finds 1 in cnt, adds 1 to answer, cnt[10] = 1
• Process 100: vis = {100, 10, 1} (various swaps), finds both 1 and 10 in cnt, adds 2 to answer
• Final answer: 3 pairs

The time complexity is O(n log n + n × d²) where n is the array length and d is the maximum number of digits. The space complexity is O(n × d²) for storing all variations.

Example Walkthrough

Let's walk through a detailed example with nums = [13, 31, 103, 310]:

Step 1: Sort the array

• After sorting: nums = [13, 31, 103, 310]

Step 2: Process each number

Processing 13:

• Convert to string: "13"
• Generate all possible variations by swapping:
  • No swap: 13
  • Swap positions 0 and 1: 31
• vis = {13, 31}
• Check counter cnt for matches: Both 13 and 31 have count 0 (not seen yet)
• Add to answer: ans = 0
• Update counter: cnt[13] = 1

Processing 31:

• Convert to string: "31"
• Generate all possible variations:
  • No swap: 31
  • Swap positions 0 and 1: 13
• vis = {31, 13}
• Check counter for matches: cnt[31] = 0, cnt[13] = 1
• Add to answer: ans = 0 + 1 = 1 (found one 13)
• Update counter: cnt[31] = 1

Processing 103:

• Convert to string: "103"
• Generate all possible variations:
  • No swap: 103
  • Swap positions 0 and 1: 013 = 13
  • Swap positions 0 and 2: 301
  • Swap positions 1 and 2: 130
• vis = {103, 13, 301, 130}
• Check counter for matches: cnt[103] = 0, cnt[13] = 1, cnt[301] = 0, cnt[130] = 0
• Add to answer: ans = 1 + 1 = 2 (found one 13)
• Update counter: cnt[103] = 1

Processing 310:

• Convert to string: "310"
• Generate all possible variations:
  • No swap: 310
  • Swap positions 0 and 1: 130
  • Swap positions 0 and 2: 013 = 13
  • Swap positions 1 and 2: 301
• vis = {310, 130, 13, 301}
• Check counter for matches: cnt[310] = 0, cnt[130] = 0, cnt[13] = 1, cnt[301] = 0
• Add to answer: ans = 2 + 1 = 3 (found one 13)
• Update counter: cnt[310] = 1

Final Result: ans = 3

The three valid pairs are:

1. (0, 1): 13 and 31 - can swap digits of 13 to get 31
2. (0, 2): 13 and 103 - can swap first and second digits of 103 to get 013 = 13
3. (0, 3): 13 and 310 - can swap first and third digits of 310 to get 013 = 13

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × (log n + log³ M))

The time complexity breaks down as follows:

• Sorting the array takes O(n log n) time
• For each element in the array (n iterations):
  • Converting number to string takes O(log M) time (where M is the maximum value, as the number of digits is proportional to log M)
  • The nested loops for swapping digits run O(log² M) times (choosing 2 positions from log M digits)
  • Each swap operation and string-to-integer conversion takes O(log M) time
  • The set vis can contain at most O(log² M) elements (all possible single swaps plus the original)
  • Summing up counts for elements in vis takes O(log² M) time
  • Overall per element: O(log² M × log M) = O(log³ M)
• Total: O(n log n) + O(n × log³ M) = O(n × (log n + log³ M))

Space Complexity: O(n + log² M)

The space complexity consists of:

• The cnt dictionary stores at most n unique elements: O(n)
• The vis set for each iteration contains at most O(log² M) elements (all possible single swap variations)
• The string s takes O(log M) space
• Overall: O(n + log² M)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Not Sorting the Array First

One of the most critical pitfalls is forgetting to sort the array before processing. Without sorting, you might miss pairs where a larger number can be transformed into a smaller one through digit swapping.

Why it matters: Consider nums = [100, 1]. If we process left-to-right without sorting:

• When processing 100, we haven't seen 1 yet, so we miss the pair
• When processing 1, we can't "look back" to find 100

Solution: Always sort the array first to ensure all potential matches for a number have been processed before it.

2. Incorrect Digit Swapping Logic

A common mistake is not properly restoring the digits after each swap, leading to compound swaps instead of single swaps.

Incorrect approach:

digits = list(str(current_num))
for j in range(len(digits)):
    for i in range(j):
        digits[i], digits[j] = digits[j], digits[i]  # Swap
        possible_values.add(int("".join(digits)))
        # Forgot to swap back! Next iteration works on modified digits

Solution: Always swap back immediately after recording the result:

digits[i], digits[j] = digits[j], digits[i]  # Swap
possible_values.add(int("".join(digits)))
digits[i], digits[j] = digits[j], digits[i]  # Swap back

3. Double Counting When Numbers Are Equal

When two numbers in the array are identical, there's a risk of counting them incorrectly if not careful about when to update the frequency counter.

Wrong approach: Updating frequency before checking for matches would cause a number to match with itself.

Solution: Always check for matches with previously seen numbers first, then update the frequency counter for the current number.

4. Not Handling Leading Zeros Correctly

When swapping digits results in leading zeros (e.g., 100 → 001), the conversion to integer automatically removes them (001 becomes 1). This is actually the desired behavior, but developers might mistakenly try to preserve leading zeros or handle them separately.

Solution: Trust Python's int() conversion to handle leading zeros correctly - int("001") automatically becomes 1, which is the intended behavior for this problem.