Count Almost Equal Pairs I - Solution & Explanation
Problem Statement
You are given an array nums consisting of positive integers.
We call two integers x and y in this problem almost equal if both integers can become equal after performing the following operation at most once:
- 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 = [3,12,30,17,21]
Output: 2
Explanation:
The almost equal pairs of elements are:
- 3 and 30. By swapping 3 and 0 in 30, you get 3.
- 12 and 21. By swapping 1 and 2 in 12, you get 21.
Example 2:
Input: nums = [1,1,1,1,1]
Output: 10
Explanation:
Every two elements in the array are almost equal.
Example 3:
Input: nums = [123,231]
Output: 0
Explanation:
We cannot swap any two digits of 123 or 231 to reach the other.
Constraints:
2 <= nums.length <= 1001 <= nums[i] <= 106
Approach Overview
Problem Overview: You are given an array of integers and need to count pairs (i, j) where i < j and the two numbers can become equal after performing at most one swap of digits in one of them. Treat numbers as digit strings and compare their positions to determine whether a single swap can make them identical.
Approach 1: Digit Frequency Comparison (O(n² · d) time, O(1) space)
Compare every pair of numbers directly. Convert numbers to strings and pad with leading zeros so both have the same length. Iterate through the digits and record positions where they differ. If there are zero differences, the numbers are already equal. If there are exactly two mismatched positions and swapping those digits would align the numbers, the pair is valid. A quick digit frequency check can reject pairs that do not share the same digit multiset before performing the swap validation. This method relies on straightforward array-style iteration over digits.
Approach 2: Digit Frequency Comparison with Counting (O(n · d log d) time, O(n) space)
Instead of checking every pair, normalize each number using a digit signature. Sort the digits of each number to create a canonical representation. Numbers that can become equal after a swap must share the same digit frequency pattern. Use a hash table to group numbers by their sorted-digit signature. Inside each group, perform the mismatch check to confirm that at most one swap makes the numbers identical. This reduces unnecessary comparisons because only candidates with identical digit composition are evaluated.
Approach 3: Direct Permutation Check (O(n · d²) time, O(n) space)
For each number, generate every possible value obtainable with a single digit swap. There are at most d(d-1)/2 such permutations for a number with d digits. Store previously seen numbers in a hash set and check whether any generated permutation exists. If it does, you found an almost-equal pair. This approach uses explicit enumeration of swaps rather than validating mismatches.
Recommended for interviews: The digit mismatch method is the most expected solution. It directly models the constraint of a single swap and keeps the logic simple. Starting with the pairwise comparison shows understanding of the problem definition, while adding signature grouping or hash filtering demonstrates optimization and strong problem-solving instincts.
Approach 1: Digit Frequency Comparison
Two numbers can be almost equal if the frequency of each digit is the same, with at most one anomaly to allow a single swap. We can use this idea to compare each pair of numbers.
The approach is to go through each pair of numbers, calculate the frequency of each digit (0-9), and check if the number frequencies are similar when allowing one mismatched pair.
This solution compares the digit frequency of two numbers using the Counter class and checks if they can be made equal by allowing a single swap. The key operation checks if the absolute differences between digit counts are minor when summed.
Complexity
Time Complexity: O(n^2 * k) where n is the number of elements and k is the maximum number of digits in a number.
Space Complexity: O(1) for fixed size Counter handling from 0 to 9.
Approach 2: Direct Permutation Check
This approach directly considers whether the digits of one number can be rearranged to form another without explicitly counting mismatches. It essentially checks if two numbers are permutations allowing a single swap.
The method involves generating a list of permutations and comparing against the other number.
This JavaScript solution creates a set of permutations for each number and checks against subsequent numbers if they can be generated by permutations, storing them in a set to compare.
Code
JavaScript
Complexity
Time Complexity: Complex due to heavy permutation generation; exponential nature is expected (O(n!)) for digits per input number.
Space Complexity: O(permutations generated).
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. We record this new number in a hash table s, representing all possible numbers after at most one swap. Then, we count how many numbers previously enumerated are in the hash table s and add this count to the answer. Next, we add the currently enumerated number to the hash table cnt, representing the count of the current number.
This enumeration method may miss some pairs, such as [100, 1], because the number obtained by swapping digits in 100 is 1, and previously enumerated numbers do not include 1, thus missing some pairs. We can solve this problem by sorting the array before enumeration.
The time complexity is O(n times (log n + log^3 M)), and the space complexity is O(n + log^2 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 Comparison | Time Complexity: O(n^2 * k) where n is the number of elements and k is the maximum number of digits in a number. |
| Direct Permutation Check | Time Complexity: Complex due to heavy permutation generation; exponential nature is expected (O(n!)) for digits per input number. |
| Sorting + Enumeration | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Digit Mismatch Comparison | O(n² · d) | O(1) | Small input sizes or when implementing the simplest interview solution |
| Digit Frequency Grouping | O(n · d log d) | O(n) | General case optimization to reduce unnecessary pair comparisons |
| Direct Permutation Enumeration | O(n · d²) | O(n) | When you prefer generating possible swaps and validating via hash lookup |
Video Solution
3265 Count Almost Equal Pairs I || Critical Thinking 🔥 || How to 🤔 in Interview || Simulation • Ayush Rao • 1,257 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Count Almost Equal Pairs I easy or hard?
Count Almost Equal Pairs I Python/Java solution
How to solve Count Almost Equal Pairs I in O(n)?
What is the best approach for Count Almost Equal Pairs I?
Is Count Almost Equal Pairs I asked at Google/Amazon/Meta?
What data structure is used in Count Almost Equal Pairs I?
What is the time complexity of Count Almost Equal Pairs I?
Ready to solve this problem?
Practice Count Almost Equal Pairs I with our built-in code editor and test cases.
Practice on FleetCode