Count Special Triplets — Solution in Python, Java & C++
Count Special Triplets solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Count Special Triplets is a medium coding problem on arrays, hash table and counting, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Hash Table, Counting
- Asked at: Amazon, Google
- 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 integer array nums.
A special triplet is a triple of indices (i, j, k) with 0 <= i < j < k < n such that nums[i] == nums[j] * 2 and nums[k] == nums[j] * 2.
Return the number of special triplets. Since it can be very large, return it modulo 10^9 + 7.
Example 1
Input: nums = [4,2,4,2,4]
Output: 4
Explanation: With the `2` at index 1: one `4` before it and two after (2 triplets). With the `2` at index 3: two `4`s before and one after (2 more).
Example 2
Input: nums = [0,0,0,0]
Output: 4
Explanation: `0 * 2 = 0`: middle index 1 gives `1 * 2`, middle index 2 gives `2 * 1`.
Example 3
Input: nums = [1,2,3]
Output: 0
Constraints
3 <= nums.length <= 10^50 <= nums[i] <= 10^5
Hints for Count Special Triplets
Hint 1
Fix the middle index
j. The outer indices are independent: anyi < jholding2 * nums[j]pairs with anyk > jholding the same value.Hint 2
So the middle contributes
left[2 * nums[j]] * right[2 * nums[j]], whereleftcounts values beforejandrightcounts values after it.Hint 3
Start with
right= counts of the whole array; while sweepingjleft to right, removenums[j]fromrightbefore using it and add it toleftafterwards. The product can exceed 32 bits — use 64-bit arithmetic before taking the modulus.
How to solve Count Special Triplets
Count by the middle element. For a fixed j, the number of valid outer pairs is the product of how many times 2 * nums[j] appears to the left and to the right, and both counts can be maintained in one sweep.
Approach
- Build
right, the frequency of every value innums, and an emptyleft. - For each
jfrom left to right: decrementright[nums[j]](sorightcovers indices afterj). - Let
t = 2 * nums[j]; addleft[t] * right[t]to the answer, modulo10^9 + 7. - Increment
left[nums[j]].
Why it works
Every special triplet has exactly one middle index, and for that j the pair (i, k) is any choice of an index before j and an index after j that both hold t. The number of such choices is left[t] * right[t], and the sweep keeps left and right equal to the counts strictly before and strictly after j.
Complexity
- Time —
O(n) - Space —
O(V) for the counts
Pitfalls
- Zeros satisfy
0 == 0 * 2: the middle itself must not be counted on either side, which is whyrightis decremented before the lookup andleftincremented after. left[t] * right[t]can reach about2.5 * 10^9, which overflows a 32-bit integer.2 * nums[j]can exceed the largest value present — guard the lookup.
Reference solution
Python
from typing import List
def specialTriplets(nums: List[int]) -> int:
MOD = 10**9 + 7
right = {}
for v in nums:
right[v] = right.get(v, 0) + 1
left = {}
ans = 0
for v in nums:
right[v] -= 1
t = v * 2
ans = (ans + left.get(t, 0) * right.get(t, 0)) % MOD
left[v] = left.get(v, 0) + 1
return ansJava
public static int specialTriplets(int[] nums) {
final long MOD = 1_000_000_007L;
int mx = 0;
for (int v : nums) mx = Math.max(mx, v);
int[] left = new int[mx + 1], right = new int[mx + 1];
for (int v : nums) right[v]++;
long ans = 0;
for (int v : nums) {
right[v]--;
int t = v * 2;
if (t <= mx) ans = (ans + (long) left[t] * right[t]) % MOD;
left[v]++;
}
return (int) ans;
}C++
int specialTriplets(vector<int>& nums) {
const long long MOD = 1000000007LL;
int mx = 0;
for (int v : nums) mx = max(mx, v);
vector<int> left(mx + 1, 0), right(mx + 1, 0);
for (int v : nums) right[v]++;
long long ans = 0;
for (int v : nums) {
right[v]--;
int t = v * 2;
if (t <= mx) ans = (ans + (long long)left[t] * right[t]) % MOD;
left[v]++;
}
return (int)ans;
}JavaScript
var specialTriplets = function(nums) {
var MOD = 1000000007;
var right = new Map(), left = new Map();
for (var i = 0; i < nums.length; i++) right.set(nums[i], (right.get(nums[i]) || 0) + 1);
var ans = 0;
for (var j = 0; j < nums.length; j++) {
var v = nums[j];
right.set(v, right.get(v) - 1);
var t = v * 2;
// Both counts are at most 1e5, so the product stays below 2^53.
ans = (ans + ((left.get(t) || 0) * (right.get(t) || 0)) % MOD) % MOD;
left.set(v, (left.get(v) || 0) + 1);
}
return ans;
};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