Count Almost Equal Pairs I

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.

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.

1class Solution {2    public int countAlmostEqualPairs(int[] nums) {3        int n = nums.length;4        int count = 0;5        for (int i = 0; i < n; i++) {6            for (int j = i + 1; j < n; j++) {7                if (isAlmostEqual(nums[i], nums[j])) {8                    count++;9                }10            }11        }12        return count;13    }14 15    private boolean isAlmostEqual(int x, int y) {16        String s1 = String.valueOf(x);17        String s2 = String.valueOf(y);18 19        if (s1.length() != s2.length()) {20            return false;21        }22 23        java.util.List<Integer> diffIndices = new java.util.ArrayList<>();24        for (int i = 0; i < s1.length(); i++) {25            if (s1.charAt(i) != s2.charAt(i)) {26                diffIndices.add(i);27            }28        }29 30        if (diffIndices.isEmpty()) {31            return true; // The numbers are equal32        }33 34        if (diffIndices.size() == 2) {35            int i = diffIndices.get(0);36            int j = diffIndices.get(1);37            return s1.charAt(i) == s2.charAt(j) && s1.charAt(j) == s2.charAt(i);38        }39 40        return false;41    }42}

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.

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.

1class Solution {2    public int countAlmostEqualPairs(int[] nums) {3        java.util.Map<Integer, Integer> freqMap = new java.util.HashMap<>();4        for (int num : nums) {5            freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);6        }7 8        long count = 0;9        for (java.util.Map.Entry<Integer, Integer> entry : freqMap.entrySet()) {10            int num = entry.getKey();11            long c = entry.getValue();12 13            // Case 1: Pairs of the same number (e.g., (12, 12))14            count += c * (c - 1) / 2;15 16            // Case 2: Pairs with a variant (e.g., (12, 21))17            char[] digits = String.valueOf(num).toCharArray();18            for (int i = 0; i < digits.length; i++) {19                for (int j = i + 1; j < digits.length; j++) {20                    // Swap digits21                    char temp = digits[i];22                    digits[i] = digits[j];23                    digits[j] = temp;24 25                    int variant = Integer.parseInt(new String(digits));26 27                    // To avoid double counting, only consider pairs (num, variant) where num < variant28                    if (num < variant && freqMap.containsKey(variant)) {29                        count += c * freqMap.get(variant);30                    }31 32                    // Swap back to restore original digits for next iteration33                    temp = digits[i];34                    digits[i] = digits[j];35                    digits[j] = temp;36                }37            }38        }39        return (int) count;40    }41}