Watch 10 video solutions for Count Almost Equal Pairs I, a medium level problem involving Array, Hash Table, Sorting. This walkthrough by Ayush Rao has 1,239 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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] <= 106Problem 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 | 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 |