LeetCode 3267 - Count Almost Equal Pairs II
We are given an array nums containing positive integers. We need to count how many pairs of indices (i, j) with i < j satisfy a special condition called almost equal.
Difficulty: 🔴 Hard
Topics: Array, Hash Table, Sorting, Counting, Enumeration
Solution
LeetCode 3267 - Count Almost Equal Pairs II
Problem Understanding
We are given an array nums containing positive integers. We need to count how many pairs of indices (i, j) with i < j satisfy a special condition called almost equal.
Two numbers x and y are considered almost equal if we can make them equal by performing at most two digit swap operations on one of the numbers. A swap operation selects any two digit positions inside the same number and exchanges them.
A very important detail is that leading zeros are allowed after swaps. For example:
100can become001, which represents the integer1.213can be viewed as0213when compared with a 4-digit number.
The constraints are:
2 <= nums.length <= 50001 <= nums[i] < 10^7
Since every number contains at most 7 digits, the digit length is very small. However, the array length can be as large as 5000, making an O(n²) pairwise comparison approach far too expensive.
The key challenge is efficiently determining whether two numbers can be transformed into one another using at most two swaps.
Important observations:
- Any sequence of at most two swaps affects only a small number of digit positions.
- Numbers with different digit multisets can never become equal.
- Leading zeros mean we can safely pad all numbers to the same length before analyzing swaps.
- Since values are bounded by
10^7, every padded representation has length at most 7.
Approaches
Brute Force
The most direct approach is to examine every pair (i, j).
For each pair:
- Convert both numbers into equal-length digit strings.
- Determine whether one can be transformed into the other using at most two swaps.
- Count the pair if the answer is yes.
There are O(n²) pairs. With n = 5000, this produces roughly 12.5 million comparisons.
Even though each comparison only involves at most 7 digits, the total work becomes too large.
Key Insight
The digit length is tiny, at most 7.
Instead of checking every pair, we can process numbers one by one and generate all numbers reachable within at most two swaps.
For a fixed 7-digit string:
- Zero swaps produces 1 configuration.
- One swap produces at most
C(7,2)=21configurations. - Two swaps produce at most
21 × 21 = 441configurations.
Thus the total number of reachable states is bounded by a small constant.
While iterating through the array, we maintain a frequency map of numbers already seen.
For the current number:
- Generate every value reachable within two swaps.
- Every previously seen occurrence of one of those values forms a valid pair.
- Add the current number to the frequency map.
This transforms the problem into a counting problem using a hash map.
Approach Comparison
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n² · d) | O(d) | Compare every pair directly |
| Optimal | O(n · d⁴) | O(U) | Generate all states reachable within two swaps, where d ≤ 7 |
Here d is the digit length and U is the number of distinct values encountered.
Since d ≤ 7, d⁴ is effectively a small constant.
Algorithm Walkthrough
- Determine the maximum digit length among all numbers.
We pad every number to this length using leading zeros. This allows numbers such as 213 and 0213 to be compared consistently.
2. Process the numbers from left to right.
We maintain a hash map count storing how many times each original integer has already appeared.
3. For the current number, convert it to its padded digit representation.
This representation will be used to generate all reachable configurations. 4. Generate all configurations obtainable with zero, one, or two swaps.
Start with the original digit arrangement.
Then enumerate every pair of positions (i, j) and perform one swap.
From every resulting arrangement, enumerate every second swap. 5. Convert each generated digit arrangement back into an integer.
Leading zeros naturally disappear when converting to an integer. 6. Store all reachable integers in a set.
Multiple swap sequences may produce the same value, so deduplication is necessary.
7. For every reachable value v, add count[v] to the answer.
Every previous occurrence of v forms a valid pair with the current number.
8. After counting pairs, insert the current number into the frequency map.
Future numbers will be able to match against it. 9. Continue until all numbers have been processed.
Why it works
For every number, we explicitly enumerate every digit arrangement reachable using zero, one, or two swaps. Any number that can become equal to the current number within two swaps must correspond to one of these generated states.
Because we only count occurrences that appeared earlier in the array, every valid pair is counted exactly once. The reachable-state generation is exhaustive, so no valid pair is missed.
Python Solution
from typing import List
from collections import defaultdict
class Solution:
def countPairs(self, nums: List[int]) -> int:
max_len = len(str(max(nums)))
freq = defaultdict(int)
answer = 0
for num in nums:
digits = list(str(num).zfill(max_len))
reachable = set()
reachable.add(int("".join(digits)))
n = len(digits)
for i in range(n):
for j in range(i + 1, n):
arr1 = digits[:]
arr1[i], arr1[j] = arr1[j], arr1[i]
reachable.add(int("".join(arr1)))
for p in range(n):
for q in range(p + 1, n):
arr2 = arr1[:]
arr2[p], arr2[q] = arr2[q], arr2[p]
reachable.add(int("".join(arr2)))
for value in reachable:
answer += freq[value]
freq[num] += 1
return answer
Implementation Explanation
The solution first determines the maximum digit length and uses zfill() so that all numbers are represented with the same number of digits.
For each number, a set named reachable stores every integer obtainable through at most two swaps.
The original arrangement is inserted first, representing zero swaps.
The outer pair of loops enumerates every possible first swap. After performing that swap, the resulting value is added to the reachable set.
Another nested pair of loops enumerates every possible second swap. Each resulting arrangement is converted back to an integer and inserted into the set.
Once all reachable values have been generated, the algorithm checks how many times each value has appeared previously using the frequency map. Those occurrences correspond exactly to valid pairs ending at the current position.
Finally, the current number is inserted into the frequency map before moving on to the next element.
Go Solution
package main
func countPairs(nums []int) int {
maxLen := 0
for _, x := range nums {
length := len(intToString(x))
if length > maxLen {
maxLen = length
}
}
freq := make(map[int]int)
answer := 0
for _, num := range nums {
digits := []byte(zfill(intToString(num), maxLen))
n := len(digits)
reachable := make(map[int]struct{})
reachable[toInt(digits)] = struct{}{}
for i := 0; i < n; i++ {
for j := i + 1; j < n; j++ {
arr1 := make([]byte, n)
copy(arr1, digits)
arr1[i], arr1[j] = arr1[j], arr1[i]
reachable[toInt(arr1)] = struct{}{}
for p := 0; p < n; p++ {
for q := p + 1; q < n; q++ {
arr2 := make([]byte, n)
copy(arr2, arr1)
arr2[p], arr2[q] = arr2[q], arr2[p]
reachable[toInt(arr2)] = struct{}{}
}
}
}
}
for v := range reachable {
answer += freq[v]
}
freq[num]++
}
return answer
}
func intToString(x int) string {
if x == 0 {
return "0"
}
buf := make([]byte, 0)
for x > 0 {
buf = append(buf, byte('0'+x%10))
x /= 10
}
for i, j := 0, len(buf)-1; i < j; i, j = i+1, j-1 {
buf[i], buf[j] = buf[j], buf[i]
}
return string(buf)
}
func zfill(s string, length int) string {
if len(s) >= length {
return s
}
buf := make([]byte, length)
padding := length - len(s)
for i := 0; i < padding; i++ {
buf[i] = '0'
}
copy(buf[padding:], s)
return string(buf)
}
func toInt(arr []byte) int {
value := 0
for _, ch := range arr {
value = value*10 + int(ch-'0')
}
return value
}
Go Specific Notes
The Go version uses a map[int]int for frequency counting and a map[int]struct{} as the reachable-state set.
Since leading zeros must be preserved during swap generation, numbers are manipulated as padded byte slices. Conversion back to an integer naturally removes leading zeros.
The maximum possible value remains small, so standard Go int arithmetic is sufficient.
Worked Examples
Example 1
Input:
[1023, 2310, 2130, 213]
Maximum digit length:
4
Padded representations:
| Number | Representation |
|---|---|
| 1023 | 1023 |
| 2310 | 2310 |
| 2130 | 2130 |
| 213 | 0213 |
Processing 1023:
| Reachable Match | Previous Count |
|---|---|
| various values | 0 |
Answer remains:
0
Frequency map:
{1023: 1}
Processing 2310:
The reachable set contains 1023.
| Reachable Value | Previous Count |
|---|---|
| 1023 | 1 |
Answer becomes:
1
Processing 2130:
The reachable set contains 2310.
| Reachable Value | Previous Count |
|---|---|
| 2310 | 1 |
Answer becomes:
2
Processing 0213:
The reachable set contains:
1023
2310
Both have appeared previously.
| Reachable Value | Previous Count |
|---|---|
| 1023 | 1 |
| 2310 | 1 |
Final answer:
4
Example 2
Input:
[1, 10, 100]
Maximum digit length:
3
Representations:
| Number | Representation |
|---|---|
| 1 | 001 |
| 10 | 010 |
| 100 | 100 |
Processing 1:
answer = 0
Processing 10:
Reachable values include:
1
10
100
Previous occurrence of 1 exists.
answer = 1
Processing 100:
Reachable values include:
1
10
100
Previous counts:
1 -> 1 occurrence
10 -> 1 occurrence
Answer increases by 2.
Final answer:
3
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n · d⁴) | For each number, all one-swap and two-swap states are generated |
| Space | O(U) | Frequency map plus a constant-sized reachable set |
Since d ≤ 7, the number of generated states is bounded by a small constant. Therefore the algorithm behaves essentially as linear time with respect to n.
Test Cases
sol = Solution()
assert sol.countPairs([1023, 2310, 2130, 213]) == 4 # official example 1
assert sol.countPairs([1, 10, 100]) == 3 # official example 2
assert sol.countPairs([1, 1]) == 1 # identical values
assert sol.countPairs([123, 123]) == 1 # duplicate numbers
assert sol.countPairs([123, 321]) == 1 # one swap
assert sol.countPairs([1234, 3412]) == 1 # two swaps
assert sol.countPairs([12, 34]) == 0 # impossible transformation
assert sol.countPairs([100, 1]) == 1 # leading zeros
assert sol.countPairs([1000, 10]) == 1 # multiple leading zeros
assert sol.countPairs([111, 111, 111]) == 3 # all equal
assert sol.countPairs([1234, 4321]) == 1 # reachable in two swaps
assert sol.countPairs([123, 456, 789]) == 0 # no matches
assert sol.countPairs([10, 100, 1000]) == 3 # chain through leading zeros
Test Summary
| Test | Why |
|---|---|
[1023,2310,2130,213] |
Official example |
[1,10,100] |
Leading-zero transformations |
[1,1] |
Duplicate values |
[123,123] |
Identical numbers |
[123,321] |
Single swap case |
[1234,3412] |
Exactly two swaps |
[12,34] |
No valid transformation |
[100,1] |
Leading zeros after swaps |
[1000,10] |
Different original lengths |
[111,111,111] |
Repeated identical digits |
[1234,4321] |
Two-swap permutation |
[123,456,789] |
Completely different digits |
[10,100,1000] |
Multiple valid pairs |
Edge Cases
Numbers With Different Lengths
A common mistake is comparing numbers using their raw string forms. Since leading zeros are allowed after swaps, numbers such as 213 and 0213 should be considered equivalent representations during the transformation process. The implementation avoids this issue by padding every number to the global maximum digit length before generating swaps.
Repeated Digits
Numbers like 1111111 produce many swap operations that leave the number unchanged. Without deduplication, the same reachable value could be counted multiple times. The implementation stores all generated results in a set, ensuring each reachable integer contributes at most once.
Multiple Swap Sequences Producing the Same Value
A given target value may be obtainable through several different sequences of two swaps. For example, swapping identical digits or undoing a previous swap can create duplicate states. The reachable-state set removes all duplicates automatically.
Leading Zeros After Swaps
Transformations such as 100 -> 001 are central to the problem. By converting generated digit strings back into integers, leading zeros are naturally discarded, allowing 001 and 1 to be treated as the same value exactly as required by the problem statement.
Large Input Size
With up to 5000 numbers, any pairwise O(n²) comparison strategy is too expensive. The implemented solution processes each number independently and performs only a constant amount of work per element because digit length never exceeds 7. This keeps the algorithm efficient for the maximum input size.