Line by line explanation || Initial greedy + Prefix sum + All possible swaps || O(n^2) || Java
Go down to my code to see explanation line by line.\n\n# Approach\n- Sort the array ascending order to keep a greedy of not dealing with swapping trailing zero 
# **Go down to my code to see explanation line by line.**\n\n# Approach\n- Sort the array ascending order to keep a greedy of not dealing with swapping trailing zero case.\n- During each iteration in the nums array, we build a prefix sum all elements in nums up to current element (exclusive). Then generate all possible number can create up to 2 swaps for the current element. Then check if each generated number contained in the prefix sum. If yes, increment number of pairs by the frequency we stored in prefix sum.\n\n# Complexity\n- Time complexity:\nO(n^2)\n\nMost number of digit each element can have is up to 7. The reason is because the constraint is strictly less than 10^7 which is 8 digits. So, given 7 digit, there are 7 x 6 = 42 possible swaps. It also requires worst case O(7) to combine all digits into a single number. That means there are 42 possible numbers after up to one swap and takes O(294). We want up to 2 swaps. So iterating each 42 possible numbers, we will get O(42 x 41 x 7) -> O(12054). Altogether, O(12054) + O(294) -> O(12348)\n\nGiven n = 5000, then O(12348) is about O(2.5n) which is basically O(n).\n\n- Space complexity:\nO(n)\n\nThis is simply because of holding a total of possible 42 x 41 -> 1722 numbers which is O(n/4) which basically is O(n) during each iteration of nums array.\n\n# Code\n```java []\nclass Solution {\n    public int countPairs(int[] nums) {\n\n        //Initial Greedy\n        Arrays.sort(nums);\n\n        int pair = 0;\n        //Prefix Sum\n        Map<Integer, Integer> freq = new HashMap<>();\n\n        for (int i = 0; i < nums.length; i++){\n\n            //All possible numbers up to 1 swap\n            Set<Integer> hold = swap(nums[i]);\n\n            //All possible numbers up to 2 swaps\n            Set<Integer> total = new HashSet<>();\n\n            //Generate all possible numbers up to 2 swaps\n            for (int x : hold){\n                for (int y : swap(x)){\n                    total.add(y);\n                }\n            }\n\n            //Check if any of possible swapped number contained in prefix sum\n            for (int x : total){\n                if (freq.containsKey(x)){\n                    pair += freq.get(x);\n                }\n            }\n\n            //Build prefix sum\n            freq.put(nums[i], freq.getOrDefault(nums[i], 0) + 1);\n        }\n\n        return pair;\n    }\n\n    //Generate all possible number with up to 1 additional swap\n    private Set<Integer> swap(int n){\n\n        //Storing all possible generated numbers\n        Set<Integer> s = new HashSet<>();\n\n        //Store the original number\n        s.add(n);\n\n        //Store the digits\n        List<Integer> num = new ArrayList<>();\n\n        //Split number into digits\n        while (n > 0){\n\n            //Add the last digit\n            num.add(0, n%10);\n\n            //Right shift one place\n            //Ex: 12345 -> 1234, or 2742 -> 274\n            n /= 10;\n        }\n\n        //Trying out all possible numbers with 1 swap\n        for (int i = 1; i < num.size(); i++){\n            for (int j = 0; j < i; j++){\n                int hold1 = num.get(i);\n                int hold2 = num.get(j);\n\n                //Swap it\n                num.set(i, hold2);\n                num.set(j, hold1);\n\n                //Combine all digits into one number\n                int sol = cal(num);\n\n                //Add it to all possible generated numbers\n                s.add(sol);\n\n                //Swap it back to original number\n                num.set(i, hold1);\n                num.set(j, hold2);\n            }\n        }\n\n        return s;\n    }\n\n    //Combined all digits into a number\n    private int cal(List<Integer> a){\n\n        //Start off with ones digit, then tens, then hundreds, etc\n        int ten = 1;\n\n        //The final answer\n        int ans = 0;\n\n        //Start from the ones, which is end of the array\n        for (int i = a.size() - 1; i > -1; i--){\n\n            //Add the number into the correct digit placement\n            ans += ten * a.get(i);\n\n            //Increase from ones to tens, or tens to hundreds, etc\n            ten *= 10;\n        }\n\n        return ans;\n    }\n}\n```\n\n# Please let me know if you have any question, otherwise please upvote if found helpful? Thanks for reading!
['Java']