Count Almost Equal Pairs II - Solution & Explanation
Problem Statement
Attention: In this version, the number of operations that can be performed, has been increased to twice.
You are given an array nums consisting of positive integers.
We call two integers x and y almost equal if both integers can become equal after performing the following operation at most twice:
- Choose either
xoryand swap any two digits within the chosen number.
Return the number of indices i and j in nums where i < j such that nums[i] and nums[j] are almost equal.
Note that it is allowed for an integer to have leading zeros after performing an operation.
Example 1:
Input: nums = [1023,2310,2130,213]
Output: 4
Explanation:
The almost equal pairs of elements are:
- 1023 and 2310. By swapping the digits 1 and 2, and then the digits 0 and 3 in 1023, you get 2310.
- 1023 and 213. By swapping the digits 1 and 0, and then the digits 1 and 2 in 1023, you get 0213, which is 213.
- 2310 and 213. By swapping the digits 2 and 0, and then the digits 3 and 2 in 2310, you get 0213, which is 213.
- 2310 and 2130. By swapping the digits 3 and 1 in 2310, you get 2130.
Example 2:
Input: nums = [1,10,100]
Output: 3
Explanation:
The almost equal pairs of elements are:
- 1 and 10. By swapping the digits 1 and 0 in 10, you get 01 which is 1.
- 1 and 100. By swapping the second 0 with the digit 1 in 100, you get 001, which is 1.
- 10 and 100. By swapping the first 0 with the digit 1 in 100, you get 010, which is 10.
Constraints:
2 <= nums.length <= 50001 <= nums[i] < 107
Approach Overview
Problem Overview: You are given an array of integers. Two numbers form an almost equal pair if you can make them identical by swapping digits within the numbers. The task is to count how many index pairs (i, j) with i < j satisfy this condition.
The key observation: digit swaps never change which digits appear in the number. Only their order changes. That means any valid pair must share the same digit multiset. This invariant allows grouping numbers by their digit composition instead of explicitly simulating swaps.
Approach 1: Digit Frequency Count (O(n · d), Space: O(n))
Convert every number into a canonical representation based on its digit frequencies. Build an array of size 10 and count how many times each digit appears. Serialize this frequency vector (for example, as a tuple or string) and use it as a key in a hash map. While iterating through the input, check how many numbers with the same frequency signature were already seen and add that count to the answer. Then increment the frequency in the map. This approach avoids sorting and uses constant-size digit arrays, making it efficient when numbers contain many digits. It relies on fast hash table lookups and simple counting.
Approach 2: Sorting Digits (O(n · d log d), Space: O(n))
Another way to create a canonical form is by sorting the digits of each number. Convert the number to a string, sort the characters, and use the sorted result as a key in a hash map. Numbers that can become equal through digit swaps will share the same sorted representation. As you process the array, maintain counts of previously seen keys and accumulate pair counts. This approach is straightforward to implement and commonly used in sorting-based grouping problems, though sorting introduces a small log d factor.
Both approaches effectively transform the problem into counting pairs of numbers with identical digit compositions. The remaining work is simple frequency aggregation using arrays and hashing.
Recommended for interviews: The digit frequency count approach. It shows you understand the invariant preserved by digit swaps and avoids unnecessary sorting. Starting with the sorted-digit grouping method demonstrates the core insight, but the frequency-vector solution highlights optimization and stronger algorithmic thinking.
Approach 1: Digit Frequency Count
This approach leverages the idea that two numbers are almost equal if their digits can be rearranged (swapping within the number) into identical sequences, at most through two operations. By identifying the permutation condition, we can count the frequency of each digit 0-9. Two numbers are almost equal if their frequency distributions of digits are identical and can be achieved through a maximum of two swaps.
This Python solution first computes the digit frequency of each number using the Counter from the collections module. It then compares the frequency maps of all pairs of numbers in nums. If they match, the pair is considered as almost equal, incrementing the count.
Complexity
Time Complexity: O(n*m) where n is the length of nums and m is the average number of digits per number, due to the frequency computation and pair comparison.
Space Complexity: O(n*m) for storing the frequency counts of each number.
Approach 2: Sorting Digits
This method compares numbers by sorting their digits. If two numbers can be rearranged into the same digit sequence (via sorting), they are 'almost equal'. This approach is more straightforward, leveraging the properties of sorted digit sequences to determine equivalence.
This Python function converts each number into its sorted digit form, storing it in a list. Pairwise checks determine if two numbers, once sorted, have identical digit sequences, being almost equal.
Complexity
Time Complexity: O(n*m log m), influenced by the sorting of digits in each number where n is size of nums and m is number of digits.
Space Complexity: O(n*m), due to sorted numbers storage.
Approach 3: Sorting + Enumeration
We can enumerate each number, and for each number, we can enumerate each pair of different digits, then swap these two digits to get a new number. Record this new number in a hash table vis, representing all possible numbers after at most one swap. Then continue to enumerate each pair of different digits, swap these two digits to get a new number, and record it in the hash table vis, representing all possible numbers after at most two swaps.
This enumeration may miss some pairs of numbers, such as [100, 1], because the number obtained after swapping 100 is 1, and the previously enumerated numbers do not include 1, so some pairs of numbers will be missed. We only need to sort the array before enumeration to solve this problem.
The time complexity is O(n times (log n + log^5 M)), and the space complexity is O(n + log^4 M). Here, n is the length of the array nums, and M is the maximum value in the array nums.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Digit Frequency Count | Time Complexity: O(n*m) where n is the length of |
| Sorting Digits | Time Complexity: O(n*m log m), influenced by the sorting of digits in each number where n is size of |
| Sorting + Enumeration | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Digit Frequency Count | O(n · d) | O(n) | Best general solution. Avoids sorting and works efficiently when numbers contain many digits. |
| Sorting Digits | O(n · d log d) | O(n) | Simpler implementation when digit count is small and code clarity is preferred. |
Video Solution
A-D | Leetcode Weekly Contest 412 Editorials | Count Almost Equal Pairs II | Abhinav Awasthi • Abhinav Awasthi • 5,317 views views
Watch 7 more video solutions →Frequently Asked Questions
Is Count Almost Equal Pairs II easy or hard?
Count Almost Equal Pairs II Python/Java solution
How to solve Count Almost Equal Pairs II in O(n)?
What is the best approach for Count Almost Equal Pairs II?
Is Count Almost Equal Pairs II asked at Google/Amazon/Meta?
What data structure is used in Count Almost Equal Pairs II?
What is the time complexity of Count Almost Equal Pairs II?
Ready to solve this problem?
Practice Count Almost Equal Pairs II with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor