3267. Count Almost Equal Pairs II LeetCode Solution
In this guide, you will get 3267. Count Almost Equal Pairs II LeetCode Solution with the best time and space complexity. The solution to Count Almost Equal Pairs II problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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 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.
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.
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 <= 5000
1 <= nums[i] < 107
Complexity Analysis
Time Complexity: O(n \cdot \log(\max(\texttt{nums}))^4)
Space Complexity: O(\log(\max(\texttt{nums}))^4)
3267. Count Almost Equal Pairs II LeetCode Solution in C++
class Solution {
public:
// Similar to 3265. Count Almost Equal Pairs I
int countPairs(vector<int>& nums) {
int ans = 0;
unordered_map<int, int> count;
const int maxLen = to_string(ranges::max(nums)).length();
for (const int num : nums) {
const string digits =
string(maxLen - to_string(num).length(), '0') + to_string(num);
for (const int swap : getSwaps(digits))
ans += count[swap];
++count[num];
}
return ans;
}
private:
// Returns all possible numbers after 1 or 2 swaps.
unordered_set<int> getSwaps(const string& digits) {
const int n = digits.length();
unordered_set<int> swaps{{stoi(digits)}};
// Add all numbers after 1 swap.
for (int i = 0; i < n; ++i)
for (int j = i + 1; j < n; ++j) {
string newDigits = digits;
swap(newDigits[i], newDigits[j]);
swaps.insert(stoi(newDigits));
}
// Add all numbers after 2 swaps.
for (int i1 = 0; i1 < n; ++i1)
for (int j1 = i1 + 1; j1 < n; ++j1)
for (int i2 = 0; i2 < n; ++i2)
for (int j2 = i2 + 1; j2 < n; ++j2) {
string newDigits = digits;
swap(newDigits[i1], newDigits[j1]);
swap(newDigits[i2], newDigits[j2]);
swaps.insert(stoi(newDigits));
}
return swaps;
}
}; /* code provided by PROGIEZ */
3267. Count Almost Equal Pairs II LeetCode Solution in Java
class Solution {
// Similar to 3265. Count Almost Equal Pairs I
public int countPairs(int[] nums) {
int ans = 0;
Map<Integer, Integer> count = new HashMap<>();
final int maxLen = String.valueOf(Arrays.stream(nums).max().getAsInt()).length();
for (final int num : nums) {
final String digits = String.format("%0" + maxLen + "d", num);
for (final int swap : getSwaps(digits))
ans += count.getOrDefault(swap, 0);
count.merge(num, 1, Integer::sum);
}
return ans;
}
// Returns all possible numbers after 1 or 2 swaps.
private Set<Integer> getSwaps(final String digits) {
final int n = digits.length();
Set<Integer> swaps = new HashSet<>(Arrays.asList(Integer.parseInt(digits)));
// Add all numbers after 1 swap.
for (int i = 0; i < n; ++i)
for (int j = i + 1; j < n; ++j) {
char[] newDigits = digits.toCharArray();
char temp = newDigits[i];
newDigits[i] = newDigits[j];
newDigits[j] = temp;
swaps.add(Integer.parseInt(new String(newDigits)));
}
// Add all numbers after 2 swaps.
for (int i1 = 0; i1 < n; ++i1)
for (int j1 = i1 + 1; j1 < n; ++j1)
for (int i2 = 0; i2 < n; ++i2)
for (int j2 = i2 + 1; j2 < n; ++j2) {
char[] newDigits = digits.toCharArray();
char temp = newDigits[i1];
newDigits[i1] = newDigits[j1];
newDigits[j1] = temp;
temp = newDigits[i2];
newDigits[i2] = newDigits[j2];
newDigits[j2] = temp;
swaps.add(Integer.parseInt(new String(newDigits)));
}
return swaps;
}
} // code provided by PROGIEZ
3267. Count Almost Equal Pairs II LeetCode Solution in Python
class Solution:
# Similar to 3265. Count Almost Equal Pairs I
def countPairs(self, nums: list[int]) -> int:
ans = 0
count = collections.Counter()
maxLen = len(str(max(nums)))
for num in nums:
digits = list(str(num).zfill(maxLen))
for swap in self._getSwaps(digits):
ans += count[swap]
count[num] += 1
return ans
def _getSwaps(self, digits: str) -> set[int]:
"""Returns all possible numbers after 1 or 2 swaps."""
n = len(digits)
swaps = set([int(''.join(digits))])
# Add all numbers after 1 swap.
for i, j in itertools.combinations(range(n), 2):
newDigits = digits[:]
newDigits[i], newDigits[j] = newDigits[j], newDigits[i]
swaps.add(int(''.join(newDigits)))
# Add all numbers after 2 swaps.
for (i1, j1), (i2, j2) in itertools.combinations(
itertools.combinations(range(n), 2), 2):
newDigits = digits[:]
newDigits[i1], newDigits[j1] = newDigits[j1], newDigits[i1]
newDigits[i2], newDigits[j2] = newDigits[j2], newDigits[i2]
swaps.add(int(''.join(newDigits)))
return swaps # code by PROGIEZ
