3267. Count Almost Equal Pairs II

HardArrayHash TableCountingEnumerationSorting

Problem Description

You are given an array nums consisting of positive integers. Two integers x and y are called almost equal if they can become equal after performing the following operation at most twice: choose either x or y and swap any two digits within the chosen number. Your task is to return the number of index pairs i and j in nums where i < j such that nums[i] and nums[j] are almost equal. It is allowed for an integer to have leading zeros after performing an operation.

Intuition

To solve the problem, we need a way to efficiently determine which numbers in the array can be transformed to match each other with at most two digit swaps. By sorting the array initially, the order of numbers helps minimize unnecessary comparisons.

For each number, we explore the set of potential numbers formed by swapping any two digits once, and then extending this to account for the numbers formed by a second swap. We keep track of these possibilities in a hash table. This way, when we encounter another number, we check against the table to see if it could be an almost equal match based on prior computations. This approach leverages enumeration and hashing to efficiently count the valid pairs.

Learn more about Sorting patterns.

Solution Approach

The reference solution uses a combination of sorting and enumeration to efficiently count the pairs of numbers that are almost equal. Here's a detailed walkthrough of the approach:

Sorting: Begin by sorting the array nums. Sorting helps in reducing the number of potential comparisons by organizing numbers in increasing order, thus limiting the number of irrelevant checks.
Enumeration and Hashing: The solution uses a hash table cnt to keep track of how many times each number appears in its swappable forms.
Digit Swapping Simulation: For each number in nums:
- Convert the number to a string to manipulate individual digits.
- Use nested loops to enumerate all unique pairs of digits. For the first pair (i, j), swap the digits to generate a new number after the first swap.
- For each new form of the number generated by the first swap, use another round of nested loops to simulate a second swap, thereby generating all possible numbers after two swaps.
- Record all numbers generated from the swaps in a set vis to prevent duplicates.
Counting Pairs: For each number's set of swappable forms recorded in vis, check how many times these forms have appeared before the current iteration by summing their occurrences in cnt. This accounts for all pairs (i, j) where i < j and they share these swap forms.
Update the Hash Table: After processing the possible forms of a particular number, increase the count in cnt for this number, so it can be considered in future comparisons.

The overall approach efficiently combines the power of sorting, enumeration, and hashing to ensure that each number's potential pairings are explored and counted systematically.

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 = [123, 321, 312, 132, 213, 231] to illustrate the solution approach.

Sorting:
- First, we sort the array. However, the nature of this problem allows us to continue with the input as is for simplification since interactions require comparisons between all numbers. Therefore, the example remains [123, 321, 312, 132, 213, 231].
Enumeration and Hashing:
- We initialize a hash table cnt to keep count of the number of times each swappable form is seen.
Digit Swapping Simulation:
- For 123: Convert to string and evaluate swaps.
  - Swapping digits (1, 2) to get 213; with additional swaps: 231, 123.
  - Swapping (1, 3): 321; with additional swaps: 312.
  - Swapping (2, 3): 132; with additional swaps: 123.
- These swaps yield swappable forms: ['213', '231', '123', '321', '312', '132'].
- Continue similarly for each remaining number:
  - 321 has swappable forms: ['231', '321', '312', '132', '213', '123'].
  - ...
Counting Pairs:
- Use a set to record potential pairings without duplicates.
- For each number's swap forms, count how many have been seen in cnt. This sums the valid pairs (i, j) for which i < j.
Update the Hash Table:
- After processing 123, update cnt to record its forms before moving to the next number. The same process applies to all subsequent numbers.

The solution achieves efficiency through sorting, enumeration, hash storage of transformed numbers, and counting feasible pairings systematically to find all 'almost equal' pairs. In this example, each number can become any other post maximum two swaps, maximizing the count of almost equal pairs.

Solution Implementation

1from collections import defaultdict
2from typing import List
3
4class Solution:
5    def countPairs(self, nums: List[int]) -> int:
6        # Sort the input numbers
7        nums.sort()
8        # Initialize answer variable to count valid pairs
9        answer = 0
10        # Create a defaultdict to count occurrences of each number
11        count_map = defaultdict(int)
12      
13        # Iterate over each number in the sorted list
14        for num in nums:
15            # Create a set to track unique permutations of the current number
16            visited_permutations = {num}
17            # Split the number into its individual digits
18            digits = list(str(num))
19            length = len(digits)
20          
21            # Generate permutations by swapping digits
22            for j in range(length):
23                for i in range(j):
24                    # Swap i-th and j-th digits
25                    digits[i], digits[j] = digits[j], digits[i]
26                    # Add the new permutation to the set
27                    visited_permutations.add(int("".join(digits)))
28                    # Further permutations by swapping any intermediate digits
29                    for q in range(i + 1, length):
30                        for p in range(i + 1, q):
31                            digits[p], digits[q] = digits[q], digits[p]
32                            visited_permutations.add(int("".join(digits)))
33                            digits[p], digits[q] = digits[q], digits[p]
34                    # Revert the initial swap to restore order
35                    digits[i], digits[j] = digits[j], digits[i]
36          
37            # Calculate how many valid pairs can be formed with current number permutations
38            answer += sum(count_map[x] for x in visited_permutations)
39            # Increment the count of the current number
40            count_map[num] += 1
41      
42        return answer
43

1import java.util.Arrays;
2import java.util.HashMap;
3import java.util.HashSet;
4import java.util.Map;
5import java.util.Set;
6
7class Solution {
8    // This method counts the number of pairs of numbers in the array `nums` 
9    // such that one number can be transformed into another by swapping its digits.
10    public int countPairs(int[] nums) {
11        // Sort the array to facilitate counting
12        Arrays.sort(nums);
13      
14        int resultCount = 0; // Variable to keep track of the number of valid pairs
15        Map<Integer, Integer> countMap = new HashMap<>(); // Map to store the frequency of each number
16
17        for (int number : nums) { // Loop through each number in the sorted array
18            Set<Integer> visitedNumbers = new HashSet<>(); // Create a set to store unique numbers generated by swapping digits
19            visitedNumbers.add(number); // Add the original number to the set
20          
21            // Convert the number to a character array to manipulate its digits
22            char[] digits = String.valueOf(number).toCharArray();
23
24            // Double loop to generate all unique permutations by swapping digits
25            for (int j = 0; j < digits.length; ++j) {
26                for (int i = 0; i < j; ++i) {
27                    swap(digits, i, j); // Swap digits at positions i and j
28                    visitedNumbers.add(Integer.parseInt(String.valueOf(digits))); // Add the new permutation to the set
29
30                    // Generate further permutations by swapping within the current permutation
31                    for (int q = i; q < digits.length; ++q) {
32                        for (int p = i; p < q; ++p) {
33                            swap(digits, p, q); // Swap digits at positions p and q
34                            visitedNumbers.add(Integer.parseInt(String.valueOf(digits))); // Add to set
35                            swap(digits, p, q); // Revert swap
36                        }
37                    }
38                    swap(digits, i, j); // Revert the original swap at positions i and j
39                }
40            }
41
42            // Count the valid pairs by checking how many permutations exist in the previously seen numbers
43            for (int transformedNumber : visitedNumbers) {
44                resultCount += countMap.getOrDefault(transformedNumber, 0);
45            }
46
47            // Update the frequency map with the current number
48            countMap.merge(number, 1, Integer::sum);
49        }
50      
51        return resultCount; // Return the total count of valid pairs
52    }
53  
54    // Helper method to swap elements at index i and j in a character array
55    private void swap(char[] array, int i, int j) {
56        char temp = array[i];
57        array[i] = array[j];
58        array[j] = temp;
59    }
60}
61

1#include <vector>
2#include <unordered_map>
3#include <unordered_set>
4#include <string>
5#include <algorithm>
6
7using namespace std;
8
9class Solution {
10public:
11    int countPairs(vector<int>& nums) {
12        // Sort the input vector to work with numbers in order
13        sort(nums.begin(), nums.end());
14      
15        int ans = 0; // Initialize the count of valid pairs
16        unordered_map<int, int> cnt; // Map to store frequency of each number
17
18        for (int num : nums) { 
19            unordered_set<int> visitedNumbers = {num}; // Set to store unique numbers created by permutation
20            string numString = to_string(num); // Convert current number to string to manipulate digits
21
22            // Iterate through each digit of the number
23            for (int j = 0; j < numString.length(); ++j) {
24                for (int i = 0; i < j; ++i) {
25                    // Swap digits at positions i and j
26                    swap(numString[i], numString[j]);
27                    visitedNumbers.insert(stoi(numString)); // Insert the new number formed into the set
28
29                    // Further permutation for digits between current swapped digits
30                    for (int q = i + 1; q < numString.length(); ++q) {
31                        for (int p = i + 1; p < q; ++p) {
32                            // Swap digits at positions p and q
33                            swap(numString[p], numString[q]);
34                            visitedNumbers.insert(stoi(numString)); // Insert newly formed number
35                            swap(numString[p], numString[q]); // Swap back to restore original sequence
36                        }
37                    }
38                    swap(numString[i], numString[j]); // Restore original digit positions
39                }
40            }
41
42            // Check how many previously counted numbers can form pairs with the current number
43            for (int possiblePair : visitedNumbers) {
44                ans += cnt[possiblePair]; // Increase count by the frequency of these numbers
45            }
46            cnt[num]++; // Increment the count of current number in the map
47        }
48
49        return ans; // Return the total count of pairs found
50    }
51};
52

1function countPairs(nums: number[]): number {
2    // Sort the array in non-decreasing order
3    nums.sort((a, b) => a - b);
4
5    let ans = 0; // Initialize the answer to 0
6    const cnt = new Map<number, number>(); // Map to store counts of each number
7
8    for (const x of nums) {
9        const vis = new Set<number>(); // Set to store unique permutations of x
10        vis.add(x);
11
12        const s = x.toString().split(''); // Split the number into digits
13
14        // Generate all unique permutations of the digits
15        for (let j = 0; j < s.length; j++) {
16            for (let i = 0; i < j; i++) {
17                // Swap digits and add result to set
18                [s[i], s[j]] = [s[j], s[i]];
19                vis.add(+s.join(''));
20
21                // Further permutations by swapping within a subset
22                for (let q = i + 1; q < s.length; ++q) {
23                    for (let p = i + 1; p < q; ++p) {
24                        [s[p], s[q]] = [s[q], s[p]];
25                        vis.add(+s.join(''));
26                        [s[p], s[q]] = [s[q], s[p]]; // Swap back
27                    }
28                }
29
30                [s[i], s[j]] = [s[j], s[i]]; // Swap back
31            }
32        }
33
34        // Count pairs by adding occurrences of permutations seen before
35        for (const y of vis) {
36            ans += cnt.get(y) || 0;
37        }
38
39        // Update count for the current element
40        cnt.set(x, (cnt.get(x) || 0) + 1);
41    }
42
43    return ans; // Return the total number of valid pairs
44}
45

Time and Space Complexity

The code involves sorting the nums array, which takes O(n \log n) time. Then, for each number in the array, it creates all possible permutations by swapping digits. The cost of generating these permutations is related to the length of the number in its string representation, giving an approximate complexity of O(\log^5 M) for each number. Thus, the overall time complexity becomes O(n \times (\log n + \log^5 M)).

The space complexity is primarily driven by the need to store potential permutations in the vis set and the cnt dictionary. Each number has approximately O(\log^4 M) permutations (considering practical limits on swapping digits), and the dictionary stores counts of all numbers, resulting in a space complexity of O(n + \log^4 M).

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 is the best way of checking if an element exists in an unsorted array once in terms of time complexity? Select the best that applies.

Linear Search

Binary Search

Quick Select

Hash Set

I don’t know