⚡ TL;DR
Count nice pairs in an array in Dart. Learn the modular arithmetic trick that turns O(n²) into O(n) using hash maps, with full code and tests.
Nice Pairs (#1814) is a clever problem where the naive approach fails for large inputs. The trick is a mathematical transformation that lets you solve it in O(n) time with a hash map. In this Dart-focused guide, we solve it step by step.
Problem Statement
Given an array nums of integers, a pair (i, j) is called nice if i < j and:
nums[i] + rev(nums[j]) == rev(nums[i]) + nums[j]Count the number of nice pairs. rev(x) reverses the digits of x (e.g., rev(123) = 321).
Example:
Input: nums = [42, 11, 1, 97]
Output: 2
Explanation: Pairs (0,3) and (1,2) are nice.
- 42 + rev(97) = 42 + 79 = 121
- rev(42) + 97 = 24 + 97 = 121
- 11 + rev(1) = 11 + 1 = 12
- rev(11) + 1 = 11 + 1 = 12The Key Insight
Subtract both sides:
nums[i] + rev(nums[j]) == rev(nums[i]) + nums[j]
nums[i] - rev(nums[i]) == nums[j] - rev(nums[j])So we just count how many numbers have the same value of nums[i] - rev(nums[i]).
Approach 1: Brute Force (O(n²))
Check every pair (i, j) where i < j.
int countNicePairsBrute(List<int> nums) {
int n = nums.length;
int count = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (nums[i] + rev(nums[j]) == rev(nums[i]) + nums[j]) {
count++;
}
}
}
return count;
}
int rev(int x) {
int res = 0;
while (x != 0) {
res = res * 10 + x % 10;
x ~/= 10;
}
return res;
}
void main() {
print(countNicePairsBrute([42, 11, 1, 97])); // 2
}Time: O(n²)
Space: O(1)
Verdict: Works but fails for n = 10⁵ (too slow).
Approach 2: Hash Map + Trick (O(n))
Compute nums[i] - rev(nums[i]) for each element and count occurrences using a hash map.
int rev(int x) {
int r = 0;
while (x > 0) {
r = r * 10 + x % 10;
x ~/= 10;
}
return r;
}
int countNicePairsHash(List<int> nums) {
int mod = 1000000007;
Map<int, int> freq = {};
int count = 0;
for (int i = 0; i < nums.length; i++) {
int val = nums[i] - rev(nums[i]);
val = ((val % mod) + mod) % mod; // Handle negatives
int occurrences = freq[val] ?? 0;
count = (count + occurrences) % mod;
freq[val] = occurrences + 1;
}
return count;
}
void main() {
print(countNicePairsHash([42, 11, 1, 97])); // 2
}How it works:
- For each new element, check how many previous elements had the same
nums[i] - rev(nums[i])value - Each occurrence contributes one new nice pair
- Modular arithmetic prevents overflow (mod 10⁹ + 7)
Time: O(n) — single pass
Space: O(n) — hash map stores all differences
Dart-Specific Implementation Notes
Using Map<int, int> with ?? operator:
int value = freq[key] ?? 0; // null-coalescing operatorModular arithmetic in Dart needs extra care for negatives:
int modVal = ((x % mod) + mod) % mod; // ensures positive modComparison Table
| Approach | Time | Space | Interview Use |
|---|---|---|---|
| Brute Force | O(n²) | O(1) | Never — fails for large n |
| Hash Map | O(n) | O(n) | ✅ Always use |
Test Cases
void main() {
assert(countNicePairsHash([42, 11, 1, 97]) == 2);
assert(countNicePairsHash([13, 10, 35, 24, 76]) == 4);
assert(countNicePairsHash([]) == 0);
assert(countNicePairsHash([1]) == 0);
assert(countNicePairsHash([1, 1]) == 1);
print("All tests passed!");
}Explanation for [13, 10, 35, 24, 76]:
13 - rev(13) = 13 - 31 = -1810 - rev(10) = 10 - 1 = 935 - rev(35) = 35 - 53 = -1824 - rev(24) = 24 - 42 = -1876 - rev(76) = 76 - 67 = 9
Pairs with same value: (-18): (0,2), (0,3), (2,3) => 3 pairs. (9): (1,4) => 1 pair. Total 4 pairs.
Edge Cases
- Empty array → return 0
- One element → return 0
- All same values → n choose 2 pairs
- All unique values → 0 pairs
- Negative results → handle with proper mod arithmetic in Dart
Practice Variations
- Count pairs with equal sum (
nums[i] + nums[j]) - Count pairs where XOR is 0 (nice pairs for XOR)
- Count pairs where difference equals k
The hash map + linear scan pattern appears in many LeetCode problems. Master it!
Related Problems
FAQ
What is the best approach to solve Count Nice Pairs in Dart?
The recommended approach is the optimal approach, which runs in O(n²) time with O(1) space. The full Dart implementation is shown above.
What is the time complexity of Count Nice Pairs in Dart?
Using the optimal approach, the time complexity is O(n²) and the space complexity is O(1).
Related Posts
- Best Time to Buy and Sell Stock in Dart - LeetCode #121 with Dynamic Programming
- Climbing Stairs in Dart - Dynamic Programming with Memoization and Iteration
- Merge Two Sorted Lists in Dart - Iterative and Recursive Approaches with Null Safety
- Best Time to Buy and Sell Stock in Go - Single Pass, Min Tracking, and Sliding Window
