Count Almost Equal Pairs I — Solution in Python, Java & C++
Count Almost Equal Pairs I solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Count Almost Equal Pairs I is a medium coding problem on arrays, hash table and sorting, asked in Amazon interviews.
- Difficulty: Medium
- Topics: Arrays, Hash Table, Sorting, Counting, Enumeration
- Asked at: Amazon
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an array nums of positive integers.
Two integers x and y are called almost equal if they can be made equal by doing the following at most once: pick one of the two numbers and swap any two of its digits. A swap may put a zero in front, and the leading zeros are then simply ignored (so 30 can become 03, which is 3).
Return the number of index pairs i < j such that nums[i] and nums[j] are almost equal.
Example 1
Input: nums = [3,12,30,17,21]
Output: 2
Explanation: `3` and `30` (swap the digits of `30` to get `03 = 3`), and `12` and `21`.
Example 2
Input: nums = [1,1,1,1,1]
Output: 10
Explanation: Every pair is already equal, and there are `5 * 4 / 2 = 10` pairs.
Example 3
Input: nums = [123,231]
Output: 0
Explanation: Turning `123` into `231` moves all three digits — one swap is not enough.
Constraints
2 <= nums.length <= 1001 <= nums[i] <= 10^6
Hints for Count Almost Equal Pairs I
Hint 1
With at most 100 numbers you can afford to test every pair; the question is how to test one pair quickly.
Hint 2
Pad the shorter number with leading zeros so both have the same number of digits, then compare them digit by digit.
Hint 3
The pair is almost equal when no digit differs, or exactly two positions differ and the two differing digits are crossed (
a[i] == b[j]anda[j] == b[i]).
How to solve Count Almost Equal Pairs I
One swap changes exactly two digit positions of one number. So after lining the two numbers up digit by digit (padding the shorter with zeros, which is what a swap into the leading position produces), they must either already agree everywhere or disagree in exactly two positions holding the same two digits in crossed order.
Approach
- For every pair
i < j, takex = nums[i]andy = nums[j]. - Walk both numbers from the last digit,
x % 10andy % 10, dividing by 10 until both are zero — a number that runs out first contributes zeros, exactly like padding. - Record the positions where the digits differ; stop early once there are three of them.
- Count the pair if there were no differences, or exactly two differences
(a1, b1)and(a2, b2)witha1 == b2anda2 == b1.
Why it works
Swapping two digits of x changes it only in those two positions, and only by exchanging their values. So x can reach y in one swap precisely when they differ in two positions whose digits are crossed; swapping in y instead is the same condition read the other way. Leading zeros are harmless: x and y agree on every position beyond the longer length, and a swap that moves a zero to the front corresponds to padding the shorter number.
Complexity
- Time —
O(n^2 * d) with d ≤ 7 digits - Space —
O(1)
Pitfalls
- Comparing the decimal strings without padding misses pairs like
3and30. - Two differing positions are not enough on their own:
12and34differ in two places but no swap helps. - Equal numbers count as almost equal — zero swaps is allowed.
Reference solution
Python
from typing import List
def countPairs(nums: List[int]) -> int:
def almost_equal(x: int, y: int) -> bool:
diff = []
while x > 0 or y > 0:
a, b = x % 10, y % 10
if a != b:
diff.append((a, b))
if len(diff) > 2:
return False
x //= 10
y //= 10
if not diff:
return True
return len(diff) == 2 and diff[0][0] == diff[1][1] and diff[0][1] == diff[1][0]
n = len(nums)
count = 0
for i in range(n):
for j in range(i + 1, n):
if almost_equal(nums[i], nums[j]):
count += 1
return countJava
static boolean almostEqual(int x, int y) {
int cnt = 0, a1 = 0, b1 = 0, a2 = 0, b2 = 0;
while (x > 0 || y > 0) {
int a = x % 10, b = y % 10;
if (a != b) {
if (cnt == 0) { a1 = a; b1 = b; }
else if (cnt == 1) { a2 = a; b2 = b; }
cnt++;
if (cnt > 2) return false;
}
x /= 10;
y /= 10;
}
return cnt == 0 || (cnt == 2 && a1 == b2 && a2 == b1);
}
public static int countPairs(int[] nums) {
int count = 0;
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (almostEqual(nums[i], nums[j])) count++;
}
}
return count;
}C++
bool almostEqual(int x, int y) {
int cnt = 0, a1 = 0, b1 = 0, a2 = 0, b2 = 0;
while (x > 0 || y > 0) {
int a = x % 10, b = y % 10;
if (a != b) {
if (cnt == 0) { a1 = a; b1 = b; }
else if (cnt == 1) { a2 = a; b2 = b; }
cnt++;
if (cnt > 2) return false;
}
x /= 10;
y /= 10;
}
return cnt == 0 || (cnt == 2 && a1 == b2 && a2 == b1);
}
int countPairs(vector<int>& nums) {
int count = 0, n = nums.size();
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (almostEqual(nums[i], nums[j])) count++;
}
}
return count;
}JavaScript
var countPairs = function(nums) {
var count = 0;
for (var i = 0; i < nums.length; i++) {
for (var j = i + 1; j < nums.length; j++) {
if (almostEqual(nums[i], nums[j])) count++;
}
}
return count;
};
var almostEqual = function(x, y) {
var cnt = 0, a1 = 0, b1 = 0, a2 = 0, b2 = 0;
while (x > 0 || y > 0) {
var a = x % 10, b = y % 10;
if (a !== b) {
if (cnt === 0) { a1 = a; b1 = b; }
else if (cnt === 1) { a2 = a; b2 = b; }
cnt++;
if (cnt > 2) return false;
}
x = Math.floor(x / 10);
y = Math.floor(y / 10);
}
return cnt === 0 || (cnt === 2 && a1 === b2 && a2 === b1);
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets