Count Special Triplets
MedPrompt
You are given an integer array nums.
A special triplet is defined as a triplet of indices (i, j, k) such that:
0 <= i < j < k < n, wheren = nums.lengthnums[i] == nums[j] * 2nums[k] == nums[j] * 2
Return the total number of special triplets in the array.
Since the answer may be large, return it modulo 109 + 7.
Example 1:
Input: nums = [6,3,6]
Output: 1
Explanation:
The only special triplet is (i, j, k) = (0, 1, 2), where:
nums[0] = 6,nums[1] = 3,nums[2] = 6nums[0] = nums[1] * 2 = 3 * 2 = 6nums[2] = nums[1] * 2 = 3 * 2 = 6
Example 2:
Input: nums = [0,1,0,0]
Output: 1
Explanation:
The only special triplet is (i, j, k) = (0, 2, 3), where:
nums[0] = 0,nums[2] = 0,nums[3] = 0nums[0] = nums[2] * 2 = 0 * 2 = 0nums[3] = nums[2] * 2 = 0 * 2 = 0
Example 3:
Input: nums = [8,4,2,8,4]
Output: 2
Explanation:
There are exactly two special triplets:
(i, j, k) = (0, 1, 3)nums[0] = 8,nums[1] = 4,nums[3] = 8nums[0] = nums[1] * 2 = 4 * 2 = 8nums[3] = nums[1] * 2 = 4 * 2 = 8
(i, j, k) = (1, 2, 4)nums[1] = 4,nums[2] = 2,nums[4] = 4nums[1] = nums[2] * 2 = 2 * 2 = 4nums[4] = nums[2] * 2 = 2 * 2 = 4
Constraints:
3 <= n == nums.length <= 1050 <= nums[i] <= 105
Approaches
3 approaches with complexity analysis and trade-offs.
The most straightforward approach is to use three nested loops to check every possible triplet of indices (i, j, k) that satisfy i < j < k. For each triplet, we verify if it meets the special triplet conditions. This method is easy to conceptualize but computationally very expensive.
Algorithm
- Initialize a counter
countto 0. - Use three nested loops to iterate through all possible triplets of indices
(i, j, k)such that0 <= i < j < k < n. - Inside the innermost loop, check if the conditions
nums[i] == nums[j] * 2andnums[k] == nums[j] * 2are met. - If the conditions are true, increment the
count. - After iterating through all triplets, return
countmodulo10^9 + 7.
Walkthrough
This method iterates through all combinations of three distinct indices i, j, and k from the array. The loops are structured to ensure that i < j < k, which is a requirement for the triplet. For each valid combination of indices, it performs a check to see if nums[i] and nums[k] are both equal to nums[j] * 2. A counter is maintained to keep track of how many such triplets are found.
class Solution { public int countSpecialTriplets(int[] nums) { int n = nums.length; long count = 0; int MOD = 1_000_000_007; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { for (int k = j + 1; k < n; k++) { // Use long for multiplication to prevent potential overflow, though not strictly necessary with given constraints. if ((long)nums[i] == (long)nums[j] * 2 && (long)nums[k] == (long)nums[j] * 2) { count++; } } } } return (int)(count % MOD); }}Complexity
Time
O(N^3) - Three nested loops iterate through the array, where N is the length of `nums`. This results in a cubic time complexity.
Space
O(1) - Constant extra space is used.
Trade-offs
Pros
Simple to understand and implement.
Requires no extra space.
Cons
Extremely inefficient and will lead to a 'Time Limit Exceeded' error for the given constraints.
We can improve upon the brute-force approach by changing our iteration strategy. Instead of iterating through all triplets, we can fix the middle index j and then search for the required i's and k's. For each j, we need to find how many indices i < j have nums[i] == 2 * nums[j] and how many indices k > j have nums[k] == 2 * nums[j]. The product of these two counts gives the number of special triplets for that specific j.
Algorithm
- Initialize a total count
totalTripletsto 0. - Iterate through the array with an index
jfrom1ton-2, consideringnums[j]as the middle element of a potential triplet. - For each
j, calculate thetargetVal = nums[j] * 2. - Initialize two counters,
count_i = 0andcount_k = 0. - In a nested loop, iterate from
i = 0toj-1to find the number of elementsnums[i]equal totargetVal. Store this incount_i. - In another nested loop, iterate from
k = j+1ton-1to find the number of elementsnums[k]equal totargetVal. Store this incount_k. - The number of triplets for the current
jiscount_i * count_k. Add this product tototalTriplets. - After the main loop finishes, return
totalTripletsmodulo10^9 + 7.
Walkthrough
The core idea is to iterate through each possible middle element nums[j]. For a fixed j, we need to find a pair of indices (i, k) such that i < j < k and nums[i] = nums[k] = 2 * nums[j]. We can do this by scanning the subarray to the left of j to count valid i's and the subarray to the right of j to count valid k's. The total number of triplets is the sum of these products over all possible j.
class Solution { public int countSpecialTriplets(int[] nums) { int n = nums.length; long totalTriplets = 0; int MOD = 1_000_000_007; for (int j = 1; j < n - 1; j++) { long targetVal = (long)nums[j] * 2; long count_i = 0; for (int i = 0; i < j; i++) { if (nums[i] == targetVal) { count_i++; } } if (count_i == 0) continue; long count_k = 0; for (int k = j + 1; k < n; k++) { if (nums[k] == targetVal) { count_k++; } } totalTriplets = (totalTriplets + (count_i * count_k)); } return (int)(totalTriplets % MOD); }}Complexity
Time
O(N^2) - For each element `j`, we scan its left and right subarrays. The total operations are proportional to the sum of `j + (n-j)` for all `j`, which simplifies to O(N^2).
Space
O(1) - No significant extra space is used besides a few variables for counting.
Trade-offs
Pros
More efficient than the O(N^3) brute-force approach.
Still relatively simple to reason about.
Cons
This approach is still too slow for the given constraints (
N <= 10^5) and will likely time out.
This is the most efficient approach, achieving a linear time complexity. We can optimize the O(N^2) approach by avoiding the repeated scans for count_i and count_k. We iterate through the array, considering each element nums[j] as the middle element. We maintain two frequency maps (or arrays, given the value constraints): one for counts of numbers to the left of j (leftFreq) and one for counts to the right (rightFreq). As we iterate from left to right, we can update these counts in O(1) time, allowing us to find count_i and count_k instantly.
Algorithm
- Define
MOD = 10^9 + 7. - Based on constraints, the maximum value for
nums[j]*2is2*10^5. Create two frequency arrays,leftFreqandrightFreq, of size200001, initialized to zero. - Populate
rightFreqby iterating throughnumsonce.rightFreq[x]will store the total count of numberxin the array. - Initialize
totalTriplets = 0(as a long to prevent overflow). - Iterate through the input array
numswith indexj. - In each iteration, let
val_j = nums[j].- First, decrement
rightFreq[val_j]. This signifies thatnums[j]is no longer on the 'right' side of the current position. - Calculate
targetVal = val_j * 2. - If
targetValis within the bounds of the frequency arrays:- Get the count of
targetValon the left:count_i = leftFreq[targetVal]. - Get the count of
targetValon the right:count_k = rightFreq[targetVal]. - Add the product
(long)count_i * count_ktototalTriplets.
- Get the count of
- Finally, increment
leftFreq[val_j]. This movesnums[j]to the 'left' side for subsequent iterations.
- First, decrement
- After the loop, return
totalTriplets % MOD.
Walkthrough
The key to this optimization is to process the array in a single pass while maintaining counts of numbers seen so far (left side) and numbers yet to be seen (right side).
First, we pre-calculate the frequency of all numbers in the array and store them in rightFreq. Then, we iterate through nums. For each element nums[j], we first 'remove' it from the right side by decrementing its count in rightFreq. Then, we can find the number of special triplets with nums[j] as the middle element. The number of valid i's is the count of 2 * nums[j] in leftFreq, and the number of valid k's is the count of 2 * nums[j] in the updated rightFreq. After calculating the contribution for j, we 'add' nums[j] to the left side by incrementing its count in leftFreq before moving to the next element.
class Solution { public int countSpecialTriplets(int[] nums) { int n = nums.length; int MOD = 1_000_000_007; // Constraints: 0 <= nums[i] <= 10^5 // target_val = nums[j] * 2, so max target_val is 2 * 10^5 int maxPossibleVal = 200001; int[] rightFreq = new int[maxPossibleVal]; for (int num : nums) { rightFreq[num]++; } int[] leftFreq = new int[maxPossibleVal]; long totalTriplets = 0; for (int val_j : nums) { // Move val_j from the right side to the middle rightFreq[val_j]--; long targetVal = (long)val_j * 2; if (targetVal < maxPossibleVal) { long count_i = leftFreq[(int)targetVal]; long count_k = rightFreq[(int)targetVal]; totalTriplets += count_i * count_k; } // Move val_j from the middle to the left side leftFreq[val_j]++; } return (int)(totalTriplets % MOD); }}Complexity
Time
O(N + M) - We iterate through the array of size N a constant number of times. The complexity is linear in the size of the input array and the range of its values. Since M is fixed by the constraints, this is effectively O(N).
Space
O(M) - Where M is the maximum possible value of `nums[j]*2`. Given the constraints, M is approximately `2*10^5`, which is a constant amount of space.
Trade-offs
Pros
Optimal time complexity, making it very efficient for large inputs.
Passes the given constraints with ease.
Cons
Requires extra space proportional to the maximum possible value of
nums[j]*2, which might be large if the value constraints were different.
Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.