3265. Count Almost Equal Pairs I

MediumArrayHash TableCountingEnumerationSorting

Problem Description

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.

Intuition

The problem requires us to find pairs of integers in the array nums that can be made equal by swapping two digits within any of the integers at most once. The challenge lies in efficiently determining which numbers can be transformed into each other with such swaps.

One approach to tackle this problem is by exploring each number's potential transformations through digit swaps and keeping track of these transformations using a data structure, such as a hash table. This allows us to quickly count how many numbers from earlier in the array can become a given number via a swap.

The core idea is to:

Sort the array to facilitate the comparison of numbers.
For each number, consider swapping every possible pair of digits and record all resulting numbers (given the constraint of a single swap), including the number itself, as possible outcomes.
Use a hash table to store counts of all numbers we've processed so far.
For each new number and its swap-variants, count how many times these numbers have appeared before (using the hash table), and add this count to the result.

This approach ensures we consider all previous numbers that could transform into the current number, accounting for unique swap transformations.

Learn more about Sorting patterns.

Solution Approach

The solution employs a combination of sorting and enumeration to identify pairs of numbers that can potentially become equal with a single swap. Here's a step-by-step breakdown of the approach:

Sorting: By sorting the array nums, we ensure that during our enumeration, we can efficiently track previous numbers and their potential swap variants. This helps in easily counting pairs without missing any possible transformations due to order.
Enumeration of Swaps: For each number x in the sorted array, consider all possible digit swaps:
- Convert the number to a string to handle its digits easily.
- Use two nested loops to swap every possible pair of digits in the number.
- Generate the number resulting from each swap, and store it in a set vis, which holds all possible numbers x can become with at most one swap, including the number itself.
Hash Table (cnt) for Counting:
- Use a hash table cnt (implemented as a defaultdict(int)) to keep track of how many times each number appears as we iterate through the array.
- For every x and its swap variants contained in vis, calculate how many of these have been previously encountered by summing up their counts from cnt.
- Add this sum to the overall count of pairs (ans).
Update Hash Table: After processing each x, update the hash table cnt to increment the count of x.
Return Result: Once done with all numbers, the variable ans holds the count of pairs where nums[i] and nums[j] are almost equal, as required by the problem definition.

This method efficiently utilizes sorting and a hash table to avoid excessive comparisons, leveraging the idea of pre-computation of possible swap outcomes to optimize the pair counting process.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a small example array nums = [21, 12, 30].

We'll follow the solution approach described:

Sorting the Array:
Sort the array, which becomes nums_sorted = [12, 21, 30]. Sorting helps in efficiently tracking previous numbers and potential swap variants.
Enumeration of Swaps:
Iterate through each number in nums_sorted and consider all possible digit swaps.
- For 12:
  - Convert 12 to a string and swap the digits. The number itself remains 12 and swapping gives 21.
  - Store the numbers 12 and 21 in a set vis = {12, 21}.
- For 21:
  - The number stays 21, and swapping its digits gives 12.
  - Store 21 and 12 in a set vis = {21, 12}.
- For 30:
  - Swap digits leaves 30, as no leading zeros are permissible. Swap does not introduce a different number.
  - Store 30 in a set vis = {30}.
Hash Table for Counting:
Initiate a hash table cnt = defaultdict(int) to track how often each number appears.
- For 12 in sorted array:
  - Check vis = {12, 21}. Both numbers are new, so ans accumulates 0.
  - Update cnt: cnt[12] += 1 leads to cnt = {12: 1}.
- For 21 in sorted array:
  - Check vis = {21, 12}. Both 12 and 21 are already encountered once, so ans += cnt[12] + cnt[21] = 1.
  - Update cnt: cnt[21] += 1 results in cnt = {12: 1, 21: 1}.
- For 30 in sorted array:
  - Check vis = {30} and find no previous occurrences, contributing 0 to ans.
  - Update cnt: cnt[30] += 1 updates to cnt = {12: 1, 21: 1, 30: 1}.
Return Result:
The variable ans now holds the count of pairs where nums[i] and nums[j] are almost equal, which is 1 in this example. The pair (12, 21) represents those almost equal numbers.

By following the above steps using sorting and a hash table, we efficiently find all such pairs without exhaustive direct comparison.

Solution Implementation

1from typing import List
2from collections import defaultdict
3
4class Solution:
5    def countPairs(self, nums: List[int]) -> int:
6        # Sort the array for easier counting and processing
7        nums.sort()
8        # Initialize the count of valid pairs
9        ans = 0
10        # Use defaultdict to handle counts of occurrences of numbers and their permutations
11        count_map = defaultdict(int)
12      
13        # Iterate through each number in the sorted list
14        for number in nums:
15            # Use a set to track all unique permutations of the current number
16            visited_permutations = {number}
17            # Convert the number to a list of its string representation to permute digits
18            digits = list(str(number))
19          
20            # Double loop to generate all permutations of the digits
21            for j in range(len(digits)):
22                for i in range(j):
23                    # Swap two digits to create a new permutation
24                    digits[i], digits[j] = digits[j], digits[i]
25                    # Add the newly formed number to the visited set
26                    visited_permutations.add(int("".join(digits)))
27                    # Swap back to restore the original order for the next permutation
28                    digits[i], digits[j] = digits[j], digits[i]
29          
30            # Count how many permutations have been seen before as valid pairs
31            ans += sum(count_map[x] for x in visited_permutations)
32          
33            # Increase the count of the current number in the map for future reference
34            count_map[number] += 1
35      
36        return ans
37

1import java.util.Arrays;
2import java.util.HashMap;
3import java.util.HashSet;
4import java.util.Map;
5import java.util.Set;
6
7class Solution {
8    public int countPairs(int[] nums) {
9        // Sort the array to ensure a systematic approach
10        Arrays.sort(nums);
11
12        int ans = 0; // This will keep track of the total number of pairs
13
14        // Map to store counts of processed numbers
15        Map<Integer, Integer> countMap = new HashMap<>();
16
17        // Iterate through each number in the array
18        for (int x : nums) {
19            // Set to track variations of the current number
20            Set<Integer> variations = new HashSet<>();
21            variations.add(x); // Always include the number itself
22
23            // Convert the number to a char array for manipulation
24            char[] numChars = String.valueOf(x).toCharArray();
25
26            // Generate all possible numbers by swapping digits
27            for (int j = 0; j < numChars.length; ++j) {
28                for (int i = 0; i < j; ++i) {
29                    // Swap digits
30                    swap(numChars, i, j);
31                    // Add the new number to the variations set
32                    variations.add(Integer.parseInt(String.valueOf(numChars)));
33                    // Swap digits back to their original positions
34                    swap(numChars, i, j);
35                }
36            }
37
38            // Count pairs for all variations present in the map
39            for (int y : variations) {
40                ans += countMap.getOrDefault(y, 0);
41            }
42
43            // Increment the count of the current number in the map
44            countMap.merge(x, 1, Integer::sum);
45        }
46        return ans; // Return the total number of pairs
47    }
48
49    // Helper method to swap two characters in a char array
50    private void swap(char[] s, int i, int j) {
51        char temp = s[i];
52        s[i] = s[j];
53        s[j] = temp;
54    }
55}
56

1#include <vector>
2#include <unordered_map>
3#include <unordered_set>
4#include <algorithm>
5#include <string>
6
7using namespace std;
8
9class Solution {
10public:
11    int countPairs(vector<int>& nums) {
12        // Sort the input numbers to facilitate pair counting
13        sort(nums.begin(), nums.end());
14      
15        int ans = 0; // Variable to store the count of pairs
16        unordered_map<int, int> frequencyMap; // To store the frequency of each number that has been processed
17
18        // Iterate over each number in the sorted list
19        for (int number : nums) {
20            unordered_set<int> uniquePermutations = {number}; // Set to store unique permutations of the digits
21            string numStr = to_string(number); // Convert the number to a string to work with its digits
22
23            // Generate permutations by swapping digits
24            for (int j = 0; j < numStr.length(); ++j) {
25                for (int i = 0; i < j; ++i) {
26                    swap(numStr[i], numStr[j]); // Swap digits
27                    uniquePermutations.insert(stoi(numStr)); // Convert permutation to integer and insert into the set
28                    swap(numStr[i], numStr[j]); // Swap back to restore original string
29                }
30            }
31
32            // Count pairs using permutations that have already been seen
33            for (int perm : uniquePermutations) {
34                ans += frequencyMap[perm]; // Add the frequency of the current permutation to ans
35            }
36
37            frequencyMap[number]++; // Increment the frequency of the current number in the map
38        }
39
40        return ans; // Return the total count of valid pairs
41    }
42};
43

1// Function to count the valid pairs in the given array of numbers.
2function countPairs(nums: number[]): number {
3    // Sort the numbers in ascending order.
4    nums.sort((a, b) => a - b);
5    let ans = 0; // Initialize count of valid pairs to 0.
6    const cnt = new Map<number, number>(); // Map to store frequency of numbers encountered.
7
8    // Iterate over each number in the sorted list.
9    for (const num of nums) {
10        const permutationsSet = new Set<number>(); // Set to store unique permutations of the current number.
11        permutationsSet.add(num); // Add the current number to the set.
12        const charArray = num.toString().split(''); // Convert the number to a character array.
13
14        // Iterate over pairs of indices in the character array.
15        for (let j = 0; j < charArray.length; j++) {
16            for (let i = 0; i < j; i++) {
17                // Swap characters at indices i and j.
18                [charArray[i], charArray[j]] = [charArray[j], charArray[i]];
19                // Add the permutation to the set.
20                permutationsSet.add(+charArray.join(''));
21                // Swap the characters back to their original position.
22                [charArray[i], charArray[j]] = [charArray[j], charArray[i]];
23            }
24        }
25
26        // For each number in the set of permutations, update the count of valid pairs.
27        for (const permutedNum of permutationsSet) {
28            ans += cnt.get(permutedNum) || 0;
29        }
30        // Update the frequency map with the current number.
31        cnt.set(num, (cnt.get(num) || 0) + 1);
32    }
33
34    return ans; // Return the total count of valid pairs.
35}
36

Time and Space Complexity

The time complexity is O(n \times (\log n + \log^3 M)), and the space complexity is O(n + \log^2 M). Here, n is the length of the array nums, and M is the maximum value in the array nums.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What's the relationship between a tree and a graph?

A graph is a special tree

A tree is a special graph

No relationship

They are the same thing

I don’t know