# Count Almost Equal Pairs I
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/count-almost-equal-pairs-i)
Canonical: https://scaleengineer.com/dsa/problems/count-almost-equal-pairs-i
**Patterns:** [Counting](https://scaleengineer.com/dsa/patterns/counting), [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Hash Table
**Companies:** [Info Edge](https://scaleengineer.com/companies/info-edge)
---
## Problem
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** `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:

* 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 <= 100`
* `1 <= nums[i] <= 106`

# Approaches
## Brute-Force Pairwise Comparison
This straightforward approach involves checking every possible pair of numbers in the array to see if they are almost equal.
**Time:** O(N^2 * D), where N is the length of the `nums` array and D is the maximum number of digits in a number. The two nested loops result in O(N^2) pairs. For each pair, the `isAlmostEqual` function takes O(D) time for string conversion and comparison. · **Space:** O(D), where D is the maximum number of digits. This space is used by the helper function to store the indices of differing characters.
**Pros:** Simple to understand and implement.; Works well for the given constraints due to the small size of N.
**Cons:** Inefficient for larger input sizes as its time complexity is quadratic.
### Explanation
The algorithm uses two nested loops to iterate through all unique pairs of indices `(i, j)` where `i < j`. For each pair of numbers `(nums[i], nums[j])`, a helper function `isAlmostEqual` is invoked. This function determines if one number can be transformed into the other by at most one swap of digits. It does this by converting the numbers to strings and comparing them. If the strings are identical (zero swaps), they are almost equal. If they differ, the function counts the number of positions with different characters. If there are exactly two differing positions, it verifies if these characters are swapped between the two strings. If this condition holds, the pair is considered almost equal (one swap). A counter is incremented for every almost equal pair found.

```java
class Solution {
    public int countAlmostEqualPairs(int[] nums) {
        int n = nums.length;
        int count = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (isAlmostEqual(nums[i], nums[j])) {
                    count++;
                }
            }
        }
        return count;
    }

    private boolean isAlmostEqual(int x, int y) {
        String s1 = String.valueOf(x);
        String s2 = String.valueOf(y);

        if (s1.length() != s2.length()) {
            return false;
        }

        java.util.List<Integer> diffIndices = new java.util.ArrayList<>();
        for (int i = 0; i < s1.length(); i++) {
            if (s1.charAt(i) != s2.charAt(i)) {
                diffIndices.add(i);
            }
        }

        if (diffIndices.isEmpty()) {
            return true; // The numbers are equal
        }

        if (diffIndices.size() == 2) {
            int i = diffIndices.get(0);
            int j = diffIndices.get(1);
            return s1.charAt(i) == s2.charAt(j) && s1.charAt(j) == s2.charAt(i);
        }

        return false;
    }
}
```
### Algorithm
1. Initialize a counter `count` to 0.
2. Use a nested loop to iterate through every pair of indices `(i, j)` such that `i < j`.
3. For each pair, call a helper function `isAlmostEqual(nums[i], nums[j])`.
4. If the helper function returns `true`, increment `count`.
5. After checking all pairs, return `count`.

**Helper `isAlmostEqual(x, y)`:**
1. Convert `x` and `y` to strings `s1` and `s2`.
2. If their lengths are different, return `false`.
3. Find all indices where `s1` and `s2` differ.
4. If there are 0 differing indices, they are equal, return `true`.
5. If there are 2 differing indices, say `d1` and `d2`, check if `s1[d1] == s2[d2]` and `s1[d2] == s2[d1]`. If true, return `true`.
6. Otherwise, return `false`.

## Frequency Map and Variant Generation
A more efficient approach that avoids redundant comparisons by first counting the frequency of each number. It then calculates pairs by considering identical numbers and by generating potential 'almost equal' variants for each unique number.
**Time:** O(N + U * D^3), where N is the array length, U is the number of unique elements, and D is the maximum number of digits. O(N) is for building the frequency map. The main loop runs U times. Inside, generating variants takes O(D^2) swaps, and each swap involves O(D) work for string/number conversion, leading to O(D^3) per unique number. · **Space:** O(U), where U is the number of unique elements in `nums`. This space is required for the frequency map.
**Pros:** More efficient than the brute-force approach, especially for inputs with many duplicates or larger N.; Reduces redundant computations by processing each unique number only once.
**Cons:** More complex to implement due to the logic for variant generation and handling double-counting.
### Explanation
This method begins by creating a frequency map (e.g., a `HashMap`) of all numbers in the input array. This takes a single pass. Then, it iterates through each unique number `num` and its frequency `c` in the map. The total count of almost equal pairs is built as follows:

1.  **Pairs of identical numbers:** For a number `num` appearing `c` times, there are `c * (c - 1) / 2` pairs of `(num, num)`. These are added to the total since identical numbers are almost equal.
2.  **Pairs of different numbers:** For each `num`, the algorithm generates all possible variants that can be formed by swapping exactly two of its digits. For each generated `variant`, it checks if the `variant` also exists in the frequency map. To prevent double-counting (e.g., counting both `(12, 21)` and `(21, 12)`), we only process pairs where `num < variant`. If such a `variant` exists with frequency `c_variant`, we add `c * c_variant` pairs to the total count.

```java
class Solution {
    public int countAlmostEqualPairs(int[] nums) {
        java.util.Map<Integer, Integer> freqMap = new java.util.HashMap<>();
        for (int num : nums) {
            freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
        }

        long count = 0;
        for (java.util.Map.Entry<Integer, Integer> entry : freqMap.entrySet()) {
            int num = entry.getKey();
            long c = entry.getValue();

            // Case 1: Pairs of the same number (e.g., (12, 12))
            count += c * (c - 1) / 2;

            // Case 2: Pairs with a variant (e.g., (12, 21))
            char[] digits = String.valueOf(num).toCharArray();
            for (int i = 0; i < digits.length; i++) {
                for (int j = i + 1; j < digits.length; j++) {
                    // Swap digits
                    char temp = digits[i];
                    digits[i] = digits[j];
                    digits[j] = temp;

                    int variant = Integer.parseInt(new String(digits));

                    // To avoid double counting, only consider pairs (num, variant) where num < variant
                    if (num < variant && freqMap.containsKey(variant)) {
                        count += c * freqMap.get(variant);
                    }

                    // Swap back to restore original digits for next iteration
                    temp = digits[i];
                    digits[i] = digits[j];
                    digits[j] = temp;
                }
            }
        }
        return (int) count;
    }
}
```
### Algorithm
1. Create a `HashMap` to store the frequency of each number in `nums`.
2. Initialize a counter `count` to 0.
3. Iterate through each unique number `num` and its count `c` in the map.
4. Add `c * (c - 1) / 2` to `count` to account for pairs of identical numbers.
5. Convert `num` to a character array.
6. Use nested loops to generate every `variant` of `num` by swapping two digits at indices `i` and `j`.
7. For each `variant`, if `num < variant` and the `variant` exists in the frequency map, add `c * map.get(variant)` to `count`.
8. Return the total `count`.

# Solutions
### Java

```java
class Solution {
public
  int countPairs(int[] nums) {
    Arrays.sort(nums);
    int ans = 0;
    Map<Integer, Integer> cnt = new HashMap<>();
    for (int x : nums) {
      Set<Integer> vis = new HashSet<>();
      vis.add(x);
      char[] s = String.valueOf(x).toCharArray();
      for (int j = 0; j < s.length; ++j) {
        for (int i = 0; i < j; ++i) {
          swap(s, i, j);
          vis.add(Integer.parseInt(String.valueOf(s)));
          swap(s, i, j);
        }
      }
      for (int y : vis) {
        ans += cnt.getOrDefault(y, 0);
      }
      cnt.merge(x, 1, Integer : : sum);
    }
    return ans;
  }
private
  void swap(char[] s, int i, int j) {
    char t = s[i];
    s[i] = s[j];
    s[j] = t;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int countPairs(vector<int> &nums) {
    sort(nums.begin(), nums.end());
    int ans = 0;
    unordered_map<int, int> cnt;
    for (int x : nums) {
      unordered_set<int> vis = {x};
      string s = to_string(x);
      for (int j = 0; j < s.length(); ++j) {
        for (int i = 0; i < j; ++i) {
          swap(s[i], s[j]);
          vis.insert(stoi(s));
          swap(s[i], s[j]);
        }
      }
      for (int y : vis) {
        ans += cnt[y];
      }
      cnt[x]++;
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def countPairs(self, nums: List[int]) -> int: nums . sort() ans = 0 cnt = defaultdict(int) for x in nums: vis = {x} s = list(str(x)) for j in range(len(s)): for i in range(j): s[i], s[j] = s[j], s[i] vis . add(int("" . join(s))) s[i], s[j] = s[j], s[i] ans += sum(cnt[x] for x in vis) cnt[x] += 1 return ans

```