Count Almost Equal Pairs II solution and explanation
7 more videos on this problem
A-D | Leetcode Weekly Contest 412 Editorials | Count Almost Equal Pairs II | Abhinav AwasthiAbhinav Awasthi · 41:12 · 5K views
3267. Count Almost Equal Pairs II | Weekly Leetcode 412codingMohan · 24:19 · 846 views
Count Almost Equal Pairs | I & II | Leetcode 3265 | Leetcode 3267 | Weekly Contest 412Tech Courses · 23:47 · 348 views
3267. Count Almost Equal Pairs II (Leetcode Hard)Programming Live with Larry · 1:42:04 · 322 views
Count almost equal pairs II | leetcode weekly contest 412 | solutionsCodeCrusher · 1:03 · 230 views
3267. Count Almost Equal Pairs II | Weekly Contest 412 | LeetCodePulkit Malhotra · 18:28 · 94 views
3267. Count Almost Equal Pairs IICodeCracker · 27:27 · 44 views
3265. 3267 Count Almost Equal Pairs I && IICodingHelp · 17:18 · 26 views
The problem
Attention: In this version, the number of operations that can be performed, has been increased to twice.
You are given an array nums consisting of positive integers.
We call two integers x and y almost equal if both integers can become equal after performing the following operation at most twice:
- Choose either
xoryand 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 = [1023,2310,2130,213]
Output: 4
Explanation:
The almost equal pairs of elements are:
- 1023 and 2310. By swapping the digits 1 and 2, and then the digits 0 and 3 in 1023, you get 2310.
- 1023 and 213. By swapping the digits 1 and 0, and then the digits 1 and 2 in 1023, you get 0213, which is 213.
- 2310 and 213. By swapping the digits 2 and 0, and then the digits 3 and 2 in 2310, you get 0213, which is 213.
- 2310 and 2130. By swapping the digits 3 and 1 in 2310, you get 2130.
Example 2:
Input: nums = [1,10,100]
Output: 3
Explanation:
The almost equal pairs of elements are:
- 1 and 10. By swapping the digits 1 and 0 in 10, you get 01 which is 1.
- 1 and 100. By swapping the second 0 with the digit 1 in 100, you get 001, which is 1.
- 10 and 100. By swapping the first 0 with the digit 1 in 100, you get 010, which is 10.
Constraints:
2 <= nums.length <= 50001 <= nums[i] < 107
Approach overview
Problem Overview: You are given an array of integers. Two numbers form an almost equal pair if you can make them identical by swapping digits within the numbers. The task is to count how many index pairs (i, j) with i < j satisfy this condition.
The key observation: digit swaps never change which digits appear in the number. Only their order changes. That means any valid pair must share the same digit multiset. This invariant allows grouping numbers by their digit composition instead of explicitly simulating swaps.
Approach 1: Digit Frequency Count (O(n · d), Space: O(n))
Convert every number into a canonical representation based on its digit frequencies. Build an array of size 10 and count how many times each digit appears. Serialize this frequency vector (for example, as a tuple or string) and use it as a key in a hash map. While iterating through the input, check how many numbers with the same frequency signature were already seen and add that count to the answer. Then increment the frequency in the map. This approach avoids sorting and uses constant-size digit arrays, making it efficient when numbers contain many digits. It relies on fast hash table lookups and simple counting.
Approach 2: Sorting Digits (O(n · d log d), Space: O(n))
Another way to create a canonical form is by sorting the digits of each number. Convert the number to a string, sort the characters, and use the sorted result as a key in a hash map. Numbers that can become equal through digit swaps will share the same sorted representation. As you process the array, maintain counts of previously seen keys and accumulate pair counts. This approach is straightforward to implement and commonly used in sorting-based grouping problems, though sorting introduces a small log d factor.
Both approaches effectively transform the problem into counting pairs of numbers with identical digit compositions. The remaining work is simple frequency aggregation using arrays and hashing.
Recommended for interviews: The digit frequency count approach. It shows you understand the invariant preserved by digit swaps and avoids unnecessary sorting. Starting with the sorted-digit grouping method demonstrates the core insight, but the frequency-vector solution highlights optimization and stronger algorithmic thinking.
Approach 1: Digit Frequency Count
This approach leverages the idea that two numbers are almost equal if their digits can be rearranged (swapping within the number) into identical sequences, at most through two operations. By identifying the permutation condition, we can count the frequency of each digit 0-9. Two numbers are almost equal if their frequency distributions of digits are identical and can be achieved through a maximum of two swaps.
def count_almost_equal_pairs(nums):
from collections import Counter
def digit_frequency(n):
return Counter(str(n))
freqs = [digit_frequency(num) for num in nums]
count = 0
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if freqs[i] == freqs[j]:
count += 1
return count
# Example usage
nums = [1023, 2310, 2130, 213]
print(count_almost_equal_pairs(nums)) # Output: 4import java.util.*;
public class Solution {
private static Map<Character, Integer> calculateFrequency(int number) {
Map<Character, Integer> freqMap = new HashMap<>();
char[] digits = Integer.toString(number).toCharArray();
for (char digit : digits) {
freqMap.put(digit, freqMap.getOrDefault(digit, 0) + 1);
}
return freqMap;
}
public static int countAlmostEqualPairs(int[] nums) {
int count = 0;
List<Map<Character, Integer>> freqList = new ArrayList<>();
for (int num : nums) {
freqList.add(calculateFrequency(num));
}
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (freqList.get(i).equals(freqList.get(j))) {
count++;
}
}
}
return count;
}
public static void main(String[] args) {
int[] nums = {1023, 2310, 2130, 213};
System.out.println(countAlmostEqualPairs(nums)); // Output: 4
}
}#include <iostream>
#include <vector>
#include <unordered_map>
std::vector<int> calculateFrequency(int number) {
std::vector<int> freq(10, 0);
while (number > 0) {
freq[number % 10]++;
number /= 10;
}
return freq;
}
int countAlmostEqualPairs(const std::vector<int>& nums) {
int count = 0;
std::vector<std::vector<int>> freqMap;
for (int num : nums) {
freqMap.push_back(calculateFrequency(num));
}
for (size_t i = 0; i < nums.size(); ++i) {
for (size_t j = i + 1; j < nums.size(); ++j) {
if (freqMap[i] == freqMap[j]) {
++count;
}
}
}
return count;
}
int main() {
std::vector<int> nums = {1023, 2310, 2130, 213};
std::cout << countAlmostEqualPairs(nums) << std::endl; // Output: 4
return 0;
}function calculateFrequency(num) {
const freqMap = Array(10).fill(0);
while (num > 0) {
freqMap[num % 10]++;
num = Math.floor(num / 10);
}
return freqMap;
}
function countAlmostEqualPairs(nums) {
const freqs = nums.map(n => calculateFrequency(n));
let count = 0;
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
if (freqs[i].toString() === freqs[j].toString()) {
count++;
}
}
}
return count;
}
// Example usage
const nums = [1023, 2310, 2130, 213];
console.log(countAlmostEqualPairs(nums)); // Output: 4#include <stdio.h>
#include <string.h>
void calculateFrequency(int number, int freq[]) {
memset(freq, 0, sizeof(int) * 10);
while (number > 0) {
freq[number % 10]++;
number /= 10;
}
}
int areFrequenciesEqual(int freq1[], int freq2[]) {
for (int i = 0; i < 10; i++) {
if (freq1[i] != freq2[i]) return 0;
}
return 1;
}
int countAlmostEqualPairs(int nums[], int numsSize) {
int count = 0;
int freqMap[numsSize][10];
for (int i = 0; i < numsSize; i++) {
calculateFrequency(nums[i], freqMap[i]);
}
for (int i = 0; i < numsSize; i++) {
for (int j = i + 1; j < numsSize; j++) {
if (areFrequenciesEqual(freqMap[i], freqMap[j])) {
count++;
}
}
}
return count;
}
int main() {
int nums[] = {1023, 2310, 2130, 213};
int numsSize = sizeof(nums) / sizeof(nums[0]);
printf("%d
", countAlmostEqualPairs(nums, numsSize)); // Output: 4
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
private static Dictionary<char, int> CalculateFrequency(int number) {
Dictionary<char, int> freqMap = new Dictionary<char, int>();
foreach (char digit in number.ToString()) {
if (freqMap.ContainsKey(digit)) {
freqMap[digit]++;
} else {
freqMap[digit] = 1;
}
}
return freqMap;
}
public static int CountAlmostEqualPairs(int[] nums) {
int count = 0;
List<Dictionary<char, int>> freqList = new List<Dictionary<char, int>>();
foreach (int num in nums) {
freqList.Add(CalculateFrequency(num));
}
for (int i = 0; i < nums.Length; i++) {
for (int j = i + 1; j < nums.Length; j++) {
if (AreDictionariesEqual(freqList[i], freqList[j])) {
count++;
}
}
}
return count;
}
private static bool AreDictionariesEqual(Dictionary<char, int> dict1, Dictionary<char, int> dict2) {
if (dict1.Count != dict2.Count) return false;
foreach (var pair in dict1) {
if (!dict2.TryGetValue(pair.Key, out int value) || value != pair.Value) {
return false;
}
}
return true;
}
public static void Main(string[] args) {
int[] nums = {1023, 2310, 2130, 213};
Console.WriteLine(CountAlmostEqualPairs(nums)); // Output: 4
}
}This Python solution first computes the digit frequency of each number using the Counter from the collections module. It then compares the frequency maps of all pairs of numbers in nums. If they match, the pair is considered as almost equal, incrementing the count.
Time Complexity: O(n*m) where n is the length of nums and m is the average number of digits per number, due to the frequency computation and pair comparison.
Space Complexity: O(n*m) for storing the frequency counts of each number.
Approach 2: Sorting Digits
This method compares numbers by sorting their digits. If two numbers can be rearranged into the same digit sequence (via sorting), they are 'almost equal'. This approach is more straightforward, leveraging the properties of sorted digit sequences to determine equivalence.
def count_almost_equal_pairs_by_sorting(nums):
def sort_digits(n):
return ''.join(sorted(str(n)))
sorted_nums = [sort_digits(num) for num in nums]
count = 0
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if sorted_nums[i] == sorted_nums[j]:
count += 1
return count
# Example usage
nums = [1023, 2310, 2130, 213]
print(count_almost_equal_pairs_by_sorting(nums)) # Output: 4import java.util.*;
public class Solution {
private static String sortDigits(int number) {
char[] digits = Integer.toString(number).toCharArray();
Arrays.sort(digits);
return new String(digits);
}
public static int countAlmostEqualPairsBySorting(int[] nums) {
String[] sortedNums = new String[nums.length];
for (int i = 0; i < nums.length; i++) {
sortedNums[i] = sortDigits(nums[i]);
}
int count = 0;
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (sortedNums[i].equals(sortedNums[j])) {
count++;
}
}
}
return count;
}
public static void main(String[] args) {
int[] nums = {1023, 2310, 2130, 213};
System.out.println(countAlmostEqualPairsBySorting(nums)); // Output: 4
}
}#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
std::string sortDigits(int number) {
std::string str = std::to_string(number);
std::sort(str.begin(), str.end());
return str;
}
int countAlmostEqualPairsBySorting(const std::vector<int>& nums) {
std::vector<std::string> sortedNums;
for (int num : nums) {
sortedNums.push_back(sortDigits(num));
}
int count = 0;
for (size_t i = 0; i < nums.size(); ++i) {
for (size_t j = i + 1; j < nums.size(); ++j) {
if (sortedNums[i] == sortedNums[j]) {
++count;
}
}
}
return count;
}
int main() {
std::vector<int> nums = {1023, 2310, 2130, 213};
std::cout << countAlmostEqualPairsBySorting(nums) << std::endl; // Output: 4
return 0;
}function sortDigits(num) {
return num.toString().split('').sort().join('');
}
function countAlmostEqualPairsBySorting(nums) {
const sortedNums = nums.map(num => sortDigits(num));
let count = 0;
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
if (sortedNums[i] === sortedNums[j]) {
count++;
}
}
}
return count;
}
// Example usage:
const nums = [1023, 2310, 2130, 213];
console.log(countAlmostEqualPairsBySorting(nums)); // Output: 4#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void sortDigits(int number, char* sorted) {
char buffer[20];
sprintf(buffer, "%d", number);
strcpy(sorted, buffer);
qsort(sorted, strlen(sorted), sizeof(char), (int(*)(const void*, const void*)) strcmp);
}
int countAlmostEqualPairsBySorting(int nums[], int numsSize) {
char sortedNums[numsSize][20];
for (int i = 0; i < numsSize; i++) {
sortDigits(nums[i], sortedNums[i]);
}
int count = 0;
for (int i = 0; i < numsSize; i++) {
for (int j = i + 1; j < numsSize; j++) {
if (strcmp(sortedNums[i], sortedNums[j]) == 0) {
count++;
}
}
}
return count;
}
int main() {
int nums[] = {1023, 2310, 2130, 213};
int numsSize = sizeof(nums) / sizeof(nums[0]);
printf("%d\n", countAlmostEqualPairsBySorting(nums, numsSize)); // Output: 4
return 0;
}using System;
using System.Linq;
public class Solution {
private static string SortDigits(int number) {
char[] digits = number.ToString().ToCharArray();
Array.Sort(digits);
return new string(digits);
}
public static int CountAlmostEqualPairsBySorting(int[] nums) {
string[] sortedNums = new string[nums.Length];
for (int i = 0; i < nums.Length; i++) {
sortedNums[i] = SortDigits(nums[i]);
}
int count = 0;
for (int i = 0; i < nums.Length; i++) {
for (int j = i + 1; j < nums.Length; j++) {
if (sortedNums[i] == sortedNums[j]) {
count++;
}
}
}
return count;
}
public static void Main(string[] args) {
int[] nums = {1023, 2310, 2130, 213};
Console.WriteLine(CountAlmostEqualPairsBySorting(nums)); // Output: 4
}
}This Python function converts each number into its sorted digit form, storing it in a list. Pairwise checks determine if two numbers, once sorted, have identical digit sequences, being almost equal.
Time Complexity: O(n*m log m), influenced by the sorting of digits in each number where n is size of nums and m is number of digits.
Space Complexity: O(n*m), due to sorted numbers storage.
Approach 3: Sorting + Enumeration
We can enumerate each number, and for each number, we can enumerate each pair of different digits, then swap these two digits to get a new number. Record this new number in a hash table vis, representing all possible numbers after at most one swap. Then continue to enumerate each pair of different digits, swap these two digits to get a new number, and record it in the hash table vis, representing all possible numbers after at most two swaps.
This enumeration may miss some pairs of numbers, such as [100, 1], because the number obtained after swapping 100 is 1, and the previously enumerated numbers do not include 1, so some pairs of numbers will be missed. We only need to sort the array before enumeration to solve this problem.
The time complexity is O(n times (log n + log^5 M)), and the space complexity is O(n + log^4 M). Here, n is the length of the array nums, and M is the maximum value in the array nums.
function countPairs(nums: number[]): number {
nums.sort((a, b) => a - b);
let ans = 0;
const cnt = new Map<number, number>();
for (const x of nums) {
const vis = new Set<number>();
vis.add(x);
const s = x.toString().split('');
for (let j = 0; j < s.length; j++) {
for (let i = 0; i < j; i++) {
[s[i], s[j]] = [s[j], s[i]];
vis.add(+s.join(''));
for (let q = i + 1; q < s.length; ++q) {
for (let p = i + 1; p < q; ++p) {
[s[p], s[q]] = [s[q], s[p]];
vis.add(+s.join(''));
[s[p], s[q]] = [s[q], s[p]];
}
}
[s[i], s[j]] = [s[j], s[i]];
}
}
for (const y of vis) {
ans += cnt.get(y) || 0;
}
cnt.set(x, (cnt.get(x) || 0) + 1);
}
return ans;
}func countPairs(nums []int) (ans int) {
sort.Ints(nums)
cnt := make(map[int]int)
for _, x := range nums {
vis := make(map[int]struct{})
vis[x] = struct{}{}
s := []rune(strconv.Itoa(x))
for j := 0; j < len(s); j++ {
for i := 0; i < j; i++ {
s[i], s[j] = s[j], s[i]
y, _ := strconv.Atoi(string(s))
vis[y] = struct{}{}
for q := i + 1; q < len(s); q++ {
for p := i + 1; p < q; p++ {
s[p], s[q] = s[q], s[p]
z, _ := strconv.Atoi(string(s))
vis[z] = struct{}{}
s[p], s[q] = s[q], s[p]
}
}
s[i], s[j] = s[j], s[i]
}
}
for y := range vis {
ans += cnt[y]
}
cnt[x]++
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Digit Frequency Count | Time Complexity: O(n*m) where n is the length of |
| Sorting Digits | Time Complexity: O(n*m log m), influenced by the sorting of digits in each number where n is size of |
| Sorting + Enumeration | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Digit Frequency Count | O(n · d) | O(n) | Best general solution. Avoids sorting and works efficiently when numbers contain many digits. |
| Sorting Digits | O(n · d log d) | O(n) | Simpler implementation when digit count is small and code clarity is preferred. |
Frequently asked questions
Is Count Almost Equal Pairs II easy or hard?
LeetCode classifies Count Almost Equal Pairs II as a Hard problem. The difficulty comes from recognizing that digit swaps preserve digit counts and converting that observation into an efficient hashing-based counting solution.
Count Almost Equal Pairs II Python/Java solution
Python and Java implementations typically compute a canonical key for each number (either a sorted digit string or a digit frequency tuple) and store counts in a dictionary or HashMap. Each time the same key appears, it contributes existing_count new pairs.
How to solve Count Almost Equal Pairs II in O(n)?
True linear time with respect to the number of elements is achieved by treating the digit frequency vector as a hash key. For each number, compute counts of digits 0–9, use that vector in a hash table, and accumulate how many identical signatures appeared before.
What is the best approach for Count Almost Equal Pairs II?
The most efficient approach groups numbers by their digit frequency signature using a hash map. Digit swaps do not change the multiset of digits, so numbers with identical digit counts can become equal after swaps. This allows counting pairs in O(n · d) time by hashing frequency vectors.
Is Count Almost Equal Pairs II asked at Google/Amazon/Meta?
Problems involving digit transformations, hashing, and grouping by canonical representations frequently appear in interviews at companies like Amazon and Google. Variants of this problem test understanding of hashing, counting techniques, and invariants preserved under transformations.
What data structure is used in Count Almost Equal Pairs II?
The primary data structure is a hash table that maps a canonical digit representation to how many times it has appeared. Arrays of size 10 are commonly used to store digit frequencies before converting them into a hashable key.
What is the time complexity of Count Almost Equal Pairs II?
The optimal solution runs in O(n · d) time where n is the number of elements and d is the number of digits in each number. A slightly simpler alternative sorts the digits of each number, which leads to O(n · d log d) complexity.