#3267

Hard

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Count Almost Equal Pairs II

Count the number of almost equal integer pairs in an array using array scanning and hash lookup efficiently.

array hash table sorting counting enumeration

Problem Statement

Given an array of positive integers nums, define two integers x and y as almost equal if they can become identical after performing a specific operation at most twice. Your task is to count all pairs (i, j) where i < j and nums[i] and nums[j] are almost equal under this rule.

Each number in nums can be transformed using the operation twice, and the array can contain up to 5000 elements with values below 10^7. Return the total number of almost equal pairs considering all possible transformations efficiently using array scanning and hash lookup.

Examples

Example 1

Input: nums = [1023,2310,2130,213]

Output: 4

The almost equal pairs of elements are:

Example 2

Input: nums = [1,10,100]

Output: 3

The almost equal pairs of elements are:

Constraints

2 <= nums.length <= 5000
1 <= nums[i] < 107

Solution Approach

Generate Transformations

For each element in nums, enumerate all integers that can result from applying the allowed operation once or twice. Store these transformed numbers in a hash table to track potential matches efficiently.

Count Pair Matches

While scanning the array, check the hash table for each element to see how many previously seen numbers can form almost equal pairs with it. Increment a running total for each match found.

Avoid Double Counting

Ensure that each pair (i, j) is counted exactly once by updating the hash table only after processing an element. This guarantees no pair is counted twice while maintaining linear scanning performance.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on the number of transformations generated per element and the efficiency of hash lookups, while space complexity is dominated by storing all reachable numbers in a hash table.

What Interviewers Usually Probe

Notice the problem emphasizes array scanning combined with hash lookup.
Be aware that generating all possible transformations per element may affect performance.
Watch for edge cases where multiple transformations lead to the same integer.

Common Pitfalls or Variants

Common pitfalls

Failing to account for exactly two operations per element may lead to incorrect counts.
Double counting pairs if the hash table is updated before scanning all potential matches.
Ignoring large values in nums, which can cause hash table collisions or overflow if not handled carefully.

Follow-up variants

Count almost equal pairs with only one allowed operation instead of two.
Find almost equal pairs in a multidimensional array using similar transformation rules.
Limit the operations to additive changes and count pairs satisfying the restricted criteria.

FAQ

What does 'almost equal' mean in Count Almost Equal Pairs II?

Two numbers are almost equal if they can become identical after applying the operation at most twice.

How should I handle duplicates when counting pairs?

Use a hash table to track counts of each transformed number and increment totals carefully to avoid double counting.

What is the best approach for large arrays up to 5000 elements?

Scan the array while generating transformations for each element and use hash lookup to efficiently count matches.

Can this problem be solved without a hash table?

Yes, but it will likely be less efficient and more prone to missing or double-counting almost equal pairs.

Why is array scanning plus hash lookup the primary pattern?

Because we need to enumerate transformations per element and quickly find how many previous numbers match, which this pattern handles efficiently.

terminal

Solution

Solution 1: 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 $\textit{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 $\textit{vis}$, representing all possible numbers after at most two swaps.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

class Solution:
    def countPairs(self, nums: List[int]) -> int:
        nums.sort()
        ans = 0
        cnt = defaultdict(int)
        for x in nums:
            vis = {x}
            s = list(str(x))
            m = len(s)
            for j in range(m):
                for i in range(j):
                    s[i], s[j] = s[j], s[i]
                    vis.add(int("".join(s)))
                    for q in range(i + 1, m):
                        for p in range(i + 1, q):
                            s[p], s[q] = s[q], s[p]
                            vis.add(int("".join(s)))
                            s[p], s[q] = s[q], s[p]
                    s[i], s[j] = s[j], s[i]
            ans += sum(cnt[x] for x in vis)
            cnt[x] += 1
        return ans

Continue Practicing

#3265 count almost equal pairs i #3186 maximum total damage with spell casting #3371 identify the largest outlier in an array