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:
x or y and 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:
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] <= 106In #3265 Count Almost Equal Pairs I, two numbers are considered almost equal if one number can become the other by performing at most one swap of two digits within the number. A practical way to detect such pairs is to treat each number as a string and enumerate all possible results obtained after swapping any two positions.
Use a hash map to store how many times each number has appeared while iterating through the array. For the current number, generate all unique variants created by performing one swap (and also include the original number for the no‑swap case). If any of these variants already exist in the map, they form valid pairs.
To avoid duplicate work, store generated variants in a set before checking the map. Since the number of digits is small, generating all swap combinations is efficient. Overall, the method combines enumeration + hashing to efficiently count valid pairs while scanning the array once.
The time complexity mainly depends on the number of digits per number, leading to roughly O(n * d^2) operations, where d is the digit length.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Hash Map with Digit Swap Enumeration | O(n * d^2) | O(n) |
NeetCodeIO
Use these hints if you're stuck. Try solving on your own first.
Since the constraint on the number of elements is small, you can check all pairs in the array.
For each pair, perform an operation on one of the elements and check if it becomes equal to the other.
Watch expert explanations and walkthroughs
Jot down your thoughts, approach, and key learnings
Yes, problems like this are common in coding interviews because they test hashing, string manipulation, and combinational enumeration. Similar patterns appear in interviews at large tech companies where candidates must optimize brute-force comparisons.
A hash map (or dictionary) is the most effective data structure because it allows constant-time lookups for previously seen numbers. Combined with a set to avoid duplicate swap results, it ensures efficient pair counting.
The optimal approach uses a hash map along with digit swap enumeration. For each number, generate all possible strings formed by swapping two digits and check whether any of those forms have already appeared in the array. This allows efficient counting of valid pairs in near linear time with respect to the array size.
Generating all possible swaps simulates the operation allowed by the problem: swapping any two digits once. By enumerating these possibilities, we can quickly determine whether a previously seen number can match the current number after one swap.