LeetCode 3265 - Count Almost Equal Pairs I

The problem asks us to find the number of index pairs (i, j) in an array nums such that i < j and the integers nums[i] and nums[j] are almost equal.

leetcodemediumarrayhash-tablesortingcountingenumeration

LeetCode Problem 3265

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Sorting, Counting, Enumeration

Solution

Problem Understanding

The problem asks us to find the number of index pairs (i, j) in an array nums such that i < j and the integers nums[i] and nums[j] are almost equal. Two integers are considered almost equal if you can make them equal by swapping any two digits at most once in either of the numbers. This means you are allowed to perform a single digit swap in one of the numbers, but not both, and then check if the numbers match.

The input is an array of positive integers with length between 2 and 100. Each integer is at most 1,000,000, which means the numbers can have up to 7 digits. The output is a single integer representing the count of almost equal pairs.

Important edge cases to consider include arrays where all numbers are identical, numbers with repeated digits, single-digit numbers (where swaps may have no effect), and numbers with differing lengths (swapping cannot change the number of digits).

Approaches

A brute-force approach would involve comparing every pair of numbers (i, j) in the array. For each pair, you would try all possible digit swaps in either number and check if they can become equal. This approach is correct but inefficient because the number of pairs is O(n²), and generating all swaps for numbers with up to 7 digits could be expensive.

The key observation for a better solution is that two numbers are almost equal if they share the same digit counts or differ in exactly two positions when sorted. Instead of checking every swap explicitly, we can represent each number as a digit frequency map. For single-digit numbers, or numbers where a swap would create equality, comparing these digit frequency maps allows us to efficiently check almost equality. This reduces the complexity significantly because we only need to compute the digit counts once per number and compare them for each pair.

Approach Time Complexity Space Complexity Notes
Brute Force O(n² * d²) O(d) Compare all pairs and try all digit swaps, where d is number of digits
Optimal O(n² * d) O(n * d) Use digit frequency arrays and compare them directly without generating swaps

Algorithm Walkthrough

  1. Convert each number in nums into a digit frequency list of length 10, where each index represents the count of that digit. This allows constant-time comparison of digit content.
  2. Initialize a counter count to zero.
  3. Loop over all pairs (i, j) in nums with i < j.
  4. For each pair, compare their digit frequency lists. If the frequency lists are identical, increment the counter.
  5. If they are not identical, check if swapping any two digits in one of the numbers could match the other. This is equivalent to checking if the two frequency lists differ in exactly two positions with difference of ±1 in those positions.
  6. Return the final count.

Why it works: By representing numbers as digit frequency arrays, we capture all possible rearrangements of digits. Almost equality requires either identical digit counts or exactly two digits swapped, which is directly captured by comparing the arrays. This guarantees correctness without explicitly performing swaps.

Python Solution

from typing import List

class Solution:
    def countPairs(self, nums: List[int]) -> int:
        def digit_count(n: int) -> List[int]:
            count = [0] * 10
            for digit in str(n):
                count[int(digit)] += 1
            return count
        
        n = len(nums)
        counts = [digit_count(num) for num in nums]
        result = 0
        
        for i in range(n):
            for j in range(i + 1, n):
                diff = 0
                for d in range(10):
                    diff += abs(counts[i][d] - counts[j][d])
                if diff <= 2:
                    result += 1
        
        return result

The Python code first converts each number into a digit frequency array. Then it iterates through all pairs of numbers, calculating the total absolute difference in digit counts. If the difference is at most 2, the numbers are almost equal, and the counter is incremented. Finally, the count is returned.

Go Solution

func countPairs(nums []int) int {
    n := len(nums)
    
    digitCount := func(num int) [10]int {
        var count [10]int
        for num > 0 {
            count[num % 10]++
            num /= 10
        }
        return count
    }
    
    counts := make([][10]int, n)
    for i, num := range nums {
        counts[i] = digitCount(num)
    }
    
    result := 0
    for i := 0; i < n; i++ {
        for j := i + 1; j < n; j++ {
            diff := 0
            for d := 0; d < 10; d++ {
                if counts[i][d] > counts[j][d] {
                    diff += counts[i][d] - counts[j][d]
                } else {
                    diff += counts[j][d] - counts[i][d]
                }
            }
            if diff <= 2 {
                result++
            }
        }
    }
    
    return result
}

In Go, we use arrays of length 10 for digit counts. We iterate over pairs and compute the sum of absolute differences. If the sum is at most 2, the pair is almost equal. The main differences are handling arrays instead of lists and explicit integer division for digits.

Worked Examples

For nums = [3,12,30,17,21]:

i j nums[i] nums[j] Digit diff sum Almost equal?
0 1 3 12 2 No
0 2 3 30 2 Yes
0 3 3 17 4 No
0 4 3 21 2 No
1 4 12 21 2 Yes

Count = 2.

Complexity Analysis

Measure Complexity Explanation
Time O(n² * d) We compare every pair of numbers (O(n²)) and for each pair, we check the 10-digit count array (d ≤ 10)
Space O(n * d) Store the digit count array for each number

Even though n² seems expensive, n ≤ 100 makes it feasible. Digit counts are constant length arrays, so memory usage is minimal.

Test Cases

# Provided examples
assert Solution().countPairs([3,12,30,17,21]) == 2  # Example 1
assert Solution().countPairs([1,1,1,1,1]) == 10    # Example 2
assert Solution().countPairs([123,231]) == 0       # Example 3

# Edge cases
assert Solution().countPairs([1,10]) == 1          # Single digit vs two-digit with leading zero
assert Solution().countPairs([111,111]) == 1       # Identical numbers
assert Solution().countPairs([12,21,13,31]) == 4   # Multiple swappable pairs
assert Solution().countPairs([10,100,1000]) == 0   # Different lengths, no almost equal pairs
Test Why
[3,12,30,17,21] Tests standard swaps between two numbers
[1,1,1,1,1] Tests all identical numbers (full combinatorial count)
[123,231] Tests numbers that cannot match with a single swap
[1,10] Tests single-digit vs two-digit number
[111,111] Tests identical multi-digit numbers
[12,21,13,31] Tests multiple valid pairs
[10,100,1000] Tests numbers of different lengths with no swaps

Edge Cases

One edge case is numbers of different lengths, e.g., 3 and 30. Even though swapping digits might create a number with leading zeros, our digit count approach handles it because it counts zeros as digits. Another edge case is single-digit numbers, where no swap is possible; the algorithm still correctly identifies equality without swaps. A third edge case involves numbers with repeated digits, such as 111 and 111, where swaps do not change the number; the algorithm counts them as almost equal. Our digit frequency representation ensures these scenarios are correctly handled without additional branching logic.