Watch 8 video solutions for Count Almost Equal Pairs II, a hard level problem involving Array, Hash Table, Sorting. This walkthrough by Abhinav Awasthi has 5,304 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
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 = [1023,2310,2130,213]
Output: 4
Explanation:
The almost equal pairs of elements are:
Example 2:
Input: nums = [1,10,100]
Output: 3
Explanation:
The almost equal pairs of elements are:
Constraints:
2 <= nums.length <= 50001 <= nums[i] < 107Problem 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 | 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. |