Count Pairs of Numbers That Become Equal After at Most One Digit Swap
Company: Capital One
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
You are given a list of non-negative integers `nums`. Two numbers form a **matching pair** if they are equal, or if you can make them equal by choosing one of the two numbers and swapping two of its digits once.
Return the number of index pairs `(i, j)` with `i < j` such that `nums[i]` and `nums[j]` form a matching pair.
### Function Signature
```python
def count_matching_pairs(nums: list[int]) -> int:
```
### Rules
- A pair gets at most one swap in total, applied to only one of its two numbers. A pair that would need a swap in each number, or two swaps in the same number, does not match.
- A swap exchanges the digits at two different positions of the chosen number's usual decimal form, written without leading zeros.
- The result of a swap may start with one or more zeros. It is read as a number with those leading zeros dropped: swapping the two digits of `30` gives `03`, which equals `3`, so `30` and `3` form a matching pair.
- Swaps are only imagined, never applied: `nums` is not changed, and every pair is judged on the original values.
- Pairs are counted by index, so equal values at different indices form a pair.
### Constraints
- `1 <= len(nums) <= 10000`
- `0 <= nums[i] <= 1000000000`
- The result is an integer from `0` to `len(nums) * (len(nums) - 1) / 2` inclusive, and it is uniquely determined by the input.
### Examples
**Example 1**
- Input: `nums = [4, 123, 452, 321, 132]`
- Output: `2`
- Explanation: `123` and `321` match by swapping the `1` and the `3` of `123`, and `123` and `132` match by swapping its `2` and `3`. `321` and `132` differ in all three positions, so a single swap in either one cannot make them equal. `4` and `452` match nothing.
**Example 2**
- Input: `nums = [30, 3, 12, 21, 12]`
- Output: `4`
- Explanation: The matching index pairs are `(0, 1)` because `30` becomes `03 = 3`, `(2, 3)` and `(3, 4)` because `12` and `21` differ by one swap, and `(2, 4)` because the values are equal.
**Example 3**
- Input: `nums = [100, 1, 10, 1000]`
- Output: `6`
- Explanation: Every pair matches. `100` can become `010 = 10` or `001 = 1`, `10` can become `01 = 1`, and `1000` can become `0100 = 100`, `0010 = 10` or `0001 = 1`.
Overview: Given a list of integers, count the index pairs whose values are equal or become equal after swapping two digits inside one of the two numbers, where leading zeros created by a swap are dropped. It tests digit manipulation, careful handling of numbers with different lengths, and hashing to avoid comparing every pair.
Read the full Capital One Machine Learning Engineer interview experience this question came from
You are given a list of non-negative integers `nums`. Two numbers form a **matching pair** if they are equal, or if they can be made equal by picking one of the two numbers and swapping two of its digits exactly once.
Implement `count_matching_pairs(nums)` and return the number of index pairs `(i, j)` with `i < j` such that `nums[i]` and `nums[j]` form a matching pair.
**Rules**
- A pair gets at most one swap in total, applied to only one of its two numbers. A pair that would need a swap in each number, or two swaps in the same number, does not match.
- A swap exchanges the digits at two different positions of the chosen number's usual decimal form, written without leading zeros. A single-digit number (including `0`) has no swap available.
- The result of a swap may start with one or more zeros. It is read as a number with those leading zeros dropped: swapping the two digits of `30` gives `03`, which equals `3`, so `30` and `3` form a matching pair. Likewise `1000` can become `0100 = 100`, `0010 = 10` or `0001 = 1`.
- Swaps are only imagined, never applied: `nums` is not changed, and every pair is judged on the original values. Matching is not transitive.
- Pairs are counted by index, so equal values at different indices form a pair.
**Output**
Return a single integer: the number of matching index pairs. The answer is uniquely determined by the input.
**Constraints**
- `1 <= len(nums) <= 10000`
- `0 <= nums[i] <= 1000000000`
- The result is an integer from `0` to `len(nums) * (len(nums) - 1) / 2` inclusive (at most `49,995,000`).
- Every input value and the result fit in a 32-bit signed integer (no value exceeds `2^31 - 1`), so `int` is sufficient in Java and C++.
**Example 1**
```
Input: nums = [4, 123, 452, 321, 132]
Output: 2
```
`123` and `321` match by swapping the `1` and the `3` of `123`, and `123` and `132` match by swapping its `2` and `3`. `321` and `132` differ in all three positions, so a single swap in either one cannot make them equal. `4` and `452` match nothing.
**Example 2**
```
Input: nums = [30, 3, 12, 21, 12]
Output: 4
```
The matching index pairs are `(0, 1)` because `30` becomes `03 = 3`, `(2, 3)` and `(3, 4)` because `12` and `21` differ by one swap, and `(2, 4)` because the values are equal.
Constraints
- 1 <= len(nums) <= 10000
- 0 <= nums[i] <= 1000000000
- The result is an integer from 0 to len(nums) * (len(nums) - 1) / 2 inclusive (at most 49,995,000).
- All input values and the result fit in a 32-bit signed integer.
Examples
Input: ([4, 123, 452, 321, 132],)
Expected Output: 2
Explanation: Example 1: 123 matches 321 and 132, but 321 and 132 need two swaps.
Input: ([30, 3, 12, 21, 12],)
Expected Output: 4
Explanation: Example 2: 30 becomes 03 = 3; 12/21 match by one swap; equal 12s match.
Hints
- A number has at most 10 digits, so it has at most 45 single-swap results -- far fewer than the roughly 5 * 10^7 index pairs a 10000-element list can have.
- A swap can shorten a number (leading zeros are dropped) but never lengthen it. If you look at the values in increasing order, which number of a pair is the only one that could ever need the swap?
- Different swaps of the same number can produce the same value (for example when two equal digits are swapped), so make sure each earlier element is counted at most once per later element.