Problem Description

You are given an array nums consisting of positive integers.

Two integers x and y are called almost equal if they 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.

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

Important Notes:

• Leading zeros are allowed after performing a swap operation (e.g., swapping digits in 100 could result in 001 which equals 1)
• The operation can be performed 0, 1, or 2 times total across both numbers
• Each operation involves swapping exactly two digits within one chosen number

Example scenarios:

• Numbers 123 and 321 are almost equal (swap digits in position 0 and 2 of either number)
• Numbers 100 and 1 are almost equal (swap any two zeros in 100 to get 001 = 1)
• Numbers that differ by more than what two swaps can fix are not almost equal

The solution involves:

1. Sorting the array first to handle cases where smaller numbers (like 1) need to be compared with larger numbers (like 100)
2. For each number, generating all possible numbers that can be obtained by performing at most 2 digit swaps
3. Using a hash table to count occurrences and find matching pairs
4. The sorting ensures that when processing a number, all potentially matching smaller numbers have already been processed and counted

Intuition

The key insight is that we need to find all pairs of numbers that can be made equal through at most 2 digit swaps. The naive approach would be to compare every pair of numbers and check if they can be made equal, but this would be inefficient.

Instead, we can think of it differently: for each number, what are all the possible numbers it could become after 0, 1, or 2 swaps? If we can generate this set of possibilities, then we can check if any previously seen numbers match these possibilities.

Why do we need sorting? Consider the pair (100, 1). When we swap digits in 100, we can get 001 which equals 1. However, if we process 1 first, we won't find 100 in our generated possibilities from 1 (since 1 has only one digit). But if we process 100 first, we can generate 1 from it. Sorting ensures larger numbers are processed after smaller ones, allowing us to catch all such pairs.

The generation strategy works as follows:

• First, include the original number (0 swaps)
• Then, try all possible single swaps: for each pair of positions (i, j), swap them and add the result
• For two swaps, we need to be careful: after making the first swap at positions (i, j), we make a second swap at different positions (p, q) where p and q are both different from the currently swapped positions

By maintaining a counter cnt that tracks how many times we've seen each number configuration, we can efficiently count pairs. When processing a number x, we:

1. Generate all its possible variations
2. Check how many of these variations we've seen before (sum up their counts)
3. Add x itself to our counter for future numbers to match against

This approach ensures we count each valid pair exactly once since we process numbers in sorted order and only look backward (at previously processed numbers).

Learn more about Sorting patterns.

Solution Approach

The implementation follows these steps:

1. Sort the array: First, we sort nums to ensure we process smaller numbers before larger ones. This handles edge cases like (100, 1) where the larger number can transform into the smaller one.

2. Initialize data structures:

   • ans: Counter for the number of valid pairs
   • cnt: A defaultdict(int) that tracks how many times we've seen each number configuration

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

   a. Create a set of all possible variations: Initialize vis = {x} to store all numbers that x can become after at most 2 swaps.

   b. Convert to string for digit manipulation: Convert x to a list of characters s = list(str(x)) with length m.

   c. Generate all single-swap variations:

   for j in range(m):
       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
           # ... (two-swap logic here)
           s[i], s[j] = s[j], s[i]  # Swap back to restore original

   d. Generate all two-swap variations: After making the first swap (i, j), we make a second swap:

   for q in range(i + 1, m):
       for p in range(i + 1, q):
           s[p], s[q] = s[q], s[p]  # Second swap
           vis.add(int("".join(s)))
           s[p], s[q] = s[q], s[p]  # Undo second swap

   The condition p, q > i ensures we don't interfere with the first swap at positions (i, j).

4. Count matching pairs: After generating all variations in vis, we count how many times these variations have been seen before:

   ans += sum(cnt[x] for x in vis)

   This adds the count of all previously processed numbers that match any variation of the current number.

5. Update the counter: Add the current number to cnt for future matching:

   cnt[x] += 1

6. Return the result: The total count ans represents all valid pairs (i, j) where i < j and nums[i] and nums[j] are almost equal.

The time complexity is O(n * d^4) where n is the array length and d is the maximum number of digits, since we have four nested loops for generating variations. The space complexity is O(n * d^4) for storing all possible variations in the counter.

Example Walkthrough

Let's walk through the algorithm with nums = [100, 1, 100, 12, 21].

Step 1: Sort the array After sorting: nums = [1, 12, 21, 100, 100]

Step 2: Process each number

Processing nums[0] = 1:

• Generate variations: vis = {1} (single digit, no swaps possible)
• Check counter: sum(cnt[x] for x in {1}) = 0 (no matches yet)
• Update: ans = 0, cnt[1] = 1

Processing nums[1] = 12:

• Original: vis = {12}
• Single swap (positions 0,1): swap '1' and '2' → get 21
• Variations: vis = {12, 21}
• Check counter: cnt[12] = 0, cnt[21] = 0, sum = 0
• Update: ans = 0, cnt[12] = 1

Processing nums[2] = 21:

• Original: vis = {21}
• Single swap (positions 0,1): swap '2' and '1' → get 12
• Variations: vis = {21, 12}
• Check counter: cnt[21] = 0, cnt[12] = 1, sum = 1 (found match with previous 12!)
• Update: ans = 1, cnt[21] = 1

Processing nums[3] = 100:

• Original: vis = {100}
• Single swaps:
  • Swap positions (0,1): '1' and '0' → 010 = 10
  • Swap positions (0,2): '1' and '0' → 001 = 1
  • Swap positions (1,2): '0' and '0' → 100 (no change)
• Variations: vis = {100, 10, 1}
• Check counter: cnt[100] = 0, cnt[10] = 0, cnt[1] = 1, sum = 1 (found match with 1!)
• Update: ans = 2, cnt[100] = 1

Processing nums[4] = 100:

• Original: vis = {100}
• Single swaps: (same as above)
• Variations: vis = {100, 10, 1}
• Check counter: cnt[100] = 1, cnt[10] = 0, cnt[1] = 1, sum = 2 (matches with previous 100 and 1!)
• Update: ans = 4, cnt[100] = 2

Final Result: ans = 4

The pairs are:

• (1, 2): nums[1]=12 and nums[2]=21
• (0, 3): nums[0]=1 and nums[3]=100
• (0, 4): nums[0]=1 and nums[4]=100
• (3, 4): nums[3]=100 and nums[4]=100

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × (log n + log^5 M))

Breaking down the analysis:

• Sorting takes O(n log n)
• For each of the n elements:
  • Converting number to string takes O(log M) where M is the maximum value (number of digits)
  • The nested loops iterate through all pairs of digit positions: O(m^2) where m = O(log M)
  • Inner nested loops for second swap: O(m^2)
  • Total swapping operations: O(m^4) = O(log^4 M)
  • Each swap operation involves string manipulation and integer conversion: O(log M)
  • Therefore, generating all variations: O(log^4 M × log M) = O(log^5 M)
  • The vis set can contain at most O(log^4 M) elements (all possible swaps)
  • Summing counts from dictionary: O(|vis|) = O(log^4 M)
• Overall: O(n log n) + O(n × log^5 M) = O(n × (log n + log^5 M))

Space Complexity: O(n + log^4 M)

Breaking down the analysis:

• The cnt dictionary stores at most n unique values: O(n)
• The vis set for each number stores all possible variations from swapping operations
• Maximum size of vis: O(log^4 M) (all possible combinations of at most 2 swaps)
• String s for digit manipulation: O(log M)
• Overall: O(n + log^4 M)

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

Common Pitfalls

1. Incorrect Loop Boundaries for Second Swap

The Pitfall: A common mistake is using incorrect loop boundaries when generating the second swap combinations. Many developers might write:

# INCORRECT - allows interference with first swap
for fourth_pos in range(num_digits):
    for third_pos in range(fourth_pos):

This allows the second swap to potentially involve positions already used in the first swap (positions first_pos and second_pos), which would either:

• Undo the first swap if we swap the same positions again
• Create an invalid state where we're effectively doing 3 position changes instead of 4 distinct positions

The Solution: Ensure the second swap only considers positions that come after the first position involved in the initial swap:

# CORRECT - ensures no interference
for fourth_pos in range(first_pos + 1, num_digits):
    for third_pos in range(first_pos + 1, fourth_pos):

2. Forgetting to Process Numbers in Sorted Order

The Pitfall: Processing the array without sorting can miss valid pairs where a larger number can transform into a smaller one through swaps. For example:

• Array: [100, 1]
• Without sorting: When processing 100 first, we haven't seen 1 yet, so we miss the pair
• The number 100 can become 001 (which equals 1) by swapping zeros

The Solution: Always sort the array first to ensure smaller numbers are processed before larger ones:

nums.sort()  # Critical for correctness

3. Not Handling Leading Zeros Correctly

The Pitfall: Developers might think that numbers with leading zeros are invalid or try to handle them specially. For instance, they might avoid creating numbers like 001 from 100.

The Solution: Python's int() function automatically handles leading zeros correctly:

int("001")  # Returns 1, not an error
int("00123")  # Returns 123

No special handling is needed - just convert the string directly to an integer.

4. Double Counting or Missing the Original Number

The Pitfall: Forgetting to include the original number itself in the set of reachable numbers (when 0 swaps are performed):

# INCORRECT - missing the original number
reachable_numbers = set()  # Should include current_num

The Solution: Initialize the reachable set with the original number:

reachable_numbers = {current_num}  # Includes 0-swap case

5. Inefficient String Conversions

The Pitfall: Converting between string and integer repeatedly inside the innermost loops:

# INEFFICIENT - converts to string multiple times
for j in range(m):
    for i in range(j):
        s = list(str(x))  # Converting inside the loop
        s[i], s[j] = s[j], s[i]
        vis.add(int("".join(s)))

The Solution: Convert once outside the loops and maintain the character list:

digits = list(str(current_num))  # Convert once
for second_pos in range(num_digits):
    for first_pos in range(second_pos):
        # Work with the same list, swap and swap back
        digits[first_pos], digits[second_pos] = digits[second_pos], digits[first_pos]
        # ... operations ...
        digits[first_pos], digits[second_pos] = digits[second_pos], digits[first_pos]  # Restore